最优化基础理论与方法

1、目录1最优化的概念与分类22. 最优化问题的求解方法32.1线性规划求解32.1.1线性规划模型32.1.2线性规划求解方法32.1.3 线性规划算法未来研究方向32.2非线性规划求解42.2.1一维搜索42.2.2无约束法42.2.3约束法42.2.4凸规划52.2.5二次规划52.2.6非线性规划算法未来研究方向52.3组合规划求解方法52.3.1 整数规划52.3.2 网络流规划72.4多目标规划求解方法72.4.1 基于一个单目标问题的方法72.4.2 基于多个单目标问题的方法82.4.3多目标规划未来的研究方向82.5动态规划算法82.5.1 逆推解法82.5.2 顺推解法92.5.

2、3 动态规划算法的优点及研究方向92.6 全局优化算法92.6.1 外逼近与割平面算法92.6.2 凹性割方法92.6.3 分支定界法92.6.4 全局优化的研究方向92.7随机规划92.7.1 期望值算法102.7.2 机会约束算法102.7.3 相关机会规划算法102.7.4 智能优化102.8 最优化软件介绍113 最优化算法在电力系统中的应用及发展趋势123.1 电力系统的安全经济调度问题123.1.1电力系统的安全经济调度问题的介绍123.1.2电力系统的安全经济调度问题优化算法的发展趋势121最优化的概念与分类最优化是应用数学的一个重要分支，最优化可定义为一种数学方法，用它可以对各

3、种生产活动进行规划，在可供利用资源(资源泛指矿藏、水能、人力、设备、原料、运输条件、生态环境、资金、时间、空问等等)的限制条件下，使生产活动得到最大的效益或用最少的资源完成指定的生产活动。最优化问题的数学表现形式为：式中，称为目标函数，若具体问题是求，则令，于是最大值问题就转化为最小值问题。称为等式约束条件，称为不等式约束条件，如果约束条件中有，则可令，于是原来的“”就变为了“”。满足约束条件的一组称之为一组可行解。满足目标函数的可行解称为最优解，即我们需要寻求的答案。许多现实和理论问题都可以建模成这样的一般性框架，最优化问题种类繁多，分类的方法也有许多。（1）按照变量的性质分类：1）确定性规

4、划：当最优化模型中所有变量都是确定性变量时，称为确定性规划。2）随机性规划：当模型中包含随机变量时，称为随机性规划。3）连续性规划：当模型中所有变量均是连续变量时，称为连续性规划。根据连续最优化模型中的函数的光滑与否，又分为光滑最优化和非光滑最优化，如果模型中所有的函数都连续可微，称为光滑最优化问题，否则为非光滑最优化问题。4）离散性规划：当模型中的变量取离散值时，称为离散性规划，又称组合优化。特别的，若问题的部分或所有的变量局限于整数值时，称这一类问题为整数规划问题。（2）按照有无约束条件分类：1）无约束规划：当最优化模型中不存在约束条件时，称为无约束规划。2）有约束规划：当模型中存在约束条

5、件时，称为有约束规划。（3）按目标函数的个数分类：1）单目标规划:只存在一个目标函数时，称这一类问题为单目标规划。2）多目标规划：当存在多个目标函数时，称为多目标规划。（4）按约束条件和目标函数是否是线性函数分类：1）线性规划：当目标函数是线性函数，而且约束条件是由线性等式函数和线性不等式函数来确定的，称这一类问题为线性规划。2）非线性规划：非线性规划研究的是目标函数或约束函数中含有非线性函数的问题。特别的，当目标函数是二次函数，而且约束条件是由线性等式函数和线性不等式函数来确定的时，称为二次规划。（4）根据是否和时间有关分类：1）动态规划：动态规划是解决多阶段决策过程的最优化的一种数学算法，

6、主要用于以时间或地域划分阶段的动态过程的最优化。2）静态规划：与时间无关的最优化问题。不同类型的最优化问题具有各自的求解方法，下面内容着重说明最优化问题的求解方法及未来研究方向，并介绍最优化方法在电力系统规划中的应用及发展。2.最优化问题的求解方法最优化方法是近几十年形成的，它主要运用数学方法研究各种优化问题的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营

