第四章无约束优化方法.

1第四章常用的无约束优化方法4.1坐标轮换法4.2鲍威尔(Powell)法4.3梯度法4.5牛顿法4.6DFP变尺度法4.7BFGS变尺度法无约束优化方法的评价准则及选用2若存在则称X*点为无约束最优点，F(X)为无约束最优值。直接搜索法：坐标轮换法、鲍威尔法方法间接法：梯度法、牛顿法、变尺度法直接搜索法：只需进行函数值的计算与比较来确定迭代方向和步长间接法：利用函数的一阶或二阶偏导数矩阵来确定迭代方向和步长**,min()()XFXFX使对于无约束优化问题:12min...TnnFXXxxxR34.1坐标轮换法2xo1x*X基本思想：把一个n维无约束最优化问题转化为依次沿n个坐标轴方向的一维最优化问题。即迭代方向依次为:,1,2,...,iein12100...0010...0............000...1TTTneee(0)X(1)0X(1)1X(1)2X(2)0X(2)1X(2)2X(3)0X第一轮:任取一初始点X(0)(0)X(1)0X1210,01TTee(1)(1)(1)1011XXe(1)1一维搜索求得(1)1X(1)(1)(1)2122XXe(1)2一维搜索求得(1)2X第二轮:(1)(2)20XX(2)(2)(2)1011XXe(2)(2)(2)2122XXe4终止准则:()()0kknXX*()knXX2xo1x*X(0)X(1)0X(1)1X(1)2X(2)0X(2)1X(2)2X(3)0X上式点距准则中的两点应是一轮迭代的始点与终点利用一维优化方法确定沿该方向上具有最小目标函数值的步长，即:min{F(X(k)+αS(k))}=F(X(k)+α(k)S(k))迭代步长α的确定:5坐标轮换法的流程图()kiX()knX()knX()kiX()1kiX6坐标轮换法的特点:具有程序结构简单，易于掌握等优点。但收敛慢，适用于n10的低维优化问题。另收敛速度与等值线的形状有关7例题4.1用坐标轮换法求目标函数的无约束最优解。给定初始点精度要求ε=0.122121212()10460FXxxxxxx(0)00,TX解：作第一轮迭代计算。沿e1方向进行一维搜索按最优步长原则确定步长α1，即极小化此问题可用某种一维优化方法求出α1。在这里，我们暂且借用微分学求导解出，令其一阶导数为零，α1=5)1(1x以为新起点，沿e2方向一维搜索以最优步长原则确定α2，即极小化得α2=4.5，对于第一轮按终止条件检验8例题4.1对于第一轮按终止条件检验:继续第二轮迭代计算。以下各轮的计算结果列于表4.1。9例题4.1计算五轮后有故近似优化解为F*＝F(x*)=7.9502522121212()10460FXxxxxxx10例题4.1用解析法验证22121212()10460FXxxxxxx12212100()240xxFXxx解:令*86X*1112212221()312xxxxxxxxFFHXFF正定114.2鲍威尔(Powell)法鲍威尔法是直接搜索法中一个十分有效的算法。该算法是沿着逐步产生的共轭方向进行搜索的，因此本质上是一种共轭方向法，鲍威尔法的收敛速率较快。以共轭方向作为搜索方向，不只限于鲍威尔法，也用于其他一些较为有效的方法，可以统称为共轭方向法。因此，共轭方向的概念在优化方法研究中占有重要的地位。共轭方向在最优化问题中的应用是基于其具有一个重要性质，即：设S1、S2、…、Sn是关于A的n个互相共轭的向量，则对于求正定二次函数的极小点，从任意初始点出发，依次沿Si（i=1，2，…，n)方向进行一维最优化搜索，至多n步便可以收敛到极小点．1()2TTFXcbXXAX122.5关于优化方法中搜寻方向的理论基础2.5.2共轭方向(见第二章)一、共轭方向的基本概念若有两个n维矢量S1、S2，对n×n阶对称正定矩阵A能满足:T12SAS=0称n维空间矢量S1与S2对A共轭共轭矢量所代表的方向称为共轭方向。正交:可以看作是共轭的特例121200TTSSSES例:(1)122111,,1211ASS12211110,121TSAS1211101TSS共轭并正交13例:(2)122111,,1202ASS12211100,122TSAS12110102TSS共轭但不正交设A为n×n阶实对称正定矩阵，有一组非零的n维矢量S1、S2、…、Sq，若满足i≠j则称矢量系Si(i＝1，2，…，q≤n)对于矩阵A共轭0jTiASS14以二维函数为例:二维正定二次函数具有两个重要特性：1）二维正定二次函数的等值线是同心的椭圆族，且椭圆中心就是正定二元二次函数的极小点。2)过同心椭圆族中心x*作任意直线，此直线与诸椭圆交点处的切线相互平行。或者说：两条平行的任意方向的切线,其切点的连线必通过椭圆簇的中心。1xo2x*X2X1X1S1S2S可以证明上诉S1和S2方向是关于矩阵A的共轭方向。151()FX2()FX1xo2x*X2X1X1S1S2S1()2TTFXXXCXABS1与S2是对A共轭的一对矢量证明：设直线方程为代入F(X),并关于α求极值1(2)(1)()()0TSFXFX即120TSAS结论:两个平行方向的极小点构成的新方向与原方向相互共轭即S1与S2对A共轭也即对于二维正定二次函数只要分别沿两个共轭方向寻优即可找到最优点.101SXX102SXX0.1SFddxxFddFTii(2)(1)(2)(1)()()()FXFXAXX16与此类似，可以推出对于n维正定二次函数，共轭方向的一个十分重要的极为有用的性质：从任意初始点出发，依次沿n个线性无关的与A共轭的方向S1，S2，…Sn各进行一维搜索，那么总能在第n步或n步之前就能达到n维正定二次函数的极小点；并且这个性质与所有的n个方向的次序无关。简言之，用共轭方向法对于二次函数从理论上来讲，n步就可达到极小点。因而说共轭方向法具有有限步收敛的特性。通常称具有这种性质的算法为二次收敛算法。共轭矢量之所以引起优化研究者的重视，就是因为它的这些性质对提高优化方法的收敛速率极为有用。17例221212()2FXxxxx22)0(1x设二维目标函数，给定方向S1＝e2，初始点，求与S1相共轭的S2，并求函数的极小点。解：(1)第一个搜索方向101S(2)函数的海赛矩阵对称正定4112H(3)从(0)1X点沿S1方向求极小点x(1)，即18例解：(4)任取另初始点11)0(2x沿S1方向一维搜索求得该方向极小点x(2)X(2)=5.01(5)求与S1相共轭的方向S2S2=X(2)-X(1)=5.01核验计算矢量S1与S2确为对A矩阵共轭。(6)从x(1)点出发，沿S2方向作一维搜索，得极小点X*=[00]T221212()2FXxxxx194.2.1鲍威尔基本算法（共轭方向的原始构成）204.2.1鲍威尔基本算法2x1xo3x(0)X(1)0X(1)1X(1)2X(1)3X(1)X1S(2)0X(2)1X(2)2X(2)3X(2)X2S(3)0X(3)1X(3)3X(3)2X(3)X3S任取一初始点X(0)→X0(1)第一环:e1,e2,e3→S1第二环:e2,e3,S1→S2第三环:e3,S1,S2→S3第一轮S1,S2,S3两两共轭由前结论:两个平行方向的极小点构成的新方向与原方向相互共轭(1)1301()XXS(2)2302()XXS(3)3303()XXS214.2.1鲍威尔基本算法2x1xo3x(0)X(1)0X(1)1X(1)2X(1)3X(1)X1S(2)0X(2)1X(2)2X(2)3X(2)X2S(3)0X(3)1X(3)3X(3)2X(3)X3S第一环:e1,e2,e3→S1第二环:e2,e3,S1→S2第三环:e3,S1,S2→S3第一轮1123231eeSeS1是e1,e2,e3的线性组合S2是e2,e3,S1的线性组合S3是e3,S1,S2的线性组合1x3x2xo1033e1S2233ee新一环方向组:e2,e3,S1线性相关!降维22e22鲍威尔法的基本思想:对原始共轭方向法进行修正,即在某环已取得的n+1个方向中,选取n个线性无关,共轭程度尽可能高的方向作为下一环的基本方向组,从而避免出现“退化”现象.鲍威尔法与原始共轭方向法的主要区别是：在构成K+1环基本方向组时，不再总是淘汰前一环(K环)中的第一个方向，而是根据条件式是否得到满足分两种情况来处理。31221231213?(2)()()2FFFFFFFFF4.2.1鲍威尔修正算法23()0kX()1kX()2kX()1kmX()kmX()knX()kX()1knX()1kS()2kS()kmS()knS()1knS映射点1()F2()F3()F()kS一、Powell修正算法的搜索方向()()()10231(),(),()kkknnFFXFFXFFX()()1max()(),1,2,...,kkiiFXFXin()()1()()kkmmFXFX()()()()()()()10102kkkkkkknnnnnXXXXXXX31221231213?(2)()()2FFFFFFFFFPowell判别式24情况一：Powell判别式中若至少有一个不等式成立，则第K+1环的方向组仍用老方向组(1)(1)(1)(1)121,,......kkkknnSSSS()()()()121,,......,kkkknnSSSS初始点:(1)()0knkXX当F2F3时,当F2≥F3时,(10()1)kknXX情况二：Powell判别式中若两个不等式均不成立，则第K+1环的方向组(1)(1)(1)(1)121,,......kkkknnSSSS去掉函数值下降最大的方向,补上新增的方向初始点:(1)()0kkXX()()12(()()1)()11,,...,,,...,,kkkknnkmkmSSSSSS25以二维为例:两条件式至少有一成立且F2F3两条件式至少有一成立且F2F326两条件式均不成立且m=1两条件式均不成立且m=227终止准则:采用了上述产生基本方向组的新方式后，除了第一环以单位坐标矢量系为基本方向组外，以后每轮开始就不必重置单位坐标矢量系，只要一环接一环继续进行即可。随着逐环迭代的继续，各环的基本方向组将渐趋共轭。因此，这个修正了的鲍威尔算法，虽然已不再像基本算法那样具有二次收敛的性质，但修正算法确实克服了退化的不利情形，同时仍能够有效地、越来越快地收敛于无约束最优点x*。()()0kkXX二、修正算法的迭代步骤及流程图()0kX()1kX()2kX()1kmX()kmX()knX()kX()1knX()1kS()2kS()kmS()knS()1knS映射点1()F2()F3()F()kS2831PQFF29试用鲍尔修正算法求目标函数的最优解。迭代精度ε=0.001。2212112()242FXxxxxx已知初始点011,TX解：第一环迭代计算沿第一坐标方向e1进行一维搜索沿第二坐标轴方向e2进行一维搜索(1)(1)1