04 无约束优化方法.ppt

《04 无约束优化方法.ppt》由会员分享，可在线阅读，更多相关《04 无约束优化方法.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1第四章无约束优化方法无约束优化方法24.1 4.1 概概 述述v尽管工程实际中的问题几乎都是约束优化问题，但尽管工程实际中的问题几乎都是约束优化问题，但无约束优化方法仍是优化方法中最基本的组成部份，无约束优化方法仍是优化方法中最基本的组成部份，因为解约束问题的一些有效方法就是将约束问题转因为解约束问题的一些有效方法就是将约束问题转化为无约束问题求解。何况还有很多问题本身就是化为无约束问题求解。何况还有很多问题本身就是无约束问题，人们对无约束优化方法研究也比较成无约束问题，人们对无约束优化方法研究也比较成熟。熟。v解无约束优化问题的一类方法是需利用函数的一阶解无约束优化问题的一类方法是需利用函

2、数的一阶或二阶导数，它们要充分利用函数的解析式子故称或二阶导数，它们要充分利用函数的解析式子故称为为解析法解析法(间接法间接法)。另一类方法在迭代过程中只需。另一类方法在迭代过程中只需计算函数值，故称计算函数值，故称直接法直接法。相对直接法而言解析法。相对直接法而言解析法又称间接法。因为解析法充分利用了函数的解析性又称间接法。因为解析法充分利用了函数的解析性质，所以它们的收敛速度多数比直接法快，但可靠质，所以它们的收敛速度多数比直接法快，但可靠性一般较低。性一般较低。34.2 4.2 最速下降法最速下降法(Gradient Method)一一.基本思想基本思想 梯度方向是函数值变化率最大的方向

