lxt第4章无约束优化方法课件.ppt

1、第四章第四章 无约束优化方法无约束优化方法1)1)坐标轮换法坐标轮换法;2)2)鲍威尔法鲍威尔法;3)3)梯度法梯度法;4)4)共轭梯度法共轭梯度法;5)5)牛顿法牛顿法;6)DFP6)DFP变尺度法变尺度法.4-1 概述概述 对于一个对于一个n n维目标函数，如果在没有任何维目标函数，如果在没有任何限制条件下寻求它的极小点，称无约束极限制条件下寻求它的极小点，称无约束极小化问题或无约束优化问题。数学上表达小化问题或无约束优化问题。数学上表达为为:Min F(X)XRn一）研究无约束优化方法的意义一）研究无约束优化方法的意义 一类有约束优化方法，往往能转化成无约束问题，一类有约束优化方法，往往

2、能转化成无约束问题，易于采用无约束优化方法求解易于采用无约束优化方法求解;有些问题可先作无约束问题求解，然后采用有约有些问题可先作无约束问题求解，然后采用有约束方法求出最优解。束方法求出最优解。二）解法分类二）解法分类无约束优化方法无约束优化方法 间接法间接法（解析法）（解析法）直接法直接法 梯度法梯度法 牛顿法牛顿法DFP变尺度法变尺度法 坐标轮换法坐标轮换法 鲍威尔法鲍威尔法确定搜索方向时用到一确定搜索方向时用到一阶或（和）二阶导数的阶或（和）二阶导数的方法。方法。其搜索方向直接其搜索方向直接取定或由计算目取定或由计算目标函数值所得的标函数值所得的信息来确定；信息来确定；4-2 坐标轮换法

3、 一、一、方法概述方法概述 坐标轮换法的基本构思是坐标轮换法的基本构思是将一个将一个 n n 维优化问题转化为维优化问题转化为依次沿依次沿 n n 个坐标方向反复进个坐标方向反复进行一维搜索问题。这种方法的行一维搜索问题。这种方法的实质是把实质是把n n维问题的求优过程维问题的求优过程转化为对每个变量逐次进行一转化为对每个变量逐次进行一维求优的循环过程。维求优的循环过程。二、迭代过程二、迭代过程 任选初始点任选初始点 搜索方向搜索方向以以X X(0)(0)为初始点，沿为初始点，沿e e1 1作正向试探性移步，步长作正向试探性移步，步长0 0 若试探成功，沿此方向一维搜索；否则，沿坐标的负若试探

