第4章无约束优化方法

1、第四章第四章 无约束优化方法无约束优化方法4.14.24.34.44.54.64.74.84.9，数值解法：数值解法：是利用是利用已有已有的信息，通过计算点一步一步地的信息，通过计算点一步一步地直接移动，直接移动，逐步逼近逐步逼近最后达到最优点。最后达到最优点。 1(0,1,)kkkkxxdk1 1）选择迭代方向即探索方向；）选择迭代方向即探索方向；2 2）在确定的方向上选择适当步长迈步进行探索）在确定的方向上选择适当步长迈步进行探索 ， 一类是利用目标函数的一类是利用目标函数的一阶或二阶导数一阶或二阶导数的无约束优化的无约束优化方方法（如最速下降法、共轭梯度法、牛顿法及变尺度法）；法（如最速

2、下降法、共轭梯度法、牛顿法及变尺度法）； 另一类另一类只利用目标函数只利用目标函数的无约束优化方法（如坐标轮的无约束优化方法（如坐标轮换换法、单形替换法及鲍威尔法等）。法、单形替换法及鲍威尔法等）。， 最速下降法就是采用使目标函数值下降得最快的最速下降法就是采用使目标函数值下降得最快的负负梯度方向梯度方向作为探索方向，来求目标函数的极小值的方法，作为探索方向，来求目标函数的极小值的方法，又称为又称为梯度法梯度法。1()(0,1,)kkkkxxf xk最速下最速下降法的降法的迭代公迭代公式式， 011*10();3minmin4|;1,kkkkkkkkkkkkkxkdf xfxa daxxa d

3、xxxxkk 1）给定初始点 和收敛精度 ，置；2）计算梯度，并构造搜索方向）用一维搜索的方法求解得最佳步长 ，代入得到新的迭代点；）若，则停止迭代，得最优解否则，转到第二步。2212 ( )25 f xxx例：用最速下降法求目标函数的极小点。，1()(0,1,)kkkkxxf xk， 1 1）对）对初始搜索点初始搜索点无严格要求；无严格要求； 2 2）收敛）收敛速度不快速度不快； 3 3）相邻两次相邻两次迭代搜索迭代搜索方向方向互相互相垂直垂直，在远离极值点处，在远离极值点处收敛快，在靠近极值点处收敛慢；收敛快，在靠近极值点处收敛慢； 4 4）收敛速度与）收敛速度与目标函数值的性质目标函数值

4、的性质有关，对等值线是有关，对等值线是同同心圆心圆的目标函数来说，经过的目标函数来说，经过一次迭代一次迭代就可以达到极值点。就可以达到极值点。， 利用利用二次曲线二次曲线来逐点来逐点近似原目标函数近似原目标函数，以，以二次曲线的二次曲线的极极小点小点来来近似原目标函数的极小点近似原目标函数的极小点并逐渐逼近该点。并逐渐逼近该点。 基本牛顿法的迭代公式：基本牛顿法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x ，基本牛顿法的迭代公式：基本牛顿法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 022121211,1 ,0.1 min( )224Txf

5、 xxxx xx例：用基本牛顿法求解下列无约束优化问题，已知。，基本牛顿法的迭代公式：基本牛顿法的迭代公式：11 (0,1,2)()kkkkkkxxdkdG xf x 阻尼牛顿法的迭代公式：阻尼牛顿法的迭代公式：11 (0,1,2,)() kkkkkkkxxdkdG xf x ，01111*1,0;()()()()34|;1,kkkkkkkkkkkkkkkxkf xG xG xdG xf xxxddxxxxkk 1）给定初始点收敛精度 ，置2）计算、和，得到；）求，其中，是沿着进行一维搜索的最佳步长；）检查收敛精度。若，则停止迭代，得最优解否则，转到第二步继续进行搜索。，022121211,1

6、 ,0.1 min( )224Txf xxxx xx例：用阻尼牛顿法求解下列无约束优化问题，已知。阻尼牛顿法的迭代公式：阻尼牛顿法的迭代公式：11 (0,1,2,)() kkkkkkkxxdkdG xf x ，10()0Tf xd 在下一次迭代时，选择搜索方在下一次迭代时，选择搜索方d d1 1指向极小点指向极小点x x* *， *111xxa d以以二元函数二元函数为例：为例： 我们任意选择一个我们任意选择一个初始点初始点x x0 0点，点，沿着沿着某个下降方向某个下降方向d d0 0作一维搜索作一维搜索 1000 xxa d 12TTfxx Gxb xc010TdGd ，01m 101m

7、1Gnmddd()0 ( ,0,1,1) ()dddGGi TjdGdi jmij设 是n n对称正定矩阵，若 维空间中有 个非零向量 、 、 、满足 则称 、 、 、对 共轭，或称它们是 的共轭方向。01m 1G I()0 ()dddiTjddij当 = （单位矩阵）时，有，即向量、 、 、互相正交。， 01m 1001n 1*dddG() m2nn3xnGdddn1x2TTfxx Gxb xc性质1：若非零向量系、 、 、是对实对称正定矩阵共轭的，则这 个向量是线性无关的。性质 ：在 维空间中互相共轭的非零向量个数不超过 。性质 ：从任意初始点点出发，顺次沿 个 的共轭方向、 、 、进行一