7、的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。2.1线性规划求解2.1.1线性规划模型线性规划模型的一般表达方式如下所示：（2.1）其中，（）为待定的决策变量，己知的系数组成的矩阵A称为约束矩阵。A的列向量记为（）。A的行向量记为()。目标函数记为，向量称为价值向量，称为价值系数；向量称为右端向量。条件称为非负约束；表示变量可取正值、负值、或零值，称这样的变量为自由变量。2.1.2线性规划求解方法2.1.2.1单纯形法求解线性规划问题的基本方法是单纯形法，是研究得最为透彻的一个方向

8、，且至今仍是最好的应用最广泛的算法之一，已有单纯形法的标准软件，可在电子计算机上求解约束条件和决策变量数达10000个以上的线性规划问题。它的理论根据是：线性规划问题的可行域是n维向量空间Rn中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到。顶点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否是最优解；若不是，则按照一定法则转换到另一改进的基本可行解，再鉴别；若仍不是，则再转换，按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解也可用此法判别。单纯形法的一般解题步骤可归纳如下：把线性规划问题的约束方程组

9、表达成典范型方程组，找出基本可行解作为初始基可行解。若基本可行解不存在，即约束条件有矛盾，则问题无解。若基本可行解存在，从初始基本可行解作为起点，根据最优性条件和可行性条件，引入非基变量取代某一基变量，找出目标函数值更优的另一基本可行解。按步骤3进行迭代,直到对应检验数满足最优性条件（这时目标函数值不能再改善），即得到问题的最优解。若迭代过程中发现问题的目标函数值无界，则终止迭代。2.1.2.2内点算法除了单纯形算法之外，现在经常使用的线性规划求解方法还包括内点算法，内点算法中的代表即Karmarkar算法。Karmarkar算法运用了求解非线性规划问题的思想来解决线性规划问题。这种算法是在把

10、一般线性规划问题转化为Karmarkar所特有的标准型，再利用一种求解这种标准型的算法最终求出最优解。2.1.3线性规划算法未来研究方向内点法是最新的设计，实际应用上它也可以与单纯形法相抗衡，不少商业化软件已经上市，前景甚佳。目前线性规划的内点法也趋于成熟，这方面的研究者们目前大都致力于以线性规划作为特例的锥规划，以及如何利用线性规划松弛求解整数规划等方面的研究。2.2非线性规划求解非线性规划问题的求解一般要比线性规划困难很多，而且目前尚没有适合于各类非线性问题的一般算法，每种算法都有自己的特定的使用范围。有些情况下，为方便计算，也会把非线性规划问题近似为线性规划问题进行求解。2.2.1一维搜

11、索一维搜索是求解单变量非线性规划问题的方法。这类方法不仅有实用价值，而且大量多维最优化方法都依赖于一系列的一维最优化。常用的一维最优化方法有黄金分割法、切线法和插值法。2.2.1.1黄金分割法黄金分割法又称0.618法。它适用于单峰函数。其基本思想是：在初始寻查区间中设计一列点，通过逐次比较其函数值，逐步缩小寻查区间，以得出近似最优值点。2.2.1.2切线法又称牛顿法。它也是针对单峰函数的。其基本思想是：在一个猜测点附近将目标函数的导函数线性化，用此线性函数的零点作为新的猜测点，逐步迭代去逼近最优点。2.2.1.3插值法又称多项式逼近法。其基本思想是用多项式（通常用二次或三次多项式）去拟合目标

12、函数。此外，还有斐波那契法、割线法、有理插值法、分批搜索法等。2.2.2无约束法无约束法是求解无约束条件的非线性规划问题的方法，指寻求n元实函数f在整个n维向量空间Rn上的最优值点的方法。这类方法的意义在于：虽然实用规划问题大多是有约束的，但许多约束最优化方法可将有约束问题转化为若干无约束问题来求解。无约束最优化方法大多是逐次一维搜索的迭代算法。这类迭代算法可分为两类。一类需要用目标函数的导函数，称为解析法。另一类不涉及导数，只用到函数值，称为直接法。这些迭代算法的基本思想是：在一个近似点处选定一个有利搜索方向，沿这个方向进行一维寻查，得出新的近似点。然后对新点施行同样手续，如此反复迭代，直到

