无约束最优化的直接法

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

2、否则，令，返回Step2Step4 检查是否满足终止准则若，迭代终止，得为问题（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；否则，转Step4Step4 进行负轴向探测从点出发，沿作负轴向探测：若，令，转Step5；否则，转Step5Step5 检验探测次数若，令，返回Step3；否则，令，转Step6Step6 进行模式移

4、动若，从点出发沿加速方向作模式移动，令，返回Step3；否则，转Step7Step7 检查是否满足终止准则若，迭代终止，得问题（8.1.1）的近似最优解为；否则，转Step8Step8 缩短步长若，令，返回Step2；否则，令，返回Step2定理8.2.1 设是具有一阶连续偏导数的凸函数，记，并且水平集有界若为由模式搜索法求解问题（8.1.1）产生的点列，则必存在极限，且其任一极限点都是问题（8.1.1）的最优解8.3 旋转方向法算法8-3（旋转方向法）Step1 选取初始数据选取初始点，初始单位正交方向组（可取为坐标轴方向）给定初始步长，收缩因子，放大因子，允许误差，令Step2 确定参考点

5、取参考点，并令Step3 进行轴向探测若，令，转Step4；否则，令，转Step4Step4 检验探测次数若，令，返回Step3；否则，转Step5Step5 判断探测是否结束若，令，返回Step3；若，令，转Step6；若，转Step7Step6 检查是否满足终止准则若，迭代终止，为问题（8.1.1）的近似最优解；否则，转Step8Step7 检验步长大小若对一切，迭代终止，为问题（8.1.1）的近似最优解；否则，令，返回Step3Step8 进行轴向旋转计算各轴向移动的步长的代数和：，利用 （8.3.1） （8.3.2） （8.3.1）构造新的单位正交方向，并令，返回Step28.4 Po

6、well法算法8-4（Powell法）Step1 选取初始数据选取初始点，个线性无关的初始搜索方向，给定允许误差，令Step2 进行基本搜索令，依次沿进行一维搜索对一切，记，Step3 检查是否满足终止准则取加速方向，若，迭代终止，得为问题的近似最优解；否则，转Step4Step4 确定搜索方向按 （8.4.17）确定，若 （8.4.18）成立，转Step5；否则，转Step6Step5 调整搜索方向从点出发沿方向作一维搜索求出，使得令，再令，返回Step2Step6 不调整搜索方向令，返回Step2例2 用Powell法求解问题（8.1.3）：，仍取初始点，初始搜索方向组，给定允许误差解 第一次迭代：令，从点出发沿进行一维搜索，易得；接着从点出发沿进行一维搜索，得由此有加速方向因为，所以要确定调整方向由于 ，按（8.4.17）式有，因此，并且又因，故（8.4.18）式不成立于是，不调整搜索方向组，并令第二次迭代：取，从点出发沿作一维搜索，得接着从点出发沿方向作一维搜索，得由此有加速方向因为，所以要确定调整方向因，故按（8.4.17