8无约束最优化的直接法

1、第八章无约束最优化的直接法本章主要内容：坐标轮换法及其收敛性模式搜索法及其收敛性旋转方向法、Powell 法。教学目的及要求：掌握坐标轮换法并理解其收敛性，掌握模式搜索法并理解其收 敛性；了解旋转方向法、Powell法。教学重点：Powell法.教学难点：Powell法.教学方法：启发式.教学手段：多媒体演示、演讲与板书相结合.教学时间：6学时.教学内容：§8.1坐标轮换法考虑无约束最优化问题(8.1.1)min f (x),其中 x Rn, f ： R算法8-1 （坐标轮换法）Step1选取初始数据.选取初始点Xg，给定允许误差Step2进行一维搜索.从xk 1出发，沿坐标轴方向e

2、k0M1进行一维搜索,M0求k1和Xk，使得f (Xk 1k g) min f (Xk 1Xkxk 1 k 1d Step3 检查迭代次数.若k n，转Step4;否则，令k : k 1，返回Step2.Step4检查是否满足终止准则.若| xn xo，迭代终止，得Xn为问题（8.1.1）的近似最优解；否则，令x0: xn,k: 1，返回Step2.定理8.1.2设f : RnR具有一阶连续偏导数，xo Rn，记f(X。)，且水平集S(f,)有界若Xk是用坐标轮换法求解问题(8.1.1)产生的点列，且在每次一维搜索中所得到的最优解都是唯一的，则(1) 当Xk为有穷点列时，其最后一个点是f的平稳

3、点；f的平(2) 当xk为无穷点列时，它必有极限点，并且其任一极限点都是 稳点.例1用坐标轮换法求解问题(8.1.3)2 2min f (x) Xix2 3x1 x1x2，其中x (X1,X2)T .取初始点x(0)(0,0) T，允许误差0.1 .解从点x(0)出发沿©进行一维搜索x(0)ei0，将2 2X1,X2 0代入 f (x) X1X2 3X1X1X2中，易得0 »(，) x(0)0e(| ,0)T ；从点x出发沿e2进行一维搜索，得13,x(2)X 4X(2) X(0)(3 3)T .(2,4)；再从点x(2)出发沿e1进行一维搜索，得(15 3)tM)；从点x

