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

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

1、第五章常用无约束最优化方法本章开始讨论多维无约束最优化问题（5.1）其中．这个问题的求解是指，在中找一点，使得对于任意的都有（5.2）成立，则点就是问题（5.1）的全局最优点．但是，大多数最优化方法只能求到局部最优点，即在中找到一点，使得式（5.2）在的某个领域中成立．这个矛盾对于实际问题一般容易解决．根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解．而在理论上这是个比较复杂的问题，本书不涉及．无约束优化方法是优化技术中极为重要和基本的内容之一．它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后

2、用无约束优化方法来求解．另外，有些无约束优化方法只需略加处理，即可用于求解约束优化问题．无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现．把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（解析法）．直接法不涉及导数、Hesse矩阵，适应性强，但收敛速度较慢；间接法收敛速度快，但需计算梯度，甚至需要计算Hesse矩阵．一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在

3、不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法．对于问题（5.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点出发，通过基本迭代格式，按照特定的算法产生一串点列，如果点列收敛，则该点列的极限点为问题（5.1）的最优解．在基本迭代格式中，每次迭代搜索方向取为目标函数的负梯度方向，即，而每次迭代的步长取为最优步长，由此所确定的算法称为最速下降法．为了求解问题（5.1），如图5.1所示，假定我们已经迭代了次，获得了第个迭代点．现在从出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的

4、，至少在邻近的范围内是这样。因此，取搜索方向为。§5.1最速下降法为了使目标函数在搜索方向上获得最多的下降，沿进行一维搜索，由此得到第个迭代点，即，其中步长因子按下式确定也可记为（5.3）显然，令就可以得到一个点列，其中是初始点，由计算者任意选定．当满足一定的条件时，由式（5.3）所产生的点列必收敛于的极小点．以后为书写方便，记．因此，在不发生混淆时，再记．二、最速下降法迭代步骤已知目标函数及其梯度，终止限、和．（1）选定初始点，计算，；置．（2）作直线搜索：；计算．（3）用终止准则检测是否满足：若满足，则打印最优解，停机；否则，置转（2）．最速下降法算法流程

5、如图5.2所示．将最速下降法应用于正定二次函数（5.4）可以推出显式迭代公式．设第次迭代点为，我们来求的表达式．对式（5.4）关于求梯度，有（5.5）因此，（5.6）现在从出发沿作直线搜索以确定，于是，（5.7）其中是最优步长因子．又因式（4.2），有，再利用（5.5），（5.6）和（5.7）可得：或，由此解出：代入（5.7）中得到，（5.8）这就是最速下降法用于二次函数的显式迭代公式．例5.1试用最速下降法求函数的极小点．迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的．设初始点为．解与（5.4）比较，得梯度表达式是由，计算出因为目

6、标函数是二次的，可以使用式（5.8），所以有因为由此说明相邻两个搜索方向与、与是正交的．计算三、最速下降法有关说明沿负梯度方向函数值下降很快的廉洁，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快．特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢．其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象．即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短

7、，因而收敛速度不快（如图5.3所示）．最速下降法的优点是算法简单，每次迭代计算量小，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢．§5.2Newton法如果目标函数在上具有连续的二阶偏导数，其Hesse矩阵正定并且可以表达成为显式（今后为了简便起见，记，那么可以使用下述的Newton法．这种方法一旦好用，收敛速度是很快的．它是一维搜索Newton切线法的推广．一、Newton法基本原理为寻求收敛速度快的算法，我们考虑在应用基本迭代公式中，每轮迭代在迭代的起始点处用一个适当的二次函数来近似该点处的目标函数，

8、由此用该点指向近似二次函数极小点的方向