8无约束最优化的直接法

第八章 无约束最优化的直接法

本章主要内容：坐标轮换法及其收敛性 模式搜索法及其收敛性 旋转方向法、

Powell法。

教学目的及要求：掌握坐标轮换法并理解其收敛性，掌握模式搜索法并理解其收

敛性；了解旋转方向法、Powell法。

教学重点：Powell法． 教学难点：Powell法． 教学方法：启发式．

教学手段：多媒体演示、演讲与板书相结合． 教学时间：6学时． 教学内容：

§8.1 坐标轮换法

考虑无约束最优化问题

minf(x)， （8.1.1） 其中x?Rn,f:Rn?R．

算法8-1（坐标轮换法）

Step1 选取初始数据．选取初始点x0，给定允许误差??0，令k?1．

?0????M?Step2 进行一维搜索．从xk?1出发，沿坐标轴方向ek??1?进行一维搜索，

???M??0???求?k?1和xk，使得

f(xk?1??k?1ek)?minf(xk?1??ek)，

?xk?xk?1??k?1ek．

Step3 检查迭代次数．若k?n，转Step4；否则，令k:?k?1，返回Step2． Step4 检查是否满足终止准则．若xn?x0??，迭代终止，得xn为问题（8.1.1）的近似最优解；否则，令x0:?xn,k:?1，返回Step2．

定理8.1.2 设f:Rn?R具有一阶连续偏导数，x0?Rn，记??f(x0)，且水平集S(f,?)有界．若?xk?是用坐标轮换法求解问题（8.1.1）产生的点列，且在每次一维搜索中所得到的最优解都是唯一的，则

（1）当?xk?为有穷点列时，其最后一个点是f的平稳点；

（2）当?xk?为无穷点列时，它必有极限点，并且其任一极限点都是f的平稳点．

例1 用坐标轮换法求解问题

minf(x)?x12?x22?3x1?x1x2， （8.1.3） 其中x?(x1,x2)T．取初始点x(0)?(0,0)T，允许误差??0.1．

?0??1????解 从点x(0)出发沿e1进行一维搜索：x(0)??e1??????????，将

?0??0??0?x1??,x2?0代入f(x)?x12?x22?3x1?x1x2中，易得

?0?,x(1)?x(0)??0e1?(,0)T；

从点x(1)出发沿e2进行一维搜索，得

3232?1?,x(2)?x(1)??1e2?(,)T；

x(2)?x(0)??．

再从点x(2)出发沿e1进行一维搜索，得

343324?2?,x(3)?x(2)??2e1?(从点x(3)出发沿e2进行一维搜索，得

38153T,)； 84?3?,x(4)?x(3)??3e2?(x(4)?x(2)??．

再从点x(4)出发沿e1进行一维搜索，得

341515T,)； 816?4?3(5)6315,x?x(4)??4e1?(,)T； 323216从点x(5)出发沿e2进行一维搜索，得

?5?3(6)6363,x?x(5)??5e2?(,)T； 643264x(6)?x(4)??．

再从点x(6)出发沿e1进行一维搜索，得

?6?3(7)25563T,x?x(6)??6e1?(,)； 12812864从点x(7)出发沿e2进行一维搜索，得

?7?3255255T,x(8)?x(7)??7e2?(,)； 256128256x(8)?x(6)??．

迭代终止，得问题（8.1.3）的近似最优解为

x(8)?(255255T,)． 128256其实问题（8.1.3）的最优解为(2,1)T．

§8.2 模式搜索法

算法8-2（模式搜索法）

Step1 选取初始数据．选取初始点x0，初始步长?0?0，给定收缩因子

??(0,1)，给定允许误差??0，令k?0．

Step2 确定参考点．令y?xk,j?1．

Step3 进行正轴向探测．从点y出发，沿ej作正轴向探测：若

f(y??kej)?f(y)，令y:?y??kej，转Step5；否则，转Step4．

Step4 进行负轴向探测．从点y出发，沿ej作负轴向探测：若

f(y??kej)?f(y)，令y:?y??kej，转Step5；否则，转Step5．

Step5 检验探测次数．若j?n，令j:?j?1，返回Step3；否则，令xk?1?y，转Step6．

Step6 进行模式移动．若f(xk?1)?f(xk)，从点xk?1出发沿加速方向xk?1?xk作模式移动，令y?2xk?1?xk,?k?1??k,k:?k?1,j?1，返回Step3；否则，转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:Rn?R是具有一阶连续偏导数的凸函数，x0?Rn，记

??f(x0)，并且水平集S(f,?)有界．若?xk?为由模式搜索法求解问题（8.1.1）产生的点列，则?xk?必存在极限，且其任一极限点都是问题（8.1.1）的最优解．

§8.3 旋转方向法

算法8-3（旋转方向法）

Step1 选取初始数据．选取初始点x0，初始单位正交方向组d1,d2,L,dn（可取d1,d2,L,dn为坐标轴方向e1,e2,L,en）．给定初始步长?(0)?(?1(0),?2(0),L,?n(0))T，收缩因子??(0,1)，放大因子??1，允许误差??0，令k?0．

Step2 确定参考点．取参考点y?xk，并令z?xk,j?1．

k)k)(k)(k)Step3 进行轴向探测．若f(y??(令y:?y??(jdj)?f(y)，jdj,?j:???j，k)(k)转Step4；否则，令?(j:????j，转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(xk)，转Step7．

Step6 检查是否满足终止准则．若xk?1?xk??，迭代终止，xk?1为问题（8.1.1）的近似最优解；否则，转Step8．

k)Step7 检验步长大小．若对一切j?1,2,L,n,?(??，迭代终止，xk为问j题（8.1.1）的近似最优解；否则，令z?y,j?1，返回Step3．

Step8 进行轴向旋转．计算各轴向移动的步长的代数和：?1,?2,L,?n，利用

?j?0,?dj,?pj??n （8.3.1）

???idi,?j?0.?i?jj?1,?pj,?j?1Tqj?? （8.3.2） qipjp??d,j?2.?j?Tjji?1qipi?dj?qjqj,j?1,2,L,n． （8.3.1）

构造新的单位正交方向d1,d2,L,dn，并令

dj?dj,?j(k?1)??j(k),j?1,2,L,n,k:?k?1，

返回Step2．

§8.4 Powell法

算法8-4（Powell法）

Step1 选取初始数据．选取初始点x0，n个线性无关的初始搜索方向

d0,d1,L,dn?1，给定允许误差??0，令k?0．

Step2 进行基本搜索．令y0?xk，依次沿d0,d1,L,dn?1进行一维搜索．对一切j?1,2,L,n，记

f(yj?1??j?1dj?1)?minf(yj?1??dj?1)，

?yj?yj?1??j?1dj?1．

Step3 检查是否满足终止准则．取加速方向dn?yn?y0，若dn??，迭代终止，得yn为问题的近似最优解；否则，转Step4．