4、成功，沿此方向一维搜索；否则，沿坐标的负方向试探。若正负方向试探均失败，则转入下一步。方向试探。若正负方向试探均失败，则转入下一步。TnTTTieeeS1,0,0,00,0,1,00,0,0,121TnxxxX)0()0(2)0(1)0(,沿沿e e2 2方向进行一维搜索。以此类推，进行完一轮一维搜索后得方向进行一维搜索。以此类推，进行完一轮一维搜索后得 以以 作为第二轮的初始点，重复步骤前作为第二轮的初始点，重复步骤前2 2步，得第二轮搜索的终点步，得第二轮搜索的终点 ，相继进行第三、第四轮等的搜索。，相继进行第三、第四轮等的搜索。如果从某轮的起始点出发，沿各个坐标轴的正负方向试探均失败，则

5、如果从某轮的起始点出发，沿各个坐标轴的正负方向试探均失败，则缩短初始试探步长。当初始步长缩得足够小，满足精度时，迭代终止。缩短初始试探步长。当初始步长缩得足够小，满足精度时，迭代终止。)1(nx)1(nx)2(nx 二、迭代过程二、迭代过程三、坐标轮换法流程图三、坐标轮换法流程图从从 出发沿出发沿 方向进行一维搜索得方向进行一维搜索得 ：1iXieiiiiieXX1)(iXFF 1ini 给给定定,0nX0XXn1iiFFXXn结束结束10kkXXn1k是否否是四、算法特点四、算法特点 如如:(:(1)1)等值线为椭圆等值线为椭圆,且长短轴分别平行于坐标轴时且长短轴分别平行于坐标轴时-高效高效

6、1x2xo(2(2)等值线为如图脊线时等值线为如图脊线时-无效无效1x2xo(3(3)一般情况一般情况-低效低效1 1）编程简单，容易掌握；）编程简单，容易掌握；2 2）收敛速度通常较低（）收敛速度通常较低（其有效性取决于目标其有效性取决于目标函数的性态函数的性态），仅适于低维的情况），仅适于低维的情况(n10)(n10)。4-3 鲍威尔法鲍威尔法 设设A A为为n n阶对称正定矩阵，若有两个阶对称正定矩阵，若有两个n n维矢量维矢量S1S1和和S2 S2，满足：满足：鲍威尔法是以共轭方向为基础的收敛较快的直接法之一。鲍威尔法是以共轭方向为基础的收敛较快的直接法之一。共轭方向法的概念共轭方向法

7、的概念则称矢量则称矢量S1S1和和S2S2对矩阵对矩阵A A共轭。共轭。共轭矢量的方向称共轭矢量的方向称共轭方向共轭方向。鲍威尔法 共轭方向与函数极小点的关系共轭方向与函数极小点的关系 设有一般二维二次正定函数设有一般二维二次正定函数 同心椭圆族。从同心椭圆族。从出发，沿出发，沿S S1 1方向作一维搜索，得最优点方向作一维搜索，得最优点X X1 1 （与椭圆相切）；再从另一初始点（与椭圆相切）；再从另一初始点 出发，沿出发，沿S S1 1方向作一维搜索，方向作一维搜索，连线的方向为连线的方向为S S2 2，则，则S S2 2必过椭圆族的中心，即必过椭圆族的中心，即X X*，且，且S S1 1

8、和和S S2 2必与必与A A正交。正交。其等值线是其等值线是沿沿S S1 1方向作一维搜索，得最优点方向作一维搜索，得最优点X X2 2（也与椭圆相切）。设（也与椭圆相切）。设X X1 1与与 X X2 2 4-2 Powell4-2 Powell法法2x3x1xo0X1e2e3e3 3）若目标函数为正定二次函数，）若目标函数为正定二次函数，n n轮结束后即可到达轮结束后即可到达最优点。最优点。2 2）每轮迭代产生一个新方向取代原来的第一方向，）每轮迭代产生一个新方向取代原来的第一方向，n n轮迭代后可产生轮迭代后可产生n n个彼此共轭的方向个彼此共轭的方向；nX1 1）开始采用坐标轴方向）

9、开始采用坐标轴方向；一）一）PowellPowell基本算法基本算法共轭方向法共轭方向法迭代过程二）二）PowellPowell法法（PowellPowell修正算法）修正算法）2x3x1xo0X2e3e1X 应用应用 PowellPowell基本算法时，若有一次搜索的最优步长为基本算法时，若有一次搜索的最优步长为0 0，且该方向被换掉，则该算法失效。且该方向被换掉，则该算法失效。1 1）问题的提出）问题的提出 2)Powell 2)Powell对基本算法的改进对基本算法的改进 在获得新方向构成新方向组时在获得新方向构成新方向组时,不是不是轮换地去掉原来的方向轮换地去掉原来的方向,而是经判别后

10、而是经判别后,在在n+1n+1个方向中留下最接近共轭的个方向中留下最接近共轭的n n个方个方向向.*根据根据PowellPowell条件判定是否需换方向；条件判定是否需换方向；如需换向，则换掉函数值下降量最大的方向如需换向，则换掉函数值下降量最大的方向.三）三）PowellPowell条件条件),()(01kXFF)(0)()(12kknknXXX),()(2knXFF)()(13knXFF),()(max,.,.2,1)()(1nmikikiXFXF)()()()(1kmkmXFXF23122132113)(21)(2(FFFFFFFFF如下述两不等式如下述两不等式同时成立则需换向，否则仍取

11、原方向组。同时成立则需换向，否则仍取原方向组。计算计算:（映射计算）（映射计算）)(1knX)(knX)(1kX)(0kXPQ大的方向的标号为目标函数值下降量最式中 m,四）更换方向的步骤四）更换方向的步骤nmmiiiSS,.,1,1,)(0)(1kknnXXS3 3）更换方向：）更换方向：2 2）构造新方向：）构造新方向：1 1）找出该轮迭代中目标函数值下降量最大的）找出该轮迭代中目标函数值下降量最大的方向方向（假定其标号为假定其标号为m m）；迭代步骤4-4 4-4 梯度法梯度法一）梯度方向一）梯度方向*可取最优步长或下降步长可取最优步长或下降步长二）基本思想二）基本思想 梯度方向是目标函

12、数上升最快的方梯度方向是目标函数上升最快的方向，负梯度方向则是最速下降方向；向，负梯度方向则是最速下降方向；)()()()()1(kkkkXFXX2 2）迭代公式迭代公式1 1）沿沿负梯度方向搜索负梯度方向搜索：)()()()(kkkgXFS kg三）终止判别条件三）终止判别条件给定给定 X0，K=0，X（K）=X0K=K+1X(k)=XX*=X（K）F*=F（X*）结结 束束NY计算计算)()(,kkgg)(kg 从从 出发出发，沿沿 搜索得搜索得)(kX)(kg)()()(kkkgXX*“最速下降性最速下降性”只只是迭代点邻域的局部是迭代点邻域的局部性质。从全局看，并性质。从全局看，并非最

13、速下降方向。非最速下降方向。四四.迭代步骤迭代步骤梯度法特点：梯度法每次迭代都是沿迭代点函数值下降最快的方向搜索，因梯度法每次迭代都是沿迭代点函数值下降最快的方向搜索，因而梯度法而梯度法又称最速下降法又称最速下降法。这种方法搜索路线常常很曲折，收敛速度较慢。对于等值线为这种方法搜索路线常常很曲折，收敛速度较慢。对于等值线为圆的优化问题，梯度法一次迭代就可以达到极小点；当等值线圆的优化问题，梯度法一次迭代就可以达到极小点；当等值线不是圆，负梯度方向不再指向圆心，迭代次数增加，偏心越严不是圆，负梯度方向不再指向圆心，迭代次数增加，偏心越严重，迭代次数越多，形成重，迭代次数越多，形成锯齿现象锯齿现象

14、。且在搜索开始时步长越大，。且在搜索开始时步长越大，愈接近极小点步长愈小，最后收敛的速度极其缓慢。愈接近极小点步长愈小，最后收敛的速度极其缓慢。因此，对于比较复杂的优化问题，梯度法不具有实用价值。但因此，对于比较复杂的优化问题，梯度法不具有实用价值。但由于梯度法在迭代开始时函数值下降得较快，由于梯度法在迭代开始时函数值下降得较快，因此常用于其他因此常用于其他方法中作初始迭代法。方法中作初始迭代法。梯度法的优点是迭代过程简单，对初始点要求不高，虽要计算梯度法的优点是迭代过程简单，对初始点要求不高，虽要计算导数，但只要求一阶偏导，存储单元较少。导数，但只要求一阶偏导，存储单元较少。4-5 4-5

15、共轭梯度法共轭梯度法)1(1)2()2()(SXFS第二方向：第二方向：)()1()1(XFS第一方向：第一方向：二二.共轭方向的构成共轭方向的构成*利于突破函数的非二次性利于突破函数的非二次性;每轮搜索方向为一组共轭方向每轮搜索方向为一组共轭方向,但第一方向为负梯度方向但第一方向为负梯度方向.一一.基本思路基本思路)1()1()1()2(SXX*可表示为两个负梯度方向的线性组合可表示为两个负梯度方向的线性组合。)2(S)1(X)2(S)2(X)1(S)()2(XF2)(2)1()()(kkkXFXF)()1()1()(kkkkSXFS，以后新方向均按下述迭代公式产生以后新方向均按下述迭代公式

16、产生：2)1(2)2()1()1()2()1()1()1()2()2(1)()()()()()()()(XFXFXFXFXFXFXFXFTT因而因而，0)1()2(ASST因为因为（A A是二次函数的是二次函数的Hessian Hessian 矩阵矩阵）CXBAXXXFTT21)(BAXXF)(二次函数二次函数其梯度为其梯度为故有故有0)()1(1)1(1)2(ASSXFT)1()1()1()2(1)(ASSASXFTT)1()1()1()2(SXX)1()1()1()2()1()2()()()(ASXXAXFXF故有故有又又0)()2()1(XFST（正交正交）刘 惟 信 用 数刘 惟 信

17、用 数学归纳法对此法学归纳法对此法的共轭性作出过的共轭性作出过证明。证明。K n给定给定X0,n,K=1,X(K)=X0S(K)=-F(X(K)从从X(K)始始，沿沿S(K)进行一维搜索得进行一维搜索得X(K+1)K=K+1是是是是否否否否计算计算)(),()1()1(KKXFXF )()1(KXF结结 束束)()1()1(KKXFFXX)1(0KXX)()1()1(2)()1()()()(KKKKKKKSXFSXFXF重置负梯度方向重置负梯度方向三三.迭代步骤迭代步骤四四.共轭梯度法的特点共轭梯度法的特点1.1.为共轭方向法为共轭方向法,具有二次收敛性具有二次收敛性;2.2.算法简单算法简单

18、,编程容易编程容易,存储量小存储量小;3.3.需用到一阶导数需用到一阶导数.4-6 4-6 牛顿法牛顿法*鲍威尔法需迭代鲍威尔法需迭代 (n+1)n(n+1)n 次才能到达二次函数的极小点；共轭梯度法次才能到达二次函数的极小点；共轭梯度法则需迭代则需迭代n n次，能否更快到达二次函数的极小点？次，能否更快到达二次函数的极小点？一一.原始牛顿法原始牛顿法一）基本思路一）基本思路 牛顿法是梯度法的进一步发展，其基本思想是在求牛顿法是梯度法的进一步发展，其基本思想是在求目标函数目标函数f(X)f(X)的极小值时，先将的极小值时，先将f(X)f(X)在点在点X Xk k附近作泰勒附近作泰勒展开，取其二

19、次近似函数式，然后求出这个二次函数的展开，取其二次近似函数式，然后求出这个二次函数的极小点，并以该极小点作为原目标函数的近似极小点；极小点，并以该极小点作为原目标函数的近似极小点；若此值不满足精度要求，则以此近似极小点作为下一次若此值不满足精度要求，则以此近似极小点作为下一次迭代的初始点，继续以上过程，迭代下去，直至所求出迭代的初始点，继续以上过程，迭代下去，直至所求出的近似极小点满足精度要求为止。的近似极小点满足精度要求为止。kkkkgHXXX1)()1(0)()(*kkkXXHg（牛顿方向牛顿方向）kkkgHS1)(1）迭代方向迭代方向：*二）原始牛顿法的迭代公式二）原始牛顿法的迭代公式原

20、函数原函数:)(XF)()()()(21)()(kkTkkTkkXHXXgXFX近似二次函数近似二次函数:0)()(kkkXHgX令令1)(k2）步长因子步长因子：CXBAXXXFTT21)(BAXXF)(二）阻尼牛顿法二）阻尼牛顿法)()()(1)()()()1(kkkkkXfXHXX*具有二次收敛性，但用到二阶导数矩阵求逆具有二次收敛性，但用到二阶导数矩阵求逆仍取牛顿方向，但改用最优步长因子：仍取牛顿方向，但改用最优步长因子：因因F(XF(X）不一定是二次函数，基本牛顿法的步长因）不一定是二次函数，基本牛顿法的步长因子恒为子恒为1 1，有时会导致迭代发散而失效。，有时会导致迭代发散而失效。

21、1.1.问题的提出问题的提出2.2.改进方法改进方法在在H Hk k正定时可保证收敛性。正定时可保证收敛性。K=0，X（K）=X0K=K+1NX*=X（K）F*=F（X*）结结 束束Y3.3.阻尼牛顿法的迭代步骤阻尼牛顿法的迭代步骤kg计算计算kkgg,计算计算 ，KKKgHS1)(1 KH由由 出发出发，沿沿 方向搜索得方向搜索得)()()()1(KKKKSXX)(KX)(KS给定给定 X0，牛顿法的特点牛顿法的特点 牛顿法不仅利用了函数的一阶导数信息，还利牛顿法不仅利用了函数的一阶导数信息，还利用了函数的二阶导数信息，故其收敛速度较梯度用了函数的二阶导数信息，故其收敛速度较梯度法快很多。但

22、是牛顿法要计算黑塞矩阵及其逆矩法快很多。但是牛顿法要计算黑塞矩阵及其逆矩阵，计算量储存量较大，且都以维数阵，计算量储存量较大，且都以维数n2比例增加，比例增加，维数高时这个问题更加突出。此外，若黑塞矩阵维数高时这个问题更加突出。此外，若黑塞矩阵是奇异时，其逆矩阵不存在，这种方法就根本不是奇异时，其逆矩阵不存在，这种方法就根本不能应用能应用4-7 DFP4-7 DFP变尺度法变尺度法)()()()()1(kkkkXFEXX)()()(1)()()()1(kkkkkXFXHXX能否克服各自的缺点，综合发挥其优点？能否克服各自的缺点，综合发挥其优点？2 2）阻尼牛顿法）阻尼牛顿法1 1）梯度法）梯度

23、法一）问题的提出一）问题的提出由由Davidan、Fletcher、Powell共同提出。共同提出。*简单，开始时目标函数值下降较快，但越来越慢。简单，开始时目标函数值下降较快，但越来越慢。*目标函数值在最优点附近时收敛快，但要用到二目标函数值在最优点附近时收敛快，但要用到二阶导数和矩阵求逆。阶导数和矩阵求逆。二）基本思路二）基本思路)()()()()1(kkkkkXFAXX1kkHA2 2）迭代终了迭代终了，具有二阶收敛性具有二阶收敛性。EAkk,0*1 1）当当 和梯度法一样，便于突破函数的非二次性和梯度法一样，便于突破函数的非二次性；式中，式中，1.1.A Ak k 构造矩阵构造矩阵（在

24、迭代中产生，不用求导和作矩阵求逆）（在迭代中产生，不用求导和作矩阵求逆）迭代公式：迭代公式：)()()()()1(kkkkXFEXX)()()(1)()()()1(kkkkkXFXHXX)()()(kkkXFAS-拟牛顿方向拟牛顿方向2.三）构造矩阵应满足的条件三）构造矩阵应满足的条件kA1）应为正定对称矩阵；应为正定对称矩阵；kA(1)应为对称矩阵应为对称矩阵；E E和和 均为对称矩阵均为对称矩阵1KHkA(2)应为正定矩阵应为正定矩阵；因为因为 应使应使 为函数下降方向为函数下降方向,即即 与与 的夹角应小于的夹角应小于900:kA)(kS)(kSkg0)(kTkSg0kkTkgAg0kk

25、TkgAg二次型正定二次型正定kA1kH2）能逼近能逼近以近似二次函数的梯度作为下一迭代点处的梯度以近似二次函数的梯度作为下一迭代点处的梯度:)()()()(21)()(kkTkkTkkXHXXgXFX其梯度其梯度)(kkkXHgg)(1kkkkXHggkkkkkkgHggHX111)()(1kA1kH用用 代替代替 ,得得kkkgAX1)(拟牛顿条件拟牛顿条件kky1kA四四.的构造方法的构造方法kkkAAA1用递推方法构造用递推方法构造kkkkkkgAAgAX)(1)(于是有于是有kA关键是确定关键是确定校正矩阵校正矩阵kkkkkgAXgA)(1)再令再令TkkkkkTkkkkgAgAXX

26、A)()(2)代入代入(1):kkkkkTkkkkkTkkkgAXgAggAgXX)()()(,1)(kTkkgX.1kkTkkgAg两边对比得两边对比得:),/(1)(kTkkgX)./(1kkTkkgAg回代到回代到(2)(2)得得:kkTkTkkkkkTkTkkkgAggAgAgXXXA)()()(3)待定常数待定常数可保证可保证AK的对称性的对称性963642321321321五五.迭代步骤迭代步骤,0nX给定)(),(,00XFgXFFXX1kgASEA,XSX搜索得极小点沿始从,gg,计算g是是是是否否否否nk)(,XFFX输出结束 XX1 kkXXgggASAAAAgggXXX,

27、.,计算因计算机的舍入误因计算机的舍入误差，构造矩阵的正差，构造矩阵的正定性可能遭到破坏，定性可能遭到破坏，故作故作n n次后重置单次后重置单位矩阵。位矩阵。4-8 无约束优化方法的评价准则无约束优化方法的评价准则一）可靠性一）可靠性 在满足合理精度要求的情况下、在一定时间内对在满足合理精度要求的情况下、在一定时间内对各类问题解题的成功率各类问题解题的成功率。（梯度法较好，牛顿法较差，（梯度法较好，牛顿法较差，其余居中）其余居中）二）有效性（收敛性）二）有效性（收敛性）在同一题目、同样精度、同一初始点情况下比较在同一题目、同样精度、同一初始点情况下比较。（具有二次收敛性的方法较好）（具有二次收敛性的方法较好）三）简便性三）简便性 比较准备工作量和存储单元。（比较准备工作量和存储单元。（用到二阶导数及用到二阶导数及矩阵求逆的方法较差矩阵求逆的方法较差）