优化算法.ppt

1、南开大学 马志斌 多维无约束最优化问题 ，其中 。这个问题的求解是指，在 中找一点 ，使得对于任意的 都有 成立。点 就是问题的全局最优点。对于问题，为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代公式 ，按照特定的算法产生一串点列 。如果点列收敛，则该点列的极限点为问题的最优解。)(minXf1:RRfn常用无约束最优化方法nR*X)()(*XfXfnRX*X0XkkkkPtXX1kX1.最速下降法 在基本迭代公式中，每次迭代搜索方向 取为目标函数f（X）的负梯度方向即 ，而每次迭代的步长 取为最优步长，由此所确定的算法称为最速下降法。最速下降法的优点是算法简单

2、，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有个严重缺点就是收敛速度慢。kP)(kkXfPkt2.Newton法 如果目标函数f（X）在 上具有连续二阶偏导数，其Hesse矩阵G(X)正定并且可以表达为显式，就可以使用Newton法。设最优化问题为minf（X），其中f：二阶可导，Hesse矩阵 f（X）正定。将f（X）在 处展开成二阶泰勒公式，于是有 显然Q（X）是二次函数，特别由假设知Q（X）还是正定二次函数，所以Q（X）是凸函数且存在唯一全局极小点，为求此最小点，令 即可解得 ，亦即 。称 为从点 出发的Newton方向。从初始点开始，每一

3、轮从当前迭代点出发，沿Newton方向并取步长 的算法称为Newton法。nR1RRn)()(21)()()()()(2kkTkkTkkXXXfXXXXXfXfXQXf0)()()(2kkkXXXfXfXQ)()(12kkkXfXfXX)()(121kkkkXfXfXX)()(12kkkXfXfPkX1kt20XX Newton法收敛速度非常快，具有二次收敛的优点，但它存在下面四个严重的缺点：（1）尽管每次迭代不会使目标函数f（X）上升，但仍不能保证f（X）下降。当Hesse矩阵非正定时，Newton法的搜索就会失败。（2）对初始点要求严格。一般要求比较接近或有利于接近极值点，而这在实际计算中

4、是比较难办的。（3）在进行某次迭代时可能求不出搜索方向。由于搜索方向为 ，若目标函数在 点Hesse矩阵是奇异的，则 不存在，因而不能构成Newton方向，从而使迭代无法进行。（4）Newton方向构造困难，计算相当复杂，除了求梯度以外还需计算Hesse矩阵及其逆矩阵，占用机器内存相当大。)()(12kkkXfXfP12)(kXfkX3.修正Newton法 为了克服Newton法的缺点，人们保留选取Newton方向作为搜索方向，摒弃其步长恒为1，而用一维搜索法确定其最优步长。由此产生的算法称为修正Newton法（或阻力Newton法）。修正Newton法克服了Newton法的缺点。特别是，当迭

5、代点接近最优解时，此法具有收敛速度快的优点，对初始点的选择要求不严。但是，修正Newton法仍需要计算的目标函数的Hesse矩阵和逆矩阵，所以计算量和存贮量均很大。另外，当目标函数的Hesse矩阵在某点出现奇异时，迭代将无法进行，因此修正Newton法仍有局限性。4.共轭方向法 设 是对称正定矩阵。对于非零向量 ，若有 ，则称 和 相互A共轭或A正交的。通常，我们把从任意点 出发，依次沿某组共轭方向进行一维搜索的求解最优化问题的方法，叫做共轭方向法。一般地，在n维空间中可以找出n个相互共轭的方向，对于n元正定二次函数，从任意初始点出发，顺次沿这n个共轭方向最多做n次直线搜索就可以求得目标函数的

6、极小点。这就是共轭方向法的算法形成的基本思想。对于n元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，那么这种说法称为具有二次终止性。共轭方向法是二次终止的。一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快。2P1PnRPP21,nnRAnRX 0021APPT5.共轭梯度法 如果在共轭方向法中初始的共轭向量 恰好取为初始点 处的负梯度 ，而以下各共轭方向 由第k迭代点 处的负梯度 与已经得到的共轭向量 的线性组合来确定，即，k=0，1，n-2，那么就构成了一种具体的共轭方向法。因为每一个共轭向量都是依赖于迭代点处的负梯度而构造出来的，所以称为共轭梯度法。

7、利用目标函数的梯度信息，可知n个共轭方向 ，由此得共轭梯度法。实际上，可以把共轭梯度法看做是最速下降法的一种改进。当令时，就变为最速下降法。共轭梯度法由于不涉及矩阵，仅仅存储向量，因而存储量小，适合于维数较高的优化问题。另外，共轭梯度法不要求精确的直线搜索。但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低方法的效能。克服的办法是：重设初始点，即把经过n+1次迭代得到的 作为初始点重新迭代。0P0X)(00Xfg1kP1kX1kXkP0kkkkkPXfP)(112,2,1,0,)()(2-n,2,1,0,)()(221k1100nkXfXfkPXfPXfPkkkkkkkg6.变尺度

8、法 我们知道Newton法最突出的优点是收敛速度快，在这一点上其他算法无法比拟。因此，建议凡是Hesse矩阵比较容易求出的问题尽可能使用Newton法求解。然而Newton法还有一个严重缺陷，就是每次迭代都要计算目标函数的Hesse矩阵及其逆矩阵，当问题的维数n比较大时，计算量迅速增加，从而抵消了Newton法的优点。为此，人们开始寻找一种既可以保持Newton法收敛速度快的优点，又可以摆脱Hesse矩阵的计算，这就是变尺度法。在Newton法中，基本迭代公式 ，其中 ，。令 ，于是有 ，k=0，1，2，其中 是初始点，和 分别是目标函数f（X）在点 的梯度和Hesse矩阵。为了消除这个迭代公

9、式中的Hesse逆矩阵 ，可用某种近似矩阵 来替换它，即构造一个矩阵序列 去逼近Hesse逆矩阵序列 。此时 。为使 确实与 近似并且有容易计算的特点，必须对 附加某些条件：（1）为保证迭代公式具有下降性质，要求 中的每一个矩阵都是对称正定的。（2）要求 之间的迭代公式具有简单形式。显然 是最简单的形式了，其中 称为校正矩阵。（3）必须满足拟Newton条件。所谓拟Newton条件为kkkkPtXX11ktkkkkgGXX110XkgkGkX1kG)(kkXHH kH1kGkkkkgHXX1kHkkkEHH1kE)()(111kkkkkXXggH)()(12kkkXfXfP)(),(2kkkk

10、XfgXfGkHkH1kGkHkH7.坐标轮换法 坐标轮换法的寻优思路是：先选定一个初始点 作为第一轮搜索的始点，依次沿n个坐标轴方向进行一维搜索，每次只在一个坐标轴方向进行一维搜索，其他的（n-1）个变量保持不变。在沿第一个坐标轴方向进行一维搜索得到目标函数值的最小点（或近似最小点）后，再以此点作为始点转到第二个坐标轴方向进行一维搜索得到 ，直到沿第n个坐标轴方向搜索结束得到 为一个循环。如果 不满足收敛准则，则以 作为初始点转入下一轮循环，直到经过k次循环，获得满足收敛准则的点 ，即作为最优点 。坐标轮换法的优点是算法简单，计算量小，其缺点是计算效率低，对高维问题尤为突出。因此，坐标轮换法

11、通常用于维数较低的优化问题。0X)1(1X)2(1X)(1nX)(nkX*X)(1nX)(1nX8.单纯形法 单纯形法是利用对简单几何图形各顶点的目标函数值作相互比较，在连续改变几何图形的过程中，逐步以目标函数值较小的顶点取代目标函数值最大的顶点，从而进行求优的一种方法。以求二元函数极小点为例，说明单纯形法形成的原理。设二元函数 在 平面上取不在同一条直线上的三个点 ，和 ，并以它们为顶点构成一单纯形三角形。算出各顶点的函数值 ，比较其大小，现假定比较后有 ，这说明 点最差，点最好，点次差。为了寻找极小点，一般来说应向最差点的反对称方向进行搜索。以 记为 的中点，在 的延长线上取点 ，使 ，称

12、为 关于 的反射点。),()(21xxfXf21Oxx1X2X3X)(1Xf)(2Xf)(3Xf4X5X)()()(321XfXfXf32XX41XX1414452)(XXXXXX1X2X3X5X1X4X 算出 的函数值 ，可能出现以下几种情形：（1）这说明搜索方向正确，可进一步扩大效果，继续沿 向前搜索。这时取 ，其中为扩张因子，一般取=1.22.0。如果 ，说明扩张有利，就可以用 点代替 点构成新的单纯形 。如果 ，说明扩张不利，舍弃 ，仍以 代替 构成新的单纯形 。（2）这说明搜索方向正确，但无须扩张，以 代替 其构成新的单纯形 。（3）这表示 点走得太远，应缩回一些。若以表示压缩因子，

13、则有 ，常取0.5。以 代替 构成新的单纯形 。（4）这时应压缩更多一些，将新点压缩至 至 之间。令 。如果 ，则以 代替 构成新的单纯形 ，否则认为 方向上所有点的函数值 都大于 ，不能沿此方向搜索。这时，可以以 为中心进行缩边。若使顶点 和 向 移近一半距离，得新的单纯形 ，以此单纯形为基础再进行寻优。单纯形法上机占用内存很少，对变量不多且精度要求不高的问题很方便，但当变量个数多于10个以上时，就显得不十分有效了。5X)(5Xf)()(35XfXf51XX)(1446XXXX)()(56XfXf6X,632XXX)()(56XfXf,532XXX)()()(253XfXfXf)()()(1

14、52XfXfXf)(4547XXXX7X,732XXX)()(15XfXf)()(4141448XXXXXXX)()(18XfXf8X,832XXX,1093XXX1X6X5X1X5X1X,532XXX5X1X1X4X1X41XX)(Xf)(1Xf3X3X1X2X常用约束最优化方法 一般的约束最优化问题，其数学模型为 ，求解最优化问题，就是要在可行域 中找一个可行点 ，使目标函数f（X）取得最小值。mjXhliXgtsXfji,2,1,0)(,2,1,0)(.)(min,2,1,0)(;,2,1,0)(mjXhliXgXDji*X1.外点罚函数法 根据约束特点（等式或不等式）构造某种“罚函数”

15、，然后把它加入到目标函数中去，使得对约束最优化问题的求解转化为对一系列无约束问题极小点或者无限地向可行域靠近，或者一直保持在可行集内移动，直到收敛于原来约束最优化问题极小点。构造函数 ，其中 。上式中，（X）称为惩罚函数，i=1，2，l。是一个逐渐增大的参数，称为惩罚因子。外点罚函数法的思想就是：当点 时，设法加大不可行点处的函数值，使不可行点不能成为问题在 中的最优解。外点罚函数法是通过一系列惩罚因子 ，k=0，1，2，求 的极小点来逼近原约束问题的最优点。这一系列的无约束极小点 将从约束可行域外部向约束边界运动。实际上，随着惩罚因子的增大，迫使惩罚项的值逐渐减小，从而使 的极小点 沿着某一

16、运动轨迹逐渐接近等式约束面与起作用的不等式约束面上的最优点 。当 趋近于无穷大时，的极小点就是原问题的最优点 。)()(),(XMXfMXFkkkMnR),(kMXF)(*kMXliiimjjXguXgXhX1221)()()()(,0,0)(时当时，当DXDXX时当时当0)(,10)(,0)(XgXgXguiiiDX kM),(kMXF)(*kMX*XkM),(kMXF*X2.内点罚函数法 内点罚函数法的迭代过程均在可行域D内进行，它是通过在D内寻找一串点列X（）来逼近最优解 。首先在D的边界设置一道障碍，当从可行域D中的某点 出发进行迭代时，每当迭代点靠近D的边界时，便被此边界上的障碍阻挡

17、碰回，换句话说，所谓阻挡碰回，就是当迭代点靠近D的边界时，离边界越近函数值增加越大，特别当迭代点到达边界上时，函数值变为无穷大。由此可以想象不可能在靠近D的边界上取得最优解，只能在远离D的边界内找到最优解。构造函数 ，其中，0是一个逐渐减小的参数且趋近于0，称为障碍因子，称为障碍函数。kr0XliikkXgrXfrXF1)(1)(),(liiXg1)(1*Xkr 内点罚函数法的优点在于每次迭代点都是可行点，当迭代到一定次数时，尽管可能没有达到约束最优点，但可以被接受为一个较好的近似最优点。在内点罚函数法中，障碍函数的定义域是约束可行域。因此，在求 的最优解时，并不是求它在整个n维欧式空间 中的

18、最优解，而是求 在约束可行域 上的极小点。这是因为障碍函数 在D的边界上无定义，而在D的外部某些项为负，并且可取绝对值任意大的负值，从而使 趋近于 ，所以 在全空间 内的极小点是不存在的。因此，在用无约束优化方法求 的最优解时，要防止越过约束边界而搜索到非可行域中去，这就要求在一位搜索时，要适当控制步长，保证搜索在可行域内进行。,2,1,0)(|liXgXDiliiXg1)(1),(krXFnR),(krXF),(krXF),(krXFnR),(krXF3.混合罚函数法 外点罚函数法的初始点可以任选，适用于求解具有等式约束与不等式约束的优化问题；而内点罚函数法要求初始点在可行域内，适用于求解不

19、等式约束优化问题。为了综合外点罚函数法和内点罚函数法的优点，常将两种算法结合起来使用，这样便形成了混合罚函数法。对于同时具有不等式约束和等式约束的优化问题，混合罚函数法采用的罚函数形式又分为内点和外点形式两种。下面只介绍内点形式的混合罚函数，即 。采用内点形式的混合罚函数时，初始点 应选为满足各个不等式约束条件的点，障碍因子 也应按内点罚函数法取为递减序列.在混合罚函数法 中，的作用是限制搜索跑出不等式的约束确定的区域，相当于内点罚函数法，而 的作用是迫使搜索点向等式约束面靠近，相当于外点罚函数法。limjjkikkXhrXgrXfrXF112)(1)(1)(),(liiXg1)(1mjjXh

20、12)(kr0X),(krXF4.约束坐标轮换法 约束坐标轮换法是在无约束坐标轮换法的基础上，加入由约束函数构成的可行性限制，使每次迭代都必须在可行域内进行。它的基本思想是将一个n维的约束优化问题转化为依次沿n个坐标轴方向轮流进行迭代的一维搜索问题。约束坐标轮换法通常利用加步搜索法来确定搜索步长。约束坐标轮换法具有算法明了、迭代简单、便于使用者掌握运用等优点。但是，它的收敛速度慢，对于维数较高的优化问题很费机时。另外，这种方法在某些情况下还会出现“死点”的病态。通常的做法是输入多个初始点，并给出各种不同的初始步长进行多次运算，再从众多的输出解中进行比较而排除伪最优点。5.复合形法 复合形法是无

21、约束最优化问题中单纯形法的推广。其基本思想是：在可行域内选取k个点作为初始复合形的顶点，然后比较这些顶点的目标函数值，目标函数值最大的点为最坏点。接着确定目标函数值的下降方向，在此方向上求一既能使目标函数值有所下降，而又满足所有的约束条件的新点，以替代最坏点而构成一个新的复合形。如此重复计算，使复合形不断向最优点移动和收缩，直至达到要求的收敛精度为止。复合形法是一种直接法。在用直接法求解约束优化问题的方法中，复合形法是一种较好的方法。由于这种方法不需要计算目标函数的导数，也不进行一位搜索，因此对目标函数和约束函数都没有特殊要求，使用范围较广。但是，这种方法的收敛速度较慢，特别当目标函数的维数较

22、高和约束条件的数目增多时，这一缺点尤为突出。另外，复合形法不能用于解具有等式约束的优化问题。常用无约束最优化方法的比较方法方法算法特点算法特点适用条件适用条件最速下降法属于间接法之一。方法简便，但要计算一阶偏导数，可靠性较好，能稳定地使函数下降，但收敛速度较慢，尤其在极值点附近尤为严重。适用于精度要求不高或用于对复杂函数寻找一个好的初始点。Newton法属于间接法之一。需计算一、二阶偏导数和Hesse矩阵的逆阵，准备工作量大，算法复杂，占用内存量大。此法具有二次收敛性，在一定条件下其收敛速度快，要求迭代点的Hesse矩阵必须非奇异且定型（正定或负定）。对初始点要求较高，可靠性较差。目标函数存在

23、一阶、二阶偏导数，且维数不宜太高。共轭方向法属于间接法之一。具有可靠性较好，占用内存少，收敛速度快。适用于维数较高的目标函数。变尺度法属于间接法之一。具有二次收敛性，收敛速度快。可靠性较好，只需计算一阶偏导数。对初始点要求不高，优于Newton法。因此，目前认为此法是最有效的方法之一，但需内存量大。适用于维数较高的目标函数（n=1050）且具有一阶偏导数。坐标轮换法最简单的直接法之一。只需计算函数值，无需求导，使用时准备工作量少，占用内存少。但计算效率低，可靠性差。用于维数较低（n5）或目标函数不易求导的情况。单纯形法此法简单，直观，属直接法之一。上机计算过程中占用内存少，规则单纯形法终止条件

24、简单，而不规则单纯形法终止条件复杂，应注意选择，才可能保证计算的可靠性。可用于维数较高的目标函数常用约束最优化方法的比较方法方法方法特点方法特点适用场合适用场合外点法将约束优化问题转化为一系列无约束优化问题。初始点可以任选，罚因子应取为单调递增数列。初始罚因子及递增系数应取适当较大值。可用于求解含有等式约束的中等维数的约束最优化问题。内点法将约束优化问题转化为一系列无约束优化问题。初始点应取为严格满足各个不等式约束的内点，障碍因子应取为单调递减的正数序列。初始障碍因子选择恰当与否对收敛速度和求解成败有较大影响。可用于求解只含有不等式约束的中等维数约束优化问题。混合罚函数法将约束优化问题转化为一系列无约束优化问题。用内点形式的混合罚函数法时，初始点及障碍因子的取法同上；用外点形式的混合罚函数法时，初始点可任选，罚因子取法同外点法相同。可用于求解既有等式又有不等式约束的中等维数的约束优化问题。约束坐标轮换法由可行点出发，分别沿各坐标轴方向以加步探索法进行搜索，使每个搜索点在可行域内，且使目标函数值下降。可用于求解只含有不等式约束，且维数较低（n5），目标函数的二次性较强的优化问题。复合形法在可行域内构造一个具有n个顶点的复合形，然后对复合形进行映射变化，逐次去掉目标函数值最大的顶点。可用于求解含不等式约束和边界约束的低维优化问题。