8、维搜索，最多经过 次迭代就可以 找到二次函数的极小点 。，00k111111xdkd340j01 2k5kk+1kkkkkkTkjkxxa df xxddGd）选定初始点 ，下降方向和收敛精度 ， 置0；2）沿方向进行一维搜索，得；）判断是否满足，满足则打印， 否则，转到第四步；）提供新的共轭方向，使， ， ，；）置，转第二步。，111,0iiriirrdvdn n个线性无关的向量系个线性无关的向量系vi vi（i=0,1i=0,1，n-1 n-1 ）一组独立向量一组独立向量d dr r（r=0,1r=0,1，n-1n-1） 11,()()j Tiijj TjdGvdGd 1110()()jT

9、iijiijTjjdGvdvddGd012210G=121012ddd例：求的一组共轭向量系、 、。，1110()()jTiijiijTjjdGvdvddGd111,0iiriirrdvd11,()()j Tiijj TjdGvdGd ， 先沿先沿最速下降方向最速下降方向( (负梯度方向负梯度方向) )探索第一步，然后沿与探索第一步，然后沿与该负梯度方向相该负梯度方向相共轭的方向共轭的方向进行探索。进行探索。，1()0Tjkkdgg 它表示沿着方向它表示沿着方向d dk k做一维搜索，做一维搜索，它的终点它的终点x xk+1k+1与始点与始点x xk k的梯度之差的梯度之差与与d dk k的共

10、轭方向的共轭方向d dj j正交。正交。 ，21112| |(0,1,2,1)kkkkkgdgdgkn ，001(1)*1*10121;(),0;3);4)(),()(),5|kkkkkkkkkkkkkdf xkdxxdf xxxf xf xknxxg 1)给定初始点x 和计算精度2）取x 的负梯度方向作为搜索方向：置沿方向作一维搜索得判断收敛：若满足则令，结束迭代；否则，转到第五步；）若，则令，转到第二步开始新的一轮的迭代；否则，转到第六步；6）构造新的共轭方向112,|1,kkkkkdgdgkk ，令转到第三步。，221212112( ,)242f x xxxxx x例：用共轭梯度法求二次

11、函数的极小点及极小值。，21112| |(0,1,2,1)kkkkkgdgdgkn 设法构造出一个设法构造出一个对称正定矩阵对称正定矩阵 来代替来代替 ，并，并在迭代过程中使在迭代过程中使 逐渐逼近逐渐逼近 , ,那么就简化了牛顿那么就简化了牛顿法的计算，并且保持了牛顿法收敛快的优点。法的计算，并且保持了牛顿法收敛快的优点。kH1()kG x1()kG xkH，1()kkkdG xfx 1 (0,1,2)kkkkkxxHf xk尺度矩阵尺度矩阵， 12TTfxx Gxb xcxQx12TTx Q GQxG G 正定正定TQ GQI牛顿迭代公式：牛顿迭代公式：1kkTkkxxQQf x1TQQG

12、THQQ1kkkkkxxHfx目标函数的偏心率减小到零。，1kkkkkxxHfx变尺度法的迭代公式：变尺度法的迭代公式：搜索方向：搜索方向： =kkkkkdHfxH g 尺度矩阵应具备的条件：尺度矩阵应具备的条件：1 1）为正定对称矩阵；）为正定对称矩阵；2 2）具有简单的迭代形式）具有简单的迭代形式: :3 3）满足拟牛顿条件：）满足拟牛顿条件：令令 则则111()kkkkkHggxx1kkkHHE1kkkygg1kkksxx1kkkHys，0000011111*11)2)()03)=4)(),5)66)kkkkkkkkkkkkkkkkkkxgf xHHIkdH gdxxdgf xsxxyg

13、gxxnH 选定初始点和收敛精度 ；计算，选定初始对称正定矩阵 （如），置；计算搜索方向；沿方向进行一维搜索，计算， ；判断是否满足迭代终止条件，若满足则，停机，否则转到 ；若迭代 次后还没有找到极小点，重置为单位矩阵011277)13kkkkIxxHHEkk，并以当前设计点 为初始点，返回 进行下一轮迭代，否则转到 ；计算矩阵，置，返回 。，DFPDFP算法的校正公式算法的校正公式1 (0,1,2,)TTkkkkkkkkkkTTkkkkks sH y y HHHEHks yy H y，221212112DFP,242 f x xxxxx x例：用算法求的极值解。1 (0,1,2,)TTkkk