3、：沿着梯度方向函数值梯度方向是函数值变化率最大的方向：沿着梯度方向函数值上升最快上升最快;沿负梯度方向函数值下降最快。用负梯度方向作为搜沿负梯度方向函数值下降最快。用负梯度方向作为搜索的方向，即索的方向，即:或用单位负梯度矢量来表示或用单位负梯度矢量来表示 这种方法是用函数变化率最大的方向作为搜索方向，又称最这种方法是用函数变化率最大的方向作为搜索方向，又称最速下降法。速下降法。二、迭代公式二、迭代公式4 或或 式中，步长式中，步长k可可以任选，只要保证以任选，只要保证f(X(k+1)f(X(k)。通常通常是沿负梯度方向进行一维搜索，找出其最优点作为下一步的迭是沿负梯度方向进行一维搜索，找出其

4、最优点作为下一步的迭代点。即：代点。即：三、迭代过程及程序框图三、迭代过程及程序框图 四、练习四、练习 用梯度法求解用梯度法求解f(X)=)=x1 12 2+2+2x2 22 2的极小点的极小点 设初始点设初始点X(0)=4,4T 要求迭代一次要求迭代一次,并验证相邻两次迭代的搜索方向互相垂直。并验证相邻两次迭代的搜索方向互相垂直。5 五、梯度法讨论五、梯度法讨论 优点：优点：程序简单，每次迭代所需的计算量小，贮存量也少；程序简单，每次迭代所需的计算量小，贮存量也少；对初始点要求不高，即使从一个不太好的初始点出发，往往也对初始点要求不高，即使从一个不太好的初始点出发，往往也能收敛到局部极小点。

5、能收敛到局部极小点。缺点：收敛的速度慢。缺点：收敛的速度慢。原因：最速下降是函数值原因：最速下降是函数值在某一点的变化率而言，是在某一点的变化率而言，是一个一个局部的性质局部的性质，从全局来，从全局来看并不是最速下降方向看并不是最速下降方向。因此梯度法的搜索路线呈直因此梯度法的搜索路线呈直角锯齿形状，所得到的搜索点为绕道逼近最优点的，除非目标角锯齿形状，所得到的搜索点为绕道逼近最优点的，除非目标函数是圆函数是圆。s64.3 4.3 牛顿类法牛顿类法(Newtons Method)一一.迭代公式及特点迭代公式及特点 1.1.迭代公式迭代公式 f(X)在迭代点在迭代点X(k)具有一阶、二阶的连续偏

6、导数，则可将其具有一阶、二阶的连续偏导数，则可将其展开成展开成Taylor级数，并略去高于二次的项，得到：级数，并略去高于二次的项，得到：二次函数二次函数(X)的极值点的极值点 如果将如果将X作为一个逼近点作为一个逼近点X(k+1),牛顿法的一般迭代公式牛顿法的一般迭代公式 式中式中 如果如果f(X)是正定二次函数，则是正定二次函数，则H(X)是个常数矩阵，逼近式是个常数矩阵，逼近式X(k)=X*是准确的，由是准确的，由X(k)出发只要迭代一次可得到极小点。出发只要迭代一次可得到极小点。7 2.2.特点特点 (1).(1).收敛的速度快，即使到了收敛的速度快，即使到了最优点邻域时也很快收敛于函

7、数最优点邻域时也很快收敛于函数的局部最优点。的局部最优点。(2).(2).采用定步长迭代，因而采用定步长迭代，因而就不能保证每次迭代中目标函就不能保证每次迭代中目标函数是下降的。数是下降的。原因：原因：(X)仅为目标函数仅为目标函数f(X)在在X(k)点附近的近似表达点附近的近似表达式。式。X(k+1)点是点是(X)在牛顿方在牛顿方向上的极小点，而非原函数的向上的极小点，而非原函数的极小点。极小点。解决办法：阻尼牛顿法。解决办法：阻尼牛顿法。123450123-1-2FCDABE8 二二.阻尼牛顿法阻尼牛顿法 1.1.迭代公式迭代公式 沿牛顿方向沿牛顿方向-H(X(k)-1f(X(k)作一维搜

8、索作一维搜索,迭代公式：迭代公式：其中其中 k使使 在在f(X)的的Hessian矩阵矩阵H(X(k)处处正定处处正定的情况下，阻尼牛顿的情况下，阻尼牛顿法能保证每次迭代函数值有所下降。即保持了牛顿法收敛快的法能保证每次迭代函数值有所下降。即保持了牛顿法收敛快的特性，又不要求初始点选得很好。特性，又不要求初始点选得很好。2.2.程序框图程序框图 三、有关牛顿法的讨论三、有关牛顿法的讨论 1.1.不能保证每次迭代函数值都下降。不能保证每次迭代函数值都下降。原因：原因：HessianHessian矩阵不定。矩阵不定。9 2.2.若若HessianHessian矩阵奇异矩阵奇异,其逆阵不存在其逆阵不

9、存在,就不能构成牛顿方就不能构成牛顿方向，迭代无法进行。向，迭代无法进行。3.3.构造牛顿方向较困难。构造牛顿方向较困难。是否能找到另一种更好的方法？是否能找到另一种更好的方法？a.能像梯度法那样，只需计算目标函数的一阶导数，对初始能像梯度法那样，只需计算目标函数的一阶导数，对初始点的要求不高，能较好的突破函数的非二次性而迅速趋近于极点的要求不高，能较好的突破函数的非二次性而迅速趋近于极值点；值点；b.同时又像牛顿法那样，一但迭代点进入极值点的邻近区域同时又像牛顿法那样，一但迭代点进入极值点的邻近区域时很快地收敛于最优点。时很快地收敛于最优点。104.4 4.4 坐标轮换法坐标轮换法(Cycl

10、ic Coordinate Method)一一.基本思想基本思想 降维的思想，将一个降维的思想，将一个n维问题转化为一系列的一维优化问题维问题转化为一系列的一维优化问题来求解。每次将来求解。每次将n-1-1个变量固定，只对一个变量作一维搜索。个变量固定，只对一个变量作一维搜索。进行一维搜索找到进行一维搜索找到X1 1(1)(1)进行一维搜索找到进行一维搜索找到X2 2(1)(1)进行一维搜索找到进行一维搜索找到Xn(1)(1)到此完成一轮迭代，到此完成一轮迭代，X的上角标表示迭代的的上角标表示迭代的轮次轮次，下角标表，下角标表示坐标轴的示坐标轴的序号序号。每次都是以前一次搜索的终点作本次一维搜

11、。每次都是以前一次搜索的终点作本次一维搜索的起点，一轮迭代完后又重头开始直至收敛，故此法又称变索的起点，一轮迭代完后又重头开始直至收敛，故此法又称变量轮换法量轮换法(Alternating Variable Method)。二、步长的确定二、步长的确定 1 1、随机选取法，保证函数值下降。、随机选取法，保证函数值下降。11 2 2、最优步长、最优步长 Xi=Xi-1+iEi 3 3、加速步长法、加速步长法 在每次一维搜索中在每次一维搜索中,都是以都是以=0开始开始,随后在函数值下降的情况下随后在函数值下降的情况下220,4,40,倍增的速度加大步长，直至函数值不再下倍增的速度加大步长，直至函数

12、值不再下降，取其前步长为最终步长。降，取其前步长为最终步长。12 三三.迭代过程及框图迭代过程及框图13 四四.坐标轮换法的讨论坐标轮换法的讨论 1 1、坐标轮换法具有程序简单，易于掌握的优点，但它的计、坐标轮换法具有程序简单，易于掌握的优点，但它的计算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方算效率较低，因此它虽然步步在登高，但相当于沿两个垂直方向在爬山，路途迂迴曲折，收敛很慢，因此它适用于维数较低向在爬山，路途迂迴曲折，收敛很慢，因此它适用于维数较低(一般一般n10)n10)的目标函数求优的目标函数求优。2 2、有、有“脊线脊线”的目标函数等值线的情形的目标函数等值线的情形,沿坐

13、标轴方向函数值沿坐标轴方向函数值不一定下降。不一定下降。0pA脊线脊线14 五、练习五、练习 用最优步长法求解用最优步长法求解 f(X)=()=(x1 1-2)-2)4 4+(+(x1 1-2-2x2 2)2 2的极小点。的极小点。初始点初始点X(0)=0,3T，要求迭代一轮。要求迭代一轮。请注意沿坐标轴移动的方向。请注意沿坐标轴移动的方向。15 四四.模式搜索法模式搜索法(Pattern Search Method&Hooke-Jeeves)模式搜索法是对坐标轮换法的改进。由两类移动组成：模式搜索法是对坐标轮换法的改进。由两类移动组成：探测性移动探测性移动探测一个有利的方向探测一个有利的方向

14、 模式移动模式移动循有利的方向加大步长移动循有利的方向加大步长移动探测性移动的起点为参考点，用探测性移动的起点为参考点，用R0,R1,表示，其终点称为基表示，其终点称为基点，用点，用B0,B1,表示。模式移动则以基点开始，而以参考点为表示。模式移动则以基点开始，而以参考点为终点。两种移动交替进行，即：终点。两种移动交替进行，即：B0R0B1R1B2BiRiBi+1Ri+1通常先取一点为整个过程的起始点，记为通常先取一点为整个过程的起始点，记为B0R0，即它既是一个参考点又是一个基点。，即它既是一个参考点又是一个基点。16174.5 4.5 鲍威尔法鲍威尔法(Powells Method)一一.

15、共轭方向的概念共轭方向的概念(Conjugate Direction)对于具有正定矩阵对于具有正定矩阵H的二元二次函数的二元二次函数依次沿依次沿s(0)(0)和和s(1)(1)这两个方向这两个方向搜索即可到达无约束搜索即可到达无约束极值点极值点X*。18 1.定义：设定义：设A为为n阶实对称正定矩阵，若有两阶实对称正定矩阵，若有两个个n维矢量维矢量s1和和s2，满足，满足s1TAs2=0,=0,则称矢量则称矢量s1和和s2对矩阵对矩阵A共轭，共轭矢量的方向称为共轭方共轭，共轭矢量的方向称为共轭方向。向。如果如果A=I(单位阵单位阵)，就成为，就成为s1Ts2=0=0，s1和和s2方方向正交，即

16、与单位阵共轭的方向是正交方向，向正交，即与单位阵共轭的方向是正交方向，所以正交方向可以说是共轭方向的一个特例。所以正交方向可以说是共轭方向的一个特例。但但正交和共轭不能混为一谈正交和共轭不能混为一谈，有的正交不共，有的正交不共轭，有的共轭不正交。轭，有的共轭不正交。1920 2.2.正定二次函数的特点正定二次函数的特点 (1)(1)正定二次二元函数的等值线是椭圆线簇正定二次二元函数的等值线是椭圆线簇,椭圆线簇的中心椭圆线簇的中心即目标函数的极值点。即目标函数的极值点。(2)(2)过同心椭圆线簇中心作任意直线过同心椭圆线簇中心作任意直线,此直线与诸椭圆交点处此直线与诸椭圆交点处的切线相互平行。的

17、切线相互平行。反之过两平行线与椭圆切点反之过两平行线与椭圆切点X(a)和和X(b)的连线必通过椭圆的中心。的连线必通过椭圆的中心。因此因此只要沿方向只要沿方向X(a)X(b)进行一维搜索，进行一维搜索，就能找出函数的极小点。就能找出函数的极小点。而且平行线的方向而且平行线的方向S1和切点连线和切点连线的方向的方向S2为共轭方向为共轭方向,即满足：即满足：s1TAs2=0=0 S10S221 3.3.结论结论 正定二次二元函数依次沿两个互相共轭的方向作一正定二次二元函数依次沿两个互相共轭的方向作一维搜索，就能得到极小点。推广到正定二次维搜索，就能得到极小点。推广到正定二次n元函数元函数中去中去,

18、可得出只要依次沿可得出只要依次沿n个互相共轭的方向进行一维个互相共轭的方向进行一维搜索就可得到极小点。如果一个算法的搜索方向是互搜索就可得到极小点。如果一个算法的搜索方向是互相共轭的，就称为共轭方向法。相共轭的，就称为共轭方向法。22 二、基本思想二、基本思想 本质就是共轭方向法，只不过不求导数而已，故又本质就是共轭方向法，只不过不求导数而已，故又称不求导数的共轭方向法。称不求导数的共轭方向法。Powell法先沿着法先沿着n个方向作一维搜索后，把初始点个方向作一维搜索后，把初始点和终点连结起来产生一个新方向，把原来的第一个方和终点连结起来产生一个新方向，把原来的第一个方向去掉，把新方向加在最后

19、，就构成一组共轭方向，向去掉，把新方向加在最后，就构成一组共轭方向，继续进行下去。也可以这样看与模式搜索的关系，假继续进行下去。也可以这样看与模式搜索的关系，假设沿设沿n个方向进行一维搜索后，又在相应的模式方向个方向进行一维搜索后，又在相应的模式方向进行了一维搜索，考虑模式方向可能比坐标轴方向进行了一维搜索，考虑模式方向可能比坐标轴方向好，所以下一次就去掉好，所以下一次就去掉一个坐标轴方向一个坐标轴方向而加进模式方而加进模式方向。向。23 二、迭代过程二、迭代过程 以二维问题为例：以二维问题为例：24 三、三、Powell法存在的问题法存在的问题 (1)(1)、对于非二次函数，用、对于非二次函

20、数，用Taylor展开只有接近中心处是椭展开只有接近中心处是椭圆，故收敛就不是二次收敛，即圆，故收敛就不是二次收敛，即n次不一定达到最优点。次不一定达到最优点。(2)(2)、共轭方向一定是线性无关的。出现线性相关或近似线、共轭方向一定是线性无关的。出现线性相关或近似线性相关，使一些方向漏掉，降维，称为退化，故对性相关，使一些方向漏掉，降维，称为退化，故对Powell法进法进行修改，即不一定固定每次去掉的都是第一个方向，而是行修改，即不一定固定每次去掉的都是第一个方向，而是“哪哪个方向好就朝哪个方向走个方向好就朝哪个方向走”，从而避免出现线性相关的，从而避免出现线性相关的“退退化化”现象。现象。

21、(3)(3)、修正方法、修正方法 增加模式移动：增加模式移动：X0k、Xnk、Xn+1k分别称为一轮迭代的起点、终点和反射点。分别称为一轮迭代的起点、终点和反射点。其函数值分别记为：其函数值分别记为：25 同时，计算各中间点处的函数值，并记为：同时，计算各中间点处的函数值，并记为：计算计算n个函数值之差。记作：个函数值之差。记作：取取 是否要对原方向组进行替换的判别条件：是否要对原方向组进行替换的判别条件：若满足，则进行替换；若不满足，则下轮仍用原方向组。若满足，则进行替换；若不满足，则下轮仍用原方向组。26对于对于n维问题维问题27 四、四、迭代框图迭代框图满足：满足：下一轮不下一轮不替换方

22、向替换方向不满足：不满足：下一轮下一轮替换方向替换方向28五、练习五、练习用鲍威尔法求解无约束极值问题用鲍威尔法求解无约束极值问题给定给定迭代一轮，求出下一轮的初始点和迭代方向。迭代一轮，求出下一轮的初始点和迭代方向。六、编程实现六、编程实现Powell算法算法29无约束优化方法无约束优化方法特点及应用范围特点及应用范围坐坐标轮换标轮换法法（变变量量轮换轮换法或降法或降维维法）法）不需求不需求导导数，程序数，程序编编制制简单简单，占用存，占用存贮贮量小，但量小，但计计算效率低，可靠算效率低，可靠性也差，当目性也差，当目标标函数的等函数的等值线值线具有脊具有脊线线形形态时态时，可能失，可能失败败

23、。适用。适用于于n10n10的小型的小型优优化化问题问题，当，当函数等函数等值线为圆值线为圆或或长长短短轴轴都平行于坐都平行于坐标轴标轴的的椭圆椭圆时时此法很有效。此法很有效。PowellPowell法法（方向加速法）（方向加速法）属于共属于共轭轭方向，具有二次收方向，具有二次收敛敛性，收性，收敛敛速度速度较较快，可靠性也快，可靠性也较较好，好，具有直接法的共同具有直接法的共同优优点，一般点，一般认为认为是直接法中最有效的方法，存是直接法中最有效的方法，存贮贮量少，程序量少，程序编编制复制复杂杂一些。适用于中小型一些。适用于中小型优优化化问题问题，但，但对对于多于多维问题维问题收收敛敛速度速度

24、较较慢。慢。单纯单纯形法形法 属直接法，属直接法，这类这类方法甚至适用于方法甚至适用于未知目未知目标标函数的数学表达式而只知函数的数学表达式而只知道它的具体算法道它的具体算法的情况，程序的情况，程序简单简单，收，收敛敛快，效果好，适用于中快，效果好，适用于中小型小型问题问题。梯度法（最速下降法）梯度法（最速下降法）属属间间接法，要接法，要计计算一算一阶导阶导数，方法数，方法简单简单，可靠性，可靠性较较好，能好，能稳稳定的使定的使函数函数值值下降。下降。对对初始点要求不高。缺点是初始几步收初始点要求不高。缺点是初始几步收敛敛快，后面快，后面收收敛缓敛缓慢，愈靠近极慢，愈靠近极值值点愈慢，适用于精

25、度要求不高或用于复点愈慢，适用于精度要求不高或用于复杂杂函数函数寻寻找一个好的初始点。找一个好的初始点。牛牛顿顿法（法（NewtonNewton）法）法（二（二阶阶梯度法）梯度法）当初始点当初始点选选得合适是目前算法中得合适是目前算法中收收敛敛最快的一种最快的一种（尢其（尢其对对二次函数）二次函数），但当初始点，但当初始点选选得不当会影响收得不当会影响收敛导敛导致失致失败败。需。需计计算一、二算一、二阶阶偏偏导导数及数及HessainHessain矩矩阵阵的逆的逆阵阵，准，准备备工作量大，程序工作量大，程序较较复复杂杂，占存，占存贮贮量大，故当函数量大，故当函数变变量量较较多和因次多和因次较较高高时时不宜采用此法。不宜采用此法。修正牛修正牛顿顿法（广法（广义义牛牛顿顿法法或阻尼牛或阻尼牛顿顿法）法）即使初始点即使初始点选择选择不当，此法亦会成功，其它特点与牛不当，此法亦会成功，其它特点与牛顿顿法相同。法相同。30vMatlab优化工具箱优化工具箱vFminsearch:用的算法是单纯形搜索法。用的算法是单纯形搜索法。vFminunc:不提供梯度矩阵采用线性搜索法，否则信不提供梯度矩阵采用线性搜索法，否则信赖域法。赖域法。313233