4、出发沿e2进行一维搜索，得3 3，XX3e24x x(2).J5 %(亍材；再从点x出发沿e1进行一维搜索，得3(5)432,x x 金Q3 15、t(32 韦)；从点X出发沿e2进行一维搜索，得3(6)(5)5,X X64x(6)x5e (-63,-63)t ；32 64再从点x(6)出发沿e进行一维搜索,3(7)(6)6 128，x x6ei(255 63)t ；(128,64)；从点x出发沿e2进行一维搜索，得7 為 x(8)x(7)x(8)x(6)7e2255 255t() ；12856'迭代终止，得问题(8.1.3)的近似最优解为(8),255 255 tx (,) 128

5、256其实问题(8.1.3)的最优解为(2,1)t .§ .2模式搜索法算法8-2 (模式搜索法)Step1选取初始数据选取初始点X。，初始步长° 0,给定收缩因子(0,1)，给定允许误差0,令k 0 .Step2确定参考点.令y Xk, j 1 .Step3 进行正轴向探测.从点y出发，沿ej作正轴向探测：若f(ykej)f(y)，令 y:yk，转 Step5；否则，转 Step4.Step4 进行负轴向探测.从点y出发，沿ej作负轴向探测：若f(ykej)f(y)，令 y:yk，转 Step5；否则，转 Step5.Step5检验探测次数.若j n，令j : j 1，返

6、回Step3;否贝U，令xk 1 转 Step6.Step6进行模式移动.若f区i)f (xj,从点Xki出发沿加速方向Xki Xk作模式移动，令 y 2Xki Xk, ki k,k ： k 1, j 1，返回 Step3;否贝U,转 Step7.Step7检查是否满足终止准则.若k，迭代终止，得问题(8.1.1 )的近似最优解为Xk;否则，转Step8.Step8缩短步长.若Xk 1 Xk，令k 1 k,k: k 1，返回Step2;否则， 令Xk 1 Xk, k 1 k, k: k 1，返回 Step2.定理8.2.1设f ：RnR是具有一阶连续偏导数的凸函数，Xo Rn，记f(Xo)，并

7、且水平集S(f,)有界.若Xk为由模式搜索法求解问题(8.1.1) 产生的点列，贝U Xk必存在极限，且其任一极限点都是问题(8.1.1)的最优解.§8.3旋转方向法算法8-3 (旋转方向法)Step1选取初始数据.选取初始点X0，初始单位正交方向组d1,d2,L ,dn (可 取d1,d2,L ,dn为坐标轴方向久仓丄©)给定初始步长 (V,丄，丁， 收缩因子(0,1)，放大因子 1，允许误差0,令k 0 .Step2确定参考点.取参考点y Xk，并令z Xk, j 1.Step3 进行轴向探测.若 f(y(k)dj) f(y)，令 y: y(k)dj, (k):(k)，

8、转 Step4；否则，令(k) :(k)，转 Step4.Step4检验探测次数.若j n，令j : j 1，返回Step3;否则，转Step5.Step5判断探测是否结束.若f(y) f (z)，令z y, j 1，返回Step3;若 f (y)f(z), f(y) f (Xk)，令 Xk 1 y，转 Step6;若 f (y) f(z) f(xQ，转 Step7.Step6检查是否满足终止准则.若Xk 1 Xk，迭代终止，Xk 1为问题(8.1.1)的近似最优解；否则，转 Step8.Step7检验步长大小若对一切j 1,2,L , n.(k) j,迭代终止，Xk为问题（8.1.1）的近似

9、最优解；否则，令z y, j 1，返回Step3.1, 2,L , n，利Pjdj，n0,i di，0.(8.3.1)Pj,j 1,qjPjTqi PjTi 1 qi Pijdj, j 2.构造新的单位正交方向djqj,j 1,2丄(8.3.2)(831)d1,d2,L ,dn，并令Step8进行轴向旋转.计算各轴向移动的步长的代数和:dj dj, (k1)j(k),j 1,2,L , n,k: k 1，返回Step2.§8.4 Powell 法算法 8-4 （Powell 法）Step1选取初始数据.选取初始点X）， n个线性无关的初始搜索方向d0,d1,L ,dn 1，给定允许误

10、差0,令k 0.Step2进行基本搜索.令y° Xk，依次沿d°,d1,L ,dn 1进行一维搜索.对一 切j 1,2丄，n,记f （Yj 1j 1dj 1） min f 厲 1dj J，yj yj 1j 1dj 1 .Step3检查是否满足终止准则.取加速方向 dn Yn Y0，若II dn|，迭代 终止，得Yn为问题的近似最优解；否则，转 Step4.Step4确定搜索方向按f(ym) f(ymi) 0mjaxi f(yj) f(yj 1)( 84仃)确定m,若f(y。)2f(yn) f (2yn y。)2f(ym) f(ymi)(8.4.18)成立，转Step5;否则

11、，转Step6.Step5调整搜索方向从点yn出发沿方向dn作一维搜索求出n，使得f(ynndn) minf®.dn) 令Xk 1 ynndn，再令 dj : dj 1, j m,m 1,L ,n 1 , k: k 1，返回 Step2.Step6不调整搜索方向.令Xk 1 yn， k: k 1，返回Step2.例 2 用 Powell 法求解问题(8.1.3): min f (x) x12 x22 3x1 x1x2，仍取初始点x(0)(0,0) T，初始搜索方向组do (0,1)T,d1 (1,0)T，给定允许误差0.1.解第一次迭代：令y(0)x(0)(0,0)T，从点y(0)出

12、发沿d0进行一维搜索，易得0 0, yy(0)0d0 (0,0)T ;接着从点y出发沿d1进行一维搜索，得33 t1 2,y y1d1(2，。)由此有加速方向d2 yy® (|,0)T .因为d23/2，所以要确定调整方向.由于 f(y(0) 0,f(y)0,f(y(2)9，4按(8.4.17)式有f(y)f(y(2) maxf(y(j) f(y(j1)| j 0,1，因此m 1，并且f(y(m) f(y(m 1) f(y)f(y(2)夕.4又因f(2yy)0,故(8418)式不成立于是，不调整搜索方向组，并令x(1)y(2)(|,0)T -第二次迭代：取y(0)x(,0)T，从点y(0)出发沿d0作一维搜索，得,3I23 (1)(0)3 3、t0 ，y y0d0(,)-4 2 4接着从点y出发沿方向d!作一维搜索，得315 3 t1 8，y y Q 塔讦-由此有加速方向(0)/33 Td2 y y(着)因为d23苗/8，所以要确定调整方向因18964，f(y(0)故按(8417)式易知m9(1)45、匚，f(y) ,f(y)4160，并且f(y(m)f(y(m 1)f(y(0) f(y)916由于f(2y y(0)4516，因此(