14、kkkkkkkTTkkkkks sH y y HHHEHks yy H y， 每次仅对多元函数的每次仅对多元函数的一个变量一个变量沿其沿其坐标轴坐标轴进行进行一维探索一维探索，其余各变量均固定不动，并，其余各变量均固定不动，并依次轮换依次轮换进行进行一一维探索的坐标轴维探索的坐标轴，完成第一轮探索后再重新进行第二轮，完成第一轮探索后再重新进行第二轮探索，直到找到目标函数在全域上的最小点为止。探索，直到找到目标函数在全域上的最小点为止。将一个将一个多维多维的无约束最优化问题，转化为的无约束最优化问题，转化为一系一系列的一维问题列的一维问题来求解。来求解。，二维问题二维问题，1 (0,1,2, 1

15、,2, )kkkkiiiixxdkin00100kTiide11()()kkkkiiiif xdf x包括正负包括正负，随机选择方法随机选择方法加速步长法加速步长法最优步长法（一维搜索方法，如：黄金分割法、最优步长法（一维搜索方法，如：黄金分割法、二次插值法，来确定最优步长）二次插值法，来确定最优步长）11()()kkkkiiiif xdf x11min()()kkkkkiiiiif xdf xd，1111)2)()()3)()J 1()J4)kkiikkkkkiiiiiikiikiihff xf xdff xff x先以试验步长确定步长的正负，当沿坐标轴正方向探索能使目标函数值减小时，则取正

16、值，否则应取负值；按所取步长计算目标函数值若，则取加速步长，使其沿同一方向延伸；若延伸至第次时，则延伸至第 次为止。当步长不宜延伸而宜缩小时，亦可缩小，也是一直到函数值达到最小值为止；改kid变方向，在新的方向上重复前述过程，直到函数值达到最小值为止，终止计算。， 计算简单、概念清楚、易于掌握；但搜索路线较长计算简单、概念清楚、易于掌握；但搜索路线较长（需要经过多次曲折迂回的路径才能达到极值点），计（需要经过多次曲折迂回的路径才能达到极值点），计算率较低，特别是当维数很高时很费时，所以坐标轮换算率较低，特别是当维数很高时很费时，所以坐标轮换法只能用于低维（法只能用于低维（n10n10）的优化问

17、题求解。此外，坐标）的优化问题求解。此外，坐标轮换法的效率在很大程度上取决于目标函数的性态，也轮换法的效率在很大程度上取决于目标函数的性态，也就是等值线的形态与坐标轴的关系。就是等值线的形态与坐标轴的关系。 ，直接利用迭代点的直接利用迭代点的目标函数值目标函数值来来构造共轭构造共轭方向方向，然后再从任一初始点出发，然后再从任一初始点出发，逐次的共轭方向逐次的共轭方向作一维搜索求极值点。作一维搜索求极值点。，共轭方向的生成：共轭方向的生成：结论：结论：从从不同的不同的两点两点出发，沿出发，沿同同一方向一方向进行两次进行两次一维搜索，所得一维搜索，所得两个极小点的连两个极小点的连线方向线方向便是便

18、是原方原方向共轭向共轭的另一方的另一方向。向。，共轭方向的生成：共轭方向的生成：二维情况：二维情况：任意点出发沿着任意点出发沿着x1x1轴轴方方向和向和ABAB方向搜索，即可方向搜索，即可得到极小点。得到极小点。，基本基本POWELLPOWELL法（二维）：法（二维）：012012001001220112012111021121)1 00 12)3)TTxeexeexxdxxxdxedxedxx任选一初始点 ，再选两个线性无关的向量，如坐标单位向量和作为初始搜索方向。从 出发，顺次沿着 、 作一维搜索得到点、 ，两点连线得到一个新的方向。再从 出发沿着作一维搜索得到点 ，作为下一轮迭代的初始点

19、。下一轮迭代的搜索方向 、 。从 出发，顺次沿着 、作一维搜索，得到点 、211212012222*dxxddGxdxxx，两点连线得一个新的方向。同一起对 共轭。再从 出发，沿着作一维搜索得到点 。 点就是该二维问题的极小点 。基本基本POWELLPOWELL法（法（n n维）：维）：1 1）从初）从初始点始点出发，首先沿着出发，首先沿着n n个坐标轴方向个坐标轴方向进行一维搜索，得进行一维搜索，得到一个终点；到一个终点；2 2）由初）由初始点和终点连线始点和终点连线形成一个形成一个新方向新方向，该方向排在原方向，该方向排在原方向组的最后，去掉原方向组的的第一个方向，形成新的方向组；组的最后

20、，去掉原方向组的的第一个方向，形成新的方向组；3 3）从上一轮的搜索）从上一轮的搜索终点终点出发沿出发沿新的搜索方向新的搜索方向作一维搜索而得作一维搜索而得到的极小点，作为到的极小点，作为下一轮下一轮迭代的迭代的始点始点。4 4）从）从新的始点新的始点出发，沿着出发，沿着新的方向组新的方向组做一维搜索。做一维搜索。 如此反复进行如此反复进行n n轮轮搜索后，可找到搜索后，可找到n n个共轭方向个共轭方向，若目标函数，若目标函数是是正定二次正定二次型函数，则经过型函数，则经过n n轮后就可以找到极小点。轮后就可以找到极小点。改进改进POWELLPOWELL法：法： 获得新方向构成新方向组时获得新方向构成新方向组时, ,不是轮换地