13、满足预定的精度要求为止。根据搜索方向的取法不同，可以有各种算法。属于解析型的算法有：梯度法：又称最速下降法。这是早期的解析法，收敛速度较慢。牛顿法：收敛速度快，但不稳定，计算也较困难。共轭梯度法：收敛较快，效果较好。变尺度法：这是一类效率较高的方法。其中达维登-弗莱彻-鲍威尔变尺度法，简称DFP法，是最常用的方法。属于直接型的算法有交替方向法（又称坐标轮换法）、模式搜索法、旋转方向法、鲍威尔共轭方向法和单纯形加速法等。2.2.3约束法指前述一般非线性规划模型的求解方法。常用的约束最优化方法有4种。拉格朗日乘子法：它是将原问题转化为求拉格朗日函数的驻点。制约函数法：又称系列无约束最小化方法，简称

14、SUMT法。它又分两类，一类叫惩罚函数法，或称外点法；另一类叫障碍函数法，或称内点法。它们都是将原问题转化为一系列无约束问题来求解。可行方向法：这是一类通过逐次选取可行下降方向去逼近最优点的迭代算法。如佐坦迪克法、弗兰克沃尔夫法、投影梯度法和简约梯度法都属于此类算法。近似型算法：这类算法包括序贯线性规划法和序贯二次规划法。前者将原问题化为一系列线性规划问题求解，后者将原问题化为一系列二次规划问题求解。2.2.4凸规划这是一类特殊的非线性规划。在前述非线性规划数学模型中，若f是凸函数，诸都是凹函数，诸都是一次函数，则称之为凸规划。所谓f是凸函数，是指f有如下性质：它的定义域是凸集，且对于定义域中

15、任意两点x和y及任一小于1的正数，下式都成立：（2.1）将上述不等式中的不等号反向即得凹函数的定义。所谓凸集，是指具有如下性质的集合：连结集合中任意两点的直线段上的点全部属于该集合。对于一般的非线性规划问题，局部解不一定是整体解。但凸规划的局部解必为整体解，而且凸规划的可行集和最优解集都是凸集。2.2.5二次规划二次规划是一类特殊的非线性规划。它的目标函数是二次函数，约束条件是线性的。求解二次规划的方法很多。常用方法是拉格朗日法，较简便易行的是沃尔夫法。它是依据库恩塔克条件，在线性规划单纯形法的基础上加以修正而成的。此外还有莱姆基法、毕尔法、凯勒法等。2.2.6非线性规划算法未来研究方向就算法

16、的发展来看，早期的方法以最速下降法和共轭梯度法为主，目前，序贯二次规划法是一类被用于广泛求解一般非线性规划的有效算法，同时也还有许多研究者在为改善这类算法作努力，其中包括序列线性规划算法以及内点算法等。非线性规化算法通常使用线搜索策略选取步长，或通过求解信赖域子问题而得到新的迭代点。这两个方面的研究非常基本，但仍有改善的空间。对于大规模问题，如何设计子空间算法；以及如何有效求解一般非线性规划的全局最优，和一些来自于图像处理等领域的特殊的非光滑问题是目前非线性规划比较重要的研究问题。总之，尽管在表面上看非线性规划已经有许许多多的研究，但由于非线性的存在，好的研究结果还将会不断出现，并且随着问题的

17、不同而产生更加具有针对性的特殊算法。2.3组合规划求解方法组合优化是20世纪60年代逐渐发展起来的一个交叉学科分支，它的研究对象是有限集合上的极值问题。一个组合优化问题由三部分构成：已知条件的输入、可行解的描述、目标函数的定义。经典的组合优化问题包括网络流、旅行商、排序、装箱、着色、覆盖、最短网络等等。组合优化的一个理论基础是计算复杂性理论，据此组合优化的可以分为两类：P问题类和NP难问题类；属于前者的问题有多项式时间算法，属于后者的问题一般认为不存在多项式时间算法，通常采用精确算法、启发式算法和近似算法等方法求解。精确算法包括简单枚举法、分而治之法、分支定界法、动态规划法等；启发式算法包括贪

