无约束最优化的直接法.doc

《无约束最优化的直接法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、求和，使得，．Step3检查迭代次数．若，转Step4；否则，令，返回Step2．Step4检查是否满足终止准则．若，迭代终止，得为问题（8.1.1）的近似最优解；否则，令，返回Step2．定理8.1.2设具有一阶连续偏导数，，记，且水平集有界．若是用坐标轮换法求解问题（8.1.1）产生的点列，且在每次一维搜索中所得到的最优解都是唯一的，则（1）当为有穷点列时，其最后一个点是的平稳点；（2）当为无穷点列时，它必有极限点，并且其任一极限点都是的平稳点．例1用坐标轮换法求解问题，（8.1.3）其中．取初始点，允许误差．解从点出发沿进行一维搜索：，将

3、代入中，易得；从点出发沿进行一维搜索，得；．再从点出发沿进行一维搜索，得；从点出发沿进行一维搜索，得；．再从点出发沿进行一维搜索，得；从点出发沿进行一维搜索，得；．再从点出发沿进行一维搜索，得；从点出发沿进行一维搜索，得；．迭代终止，得问题（8.1.3）的近似最优解为．其实问题（8.1.3）的最优解为．§8.2模式搜索法算法8-2（模式搜索法）Step1选取初始数据．选取初始点，初始步长，给定收缩因子，给定允许误差，令．Step2确定参考点．令．Step3进行正轴向探测．从点出发，沿作正轴向探测：若，令，转Step5；否则，转Step4．Ste

4、p4进行负轴向探测．从点出发，沿作负轴向探测：若，令，转Step5；否则，转Step5．Step5检验探测次数．若，令，返回Step3；否则，令，转Step6．Step6进行模式移动．若，从点出发沿加速方向作模式移动，令，返回Step3；否则，转Step7．Step7检查是否满足终止准则．若，迭代终止，得问题（8.1.1）的近似最优解为；否则，转Step8．Step8缩短步长．若，令，返回Step2；否则，令，返回Step2．定理8.2.1设是具有一阶连续偏导数的凸函数，，记，并且水平集有界．若为由模式搜索法求解问题（8.1.1）产生的点列，则

5、必存在极限，且其任一极限点都是问题（8.1.1）的最优解．§8.3旋转方向法算法8-3（旋转方向法）Step1选取初始数据．选取初始点，初始单位正交方向组（可取为坐标轴方向）．给定初始步长，收缩因子，放大因子，允许误差，令．Step2确定参考点．取参考点，并令．Step3进行轴向探测．若，令，转Step4；否则，令，转Step4．Step4检验探测次数．若，令，返回Step3；否则，转Step5．Step5判断探测是否结束．若，令，返回Step3；若，令，转Step6；若，转Step7．Step6检查是否满足终止准则．若，迭代终止，为问题（8.

6、1.1）的近似最优解；否则，转Step8．Step7检验步长大小．若对一切，迭代终止，为问题（8.1.1）的近似最优解；否则，令，返回Step3．Step8进行轴向旋转．计算各轴向移动的步长的代数和：，利用（8.3.1）（8.3.2）．（8.3.1）构造新的单位正交方向，并令，返回Step2．§8.4Powell法算法8-4（Powell法）Step1选取初始数据．选取初始点，个线性无关的初始搜索方向，给定允许误差，令．Step2进行基本搜索．令，依次沿进行一维搜索．对一切，记，．Step3检查是否满足终止准则．取加速方向，若，迭代终止，得为问

7、题的近似最优解；否则，转Step4．Step4确定搜索方向．按（8.4.17）确定，若（8.4.18）成立，转Step5；否则，转Step6．Step5调整搜索方向．从点出发沿方向作一维搜索．求出，使得．令，再令，，返回Step2．Step6不调整搜索方向．令，，返回Step2．例2用Powell法求解问题（8.1.3）：，仍取初始点，初始搜索方向组，给定允许误差．解第一次迭代：令，从点出发沿进行一维搜索，易得；接着从点出发沿进行一维搜索，得由此有加速方向．因为，所以要确定调整方向．由于，按（8.4.17）式有，因此，并且．又因，故（8.4.1

8、8）式不成立．于是，不调整搜索方向组，并令．第二次迭代：取，从点出发沿作一维搜索，得．接着从点出发沿方向作一维搜索，得．由此有加速方向．因为，所以要确