常用无约束最优化方法课件.ppt

《常用无约束最优化方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、CompanyLogo4.74.64.54.44.3修正Newton法共轭方向法共轭梯度法变尺度法坐标轮换法第四章常用无约束最优化方法4.24.14.8最速下降法Newton法单纯形法CompanyLogo成立．点就是问题（4.1）的全局最优点．但是，大多数最优化方法只能求到局部最优点，即在中找到一点，使得式（4.2)在的某个领域中成立．第四章常用无约束最优化法本章开始讨论多维无约束最优化问题（4.1）其中．这个问题的求解是指，在中找一点，使得对于任意的都有（4.2）CompanyLogo这个矛盾对于实

2、际问题来讲一般容易解决，因为根据问题的实际意义多半可以直接判定用优化方法求出的局部最优解是否为全局最优解．但在理论上这是个比较复杂的问题，本书不涉及．无约束优化方法是优化技术中极为重要和基本的内容之一．它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解．另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题．CompanyLogo无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现．把这些方法归纳起来可以分成两大类：一

3、类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（或解析法）．直接法不涉及导数和Hesse矩阵，适应性强，但收敛速度一般较慢；间接法收敛速度一般较快，但需计算梯度，甚至需要计算Hesse矩阵．一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法．CompanyLogo一、最速下降法基本原理在基本

4、迭代公式中，每次迭代搜索方向取为目标函数的负梯度方向，即，而每次迭代的步长取为最优步长，由此所确定的算法称为最速下降法．对于问题（4.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点出发，通过基本迭代公式，按照特定的算法产生一串点列，如果点列收敛，则该点列的极限点为问题（4.1）的最优解．§4.1最速下降法CompanyLogo为了求解问题（4.1），如图4.1所示，假定我们已经迭代了次，获得了第个迭代点．现在从出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）

5、进行搜索应该是有利的，至少在邻近的范围内是这样．因此，取搜索方向为．．图4.1CompanyLogo为了使目标函数在搜索方向上获得最多的下降，沿进行一维搜索，由此得到第个迭代点，即，其中步长因子按下式确定，也可记为．（4.3）显然，令就可以得到一个点列，其中是初始点，由计算者任意选定．当满足一定的条件时，由式（4.3）所产生的点列必收敛于的极小点．CompanyLogo以后为书写方便，记．因此，．在不发生混淆时，再记．CompanyLogo已知目标函数及其梯度，终止限、和．（1）选定初始点，计算，；置．

6、（2）作直线搜索：；计算，．（3）用终止准则检测是否满足：若满足，则打印最优解，，结束；否则，置，转（2）．最速下降法算法流程如图4.2所示．二、最速下降法迭代步骤，CompanyLogo开始结束选定X0YX，fH准则满足最速下降法算法流程如图所示．图4.2CompanyLogo设第次迭代点为，我们来求的表达式．对式(4.4)关于求梯度，有，(4.5)因此，．(4.6)现在从出发沿作直线搜索以确定，于是，(4.7)其中是最优步长因子．将最速下降法应用于正定二次函数（4.4）可以推出显式迭代公式．Comp

7、anyLogo又因式（4.2），有，再利用式（4.5），式（4.6）和式（4.7）可得或．由此解出，代入式（4.7）中得到.（4.8）这就是最速下降法用于二次函数的显式迭代公式．CompanyLogo例4.1试用最速下降法求函数的极小点．迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的．设初始点为．CompanyLogo解与式（4.4）比较，得，梯度表达式是，由，计算出，，．因为目标函数是二次的，可以使用式（4.8），所以有，CompanyLogo计算因为由此说明相邻两个搜索方

8、向与、,与是正交的．CompanyLogo三、最速下降法有关说明最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢．图4.3沿负梯度方向函数值下降很快的说法，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢．Com