18、婪策略、局部搜索、禁忌搜索、神经网络、模拟退火、遗传算法等；近似算法包括贪婪策略法、局部搜索法、原始对偶法、划分法、松弛法、内点算法、半定规划等；其中启发式算法在实际工程中应用较广。2.3.1整数规划在组合规划中，有一个特殊的类型，其变量（全部或部分）限制为整数，称为整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0-1规划，它的变数仅限于0或1。从约束条件的构成又可细分为线性，二次和非线性的整数规划。目前所流行的求解整数规划的方法往往只适用于整数线性规划，除上述介绍的启发式算法，现今比较成功又流行的方

19、法是分支定界法、割平面法和分解算法。随着社会的发展，实际规划问题的规模越来越庞大，模型也越来越复杂，现在经常将几类算法混合使用。2.3.1.1分支定界法分支定界法是一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。步骤如下：(1)求整数规划的松弛问题最优解。(2)若松弛问题的最优解满足整数要求，得到整数规划的最优解，否则转下一步。(3)任意选一个非整数解的变量，在松弛问题中加上约束及组成两个新的松弛问题，称为分支。新的松弛问题具有如下特征：当原问题是求最大值时，目标值是分支问题的上界；当原问题足求最小值时，目标值是分支问题的下界。(4)检查所有分支的解及目标函数值，若某分支的解是整数并

20、且目标函数值大于(max)等于其他分支的目标值，则将其他分支剪去不再计算，若还存在非整数解并且目标值大于( max)整数解的目标值，需要继续分支，再检查，直到得到最优解。2.3.1.2割平面法割平面法是1958年由美国学者高莫利提出的求解全整数规划的一种比较简单的方法。用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)而把所有的整数解

21、都保留下来，故称新增加的约束条件为割平面当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。步骤如下：(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。(2)求一个

22、“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。2.3.1.3分解算法分解算法的基本思想是，对整数规划问题的约束函数或者目标函数进行适当的区分和变换，得到另一个或者一系列相对简单的优化问题，通过求解比较简单的优化问题得到整数规划问题的最优解。从本质上说，分解算法也算是一种松弛方法，但他同前面介绍的割平面法、分支定界法不同之处在于，分解算法常常要将多个约束或变量的作用加以区别，分别对待。分解算法包括基于拉格朗日松弛的分解算法和Benders分解法。(1)基于拉格朗日松弛的分解算法拉格朗日松弛算法是将约束与其相应拉格朗日乘子的乘积作为惩罚项加

23、入目标函数,形成拉格朗日问题,进而通过求解拉格朗日问题的对偶问题来实现原问题的求解,该方法是目前求解大规模整数规划问题最有效的方法之一。拉格朗日松弛算法是将问题分解为双层优化问题,上层为最大化以拉格朗日乘子为变量的对偶问题,下层是对给定的拉格朗日乘子,最小化拉格朗日问题,可以分解为若干单机组问题分别进行求解,通过不断交替求解上下层优化问题实现对问题的求解。由于对偶问题不可微,通常釆用次梯度法、束方法等不可微方法进行求解。(2)Benders分解法分解法是求解整数规划问题的一类常用的数学规划方法，它的基本思想是将问题的变量分为离散变量和连续变量两类，将问题分解为处理离散变量的混合整数线性规划主问

24、题和处理连续变量的（非）线性规划子问题，通过求解混合整数线性规划主问题得到的整数最优解来产生（非）线性规划子问题，再用求解（非）线性规划子问题得到的解来构造新的线性不等式约束并添加到主问题中，通过逐次交替求解混合整数线性规划主问题和（非）线性规划子问题来获得原问题的最优解。2.3.1.4整数规划未来研究方向随着整数规划理论和算法的发展，整数规划已成为应用最广泛的最优化方法之一，特别是近年来整数规划算法技术和软件系统的发展和推广，整数规划得到了广泛的应用和发展。整数规划问题的困难和挑战来源于三个方面：一是大部分整数规划问题都是NP-难的，故本质上不太可能存在和线性规划和凸规划一样有效的算法；二是

25、对整数点集合(如多面体格点理论和全单模理论)和整数变量的函数在数学上缺乏有力的理论和工具；三是实际问题的规模往往超过现有算法的求解能力，尽管现有的一些整数规划软件可以求解任意线性、二次和非线性整数规划问题，但往往不能处理来源于实际问题的整数规划模型，例如运输和交通中的大规模。0-1混合线性整数规划问题，金融优化中的离散约束问题等。整数规划未来发展方向和关键问题包括：(1)整数多面体凸包的刻画；(2)随机整数规划；(3)多层整数规划；(4)混合0-1二次整数规划；(5)协正规划；(6)半定整数规划。2.3.2网络流规划组合规划问题中有一种特殊的问题叫做网络流规划，网络流是一种类比水流的解决问题方

26、法，与线性规划密切相关。一般包括最短路问题，最大流与最小割问题、最小费用网络问题、最大森林问题。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。2.4多目标规划求解方法多目标规划问题的直接求法通常是寻找它的整个最优解集，除了特殊的情况，计算所有最优解是比较困难的。由于这个原因，对直接解法的研究结果还比较少。本节只介绍一些间接的求解多目标规划的方法，这些方法的共同特点是将多目标规划问题转换成一个或多个单目标规划问题，然后，通过求解单目标优化问题得到一个或多个最优解。一般的，并不要求间接解法给出问题的所有最优解。2.4.1基于一个单目标问题的方法

27、这类方法的基本思想如下：首先，将原来的多目标规划问题转换成一个单目标优化问题，然后，利用非线性优化算法求解该单目标问题，把所求得的最优解作为问题的最优解。这种方法的核心在于，保证所构造的单目标问题的最优解是有效解或若有效解。包括线性加权和法、主要目标法、极小极大法。2.4.1.1线性加权和法线性加权和法是根据p个目标函数的重要程度，分别赋予一定的权系数，然后将所有的目标函数加权求和作为新的目标函数，在多目标规划问题的可行域上求出新的目标函数的最优值。2.4.1.2主要目标法对于多目标问题，主要目标法是根据实际情况，首先确定一个目标函数为主要目标，而把其余p-1个目标函数作为次要目标，然后，借助

28、于决策者的经验，通过选定一定的界限值把次要目标函数转化为约束条件，通过求解这样一个单目标问题获得原问题的解。2.4.1.3极小极大法极小极大法的基本思想是在目标函数的p个分量中，极小化目标函数的最大分量，将该问题的最优解作为原问题的弱有效解。一般的，通过引入目标函数的权向量将问题转换为单目标问题，把该情况下的最优解称为原问题的极小化极大意义下的最优解。2.4.2基于多个单目标问题的方法这类方法的基本思想是，根据某种规则，首先将多目标规划问题转换成有一定次序的多个单目标优化问题；然后，依次分别求解这些单目标优化问题，并且把最后一个单目标优化问题的最优解作为原问题的最优解。基于多个单目标问题的方法

29、的核心是，保证最后一个单目标优化问题的最优解是多目标问题的有效解或弱有效解。包括分层排序法，重点目标法，分组排序法。2.4.2.1分层排序法分层排序法是根据目标的重要程度将它们一一排序，然后，分别在前一个目标的最优解集中，需求后一个目标的最优解集，并把最后一个目标函数的最优解作为原问题的最优解。2.4.2.2重点目标法重点目标法是在p个目标函数中，首先确定最重要的目标，并求出其最优解集，然后在此最优解集上求解其余p-1个目标对应的多目标规划问题.2.4.2.3分组排序法分组排序法的基本思想是根据某种规则，首先将多目标函数的目标分成若干组，使得在每个组内的目标的重要程度相差不多，此时，每组目标实

30、际上对应着一个新的多目标规划问题，然后，依次在前一组目标对应问题的最优解集中，寻找后一组目标对应问题的最优解集，并把最后一组目标对应问题的最优解作为原问题的最优解。2.4.3多目标规划未来的研究方向在很多实际问题中，例如经济、管理、军事、科学和工程设计等领域，衡量一个方案的好坏往往难以用一个指标来判断，而需要用多个目标来比较，而这些目标有时不甚协调，甚至是矛盾的，因此有许多学者致力于这方面的研究。然而至今关于多目标最优解尚无一种完全令人满意的定义，所以在理论上多目标规划仍处于发展阶段。2.5动态规划算法当系统模型具备马尔科夫性，同时目标函数可分且嵌套单调时，基于贝尔曼提出的最优性原理，可将求解

31、多阶段全局最优决策问题分解为一系列在各个时间段上的局部优化问题进行求解，这种算法叫做动态规划法。动态规划是对解最优化问题的一种途径、一种方法，而不是一种特殊算法。不像搜索或数值计算那样，具有一个标准的数学表达式和明确清晰的解题方法。动态规划设计往往是针对一种最优化问题，由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题，有各具特色的解题方法，而不存在一种万能的动态规划算法，可以解决各类最优化问题。因此必须具体问题具体分析处理，以丰富的想象力去建立模型，用创造性的技巧去求解。同时值得注意的是，虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些

32、与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。下面介绍两种常用的动态规划算法思路：2.5.1逆推解法逆推解法的步骤是利用已知条件从最后一个阶段开始有后向前推算，求得各阶段的最优决策和最优指标函数，最后算出第一阶段的目标函数时便得到最优指标函数值，然后再从第一阶段利用状态转移方程确定最优轨线和最优策略。2.5.2顺推解法顺推解法和逆推解法的递推顺序正好相反，在顺推解法中从第一阶段开始，利用状态转移方程从前向后推算。2.5.3动态规划算法的优点及研究方向相比其它解法，特别是在有扰动或在随机情况下，动态规划总是能有效地

33、提供一个在当前信息集下的最优反馈控制策略。在过去的若干年里，动态规划取得了不少可喜的进展，特别是它被扩展到多目标动态规划；动态规划应用在本世纪前后的一个重大突破是其在海量数据分析中的应用，特别是人类基因组计划完成以后，它成为生物信息学的一个基本模型和工具。然而，在克服被贝尔曼称之为“维数灾”的这一动态规划致命弱点的方面，至今尚未取得突破性的进展。所以寻求克服维数灾的有效算法对动态规划在高维问题中的应用具有它的紧迫性。另外，求解不可分优化问题得到的最优策略并不满足最优性原理，或不具备时间一致性。这牵涉到不可分优化问题模型本身的合理性。因此怎样找出一组可分优化问题来逼近一个给定的不可分优化问题也对

34、动态规划发展具有显然的重要性。2.6全局优化算法全局优化研究的是非线性目标函数在某个特定区域上全局最优的特征和计算方法。由于目标函数通常不是凸的函数，特定区域也有可能不是凸集，所以全局优化也可以称为非凸优化。由于很可能在一个全局优化问题里存在多个局部最优解，且它们不同于问题的全局最优解，因此人们无法借助于经典的局部优化方法求解这些问题，下面介绍三种经典的全局优化算法。2.6.1外逼近与割平面算法外逼近的基本思想是，先将可行域D松弛成一个相对简单的集合，并且在这个松弛集合上极小化目标函数。若松弛问题的解是可行的，那么原问题的求解过程完成，否则，添加一个辅助性约束割去的一部分，生成一个新的松弛集合

35、。令松弛集合替代原松弛集合，重复以上过程，以此类推，循环往复，就得到一个逼近原问题的松弛问题序列，求解松弛形式的子问题，得到一个最优解，若，则为问题的最优解。2.6.2凹性割方法在外逼近和割平面算法中，割作为一种工具是以合取方式使用的，即添加的割一般不会去掉可行点，并且所有割平面的交集构成整个可行域，因此，这种技术非常适合处理可行域是闭凸集这种情形。此时，支撑超平面能够将该凸集和它之外的点分离开来。然而，某些优化问题的可行域是非凸的，我们希望对非凸的集合进行逼近，用某种特定的割将非凸集与它之外的点分离开来，这就是凹形割方法，这是一种以析取方式使用割的技术，即每一割可能会去掉感兴趣区域的一部分，

36、但是所有割的并集会覆盖我们感兴趣的区域。2.6.3分支定界法分支定界法不但能够求解整数规划问题，而且也能够求解全局优化问题，在利用分支定界法求解全局优化问题时，首先，要对优化问题的可行域进行松弛；然后，将松弛集合依次分割成一些小集合（称为分支），在每个分支中确定待极小化的目标函数的下界（称为定界，有时，也需要确定目标函数最优值的上界，以便加快分支定界的收敛过程）；通过比较不同分支对应的目标函数最优值的界的关系，选择需要进一步分割的分支。依次类推，直至得到优化问题的最优解，或者满足要求的近似解。2.6.4全局优化的研究方向全局优化问题的困难在于非凸性使卡罗胥一库恩一塔克条件一般不足以保证全局最优

37、性，从而我们无法利用局部优化算法寻找全局最优点。本质上，由于导数是局部性质，因而不能期望基于导数性质的传统优化算法有希望求到全局解，全局算法需要函数和问题的全局性质。目前的数学理论很难或无法刻画一般多元函数的全局性质，这是全局优化问题的本质困难所在。全局优化的未来发展方向和关键问题包括：(1)凸逼近和凸松弛方法；(2)非凸二次规划；(3)基于模拟仿真技术的全局优化算法；(4)特殊结构的全局优化问题。2.7随机规划随机最优化问题是特指带有随机因素的最优化问题，需要利用概率统计、随机过程以及随机分析等工具。2.7.1期望值算法通常人们处理随机因素的第一种方法是期望值方法，将随机的因素用它的期望值代

38、替，将问题转化为确定性问题考虑。2.7.2机会约束算法第二种方法是在概率意义下考虑优化问题。例如在置信区间范围内考虑优化问题，将问题转换为概率约束或者是机会约束的优化问题；又例如考虑极大化某些事件的概率问题，也称为机会约束算法。第二种方法相对于期望值方法的优点是考虑到各种风险的影响，缺点是使得问题的处理变得相对困难。2.7.3相关机会规划算法第三种即是刘宝碇教授于1997年提出的相关机会规划，是一种使事件的机会在随机环境下达到最优的理论。2.7.4智能优化智能优化是涉及数学、运筹学、生命科学、计算机科学等的一个交叉研究方向。智能优化主要是借鉴仿生学和拟物的思想，基于人们对生物体智能机理和某些自

39、然规律的认识，采用数值计算的方法去模拟和实现人类的智能、生物智能和其它社会与自然的规律。智能优化本质上也属于随机优化，包括：遗传算法、粒子群算法、蚁群算法、人工神经网络算法等。2.7.4.1遗传算法遗传算法是模拟达尔文生物进化论的遗传学机理和自然选择的生物进化过程的计算模型，是通过模拟自然界的进化过程来搜索最优解的一种方法。遗传算法是从一个问题的可行解的种群开始的，通过对所产生的每个染色体进行评价，并根据适应度来选择染色体，使适应度好的染色体比适应度差的染色体有更多的繁殖机会。末代种群中的最优个体可以作为问题近似最优解。它的主要特点是群体搜索策略和群体之间的信息交换。与解析法、穷举法、随机法等

40、传统搜索方法相比，遗传算法具有不需搜索空间的知识、并行爬峰、编码方法适应性广等特点。遗传算法尤其适用于处理传统搜索方法难以解决的复杂的非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。2.7.4.2神经网络算法神经网络是一种运算模型，由大量的节点(或称神经元)和之间相互连接构成。每个节点代表一种特定的输出函数，称为激励函数。每两个节点间的连接都代表一个对于通过该连接信号的加权值，即为权重，相当于人工神经网络的记忆功能。网络的输出则依据网络的连接方式，权重值和激励函数的不同而不同。神经网络的特点和优越性主要有三点：(1)自学习

41、功能；(2)联想存储功能；(3)高速寻找优化解的能力，神经网络主要应用在模式识别、自动控制、人工智能领域。近年来，神经网络与其他方法相结合的策略也得到了广泛的应用，且取得了很大的进展。2.7.4.3粒子群算法它是通过模拟鸟群觅食行为而发展起来的一种基于群体协作的随机搜索算法。通常被认为是群集智能的一种。在这类算法中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。粒子群算法初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。一个就是粒子本身所找到的最优解，这个解叫做个体极值，另一个极值是整个种群目前找到的最优解，这个极值是全局极值。目前它已广泛应用于函数优化，神经网络训练，模糊系统控制以及其它应用领域。2.7.4.4蚁群算法蚁群算法的基本思想来源于蚂蚁在寻找食物过程中发现路径的行为。它是一