《[理学]第5章 常用无约束最优化方法》由会员分享，可在线阅读，更多相关《[理学]第5章 常用无约束最优化方法（88页珍藏版）》请在金锄头文库上搜索。
1、第五章 常用无约束最优化方法,本章开始讨论多维无约束最优化问题（5.1）其中 这个问题的求解是指，在 中找一点 ，使得对于任意的都有 （5.2）成立，则点 就是问题（5.1）的全局最优点但是，大多数最优化方法只能求到局部最优点，即在 中找到一点 ，使得式（5.2）在 的某个领域中成立这个矛盾对于实际问题一般容易解决根据问题的实际意义多半可以判定用优化方法求出的局部最优解是否为全局最优解而在理论上这是个比较复杂的问题，本书不涉及,无约束优化方法是优化技术中极为重要和基本的内容之一它不仅可以直接用来求解无约束优化问题，而且很多约束优化问题也常将其转化为无约束优化问题，然后用无约束优化方法来求解另外
2、，有些无约束优化方法只需略加处理，即可用于求解约束优化问题无约束优化理论发展较早，比较成熟，方法也很多，新的方法还在陆续出现把这些方法归纳起来可以分成两大类：一类是仅用计算函数值所得到的信息来确定搜索方向，通常称它为直接搜索法，简称为直接法，另一类需要计算函数的一阶或二阶导数值所得到的信息来确定搜索方向，这一类方法称为间接法（解析法）直接法不涉及导数、Hesse矩阵，适应性强，但收敛速度较慢；间接法收敛速度快，但需计算梯度，甚至需要计算Hesse矩阵一般的经验是，在可能求得目标函数导数的情况下还是尽可能使用间接方法；相反，在不可能求得目标函数的导数或根本不存在导数的情况下，当然就应该使用直接法
3、,对于问题（5.1）为了求其最优解，按最优化算法的基本思想是从一个给定的初始点 出发，通过基本迭代格式 ，按照特定的算法 产生一串点列 ，如果点列收敛，则该点列的极限点为问题（5.1）的最优解 在基本迭代格式 中，每次迭代搜索方向 取为目标函数 的负梯度方向，即 ，而每次迭代的步长 取为最优步长，由此所确定的算法 称为最速下降法为了求解问题（5.1），如图5.1所示，假定我们 已经迭代了 次，获得了第 个迭代点 现在从 出发，可选择的下降方向很多，一个非常自然的想法是沿最速下降方向（即负梯度方向）进行搜索应该是有利的，至少在 邻近的范围内是这样。因此，取搜索方向为 。,5.1 最速下降法,为了
4、使目标函数在搜索方向上获得最多的下降，沿 进行一维搜索，由此得到第 个迭代点，即 ，其中步长因子 按下式确定也可记为 （5.3）显然，令 就可以得到一个点列 ，其中 是初始点，由计算者任意选定当 满足一定的条件时，由式（5.3）所产生的点列 必收敛于的极小点以后为书写方便，记 因此，在不发生混淆时，再记 ,二、最速下降法迭代步骤已知目标函数 及其梯度 ，终止限 、 和 （1）选定初始点 ，计算 ， ；置 （2）作直线搜索： ；计算 （3）用终止准则检测是否满足：若满足，则打印最优解 ， 停机；否则，置 转（2）最速下降法算法流程如图5.2所示将最速下降法应用于正定二次函数 （5.4） 可以推出
5、显式迭代公式 设第 次迭代点为 ，我们来求 的表达式 对式（5.4）关于 求梯度，有（5.5） 因此， （5.6）,现在从 出发沿 作直线搜索以确定 ，于是，（5.7） 其中 是最优步长因子又因式（4.2），有 ，再利用（5.5），（5.6）和（5.7）可得：或 ，由此解出： 代入（5.7）中得到，（5.8） 这就是最速下降法用于二次函数的显式迭代公式,例5.1试用最速下降法求函数 的极小点迭代两次，计算各迭代点的函数值，梯度及其模，并验证相邻两个搜索方向是正交的设初始点为 ,解 与（5.4）比较，得 梯度表达式是由 ，计算出 因为目标函数是二次的，可以使用式（5.8），所以 有,因为 由此说
6、明相邻两个搜索方向 与 、 与 是正交的,计算,三、最速下降法有关说明,沿负梯度方向函数值下降很快的廉洁，容易使人们产生一种错觉，认为这一定是最理想的搜索方向，沿该方向搜索时收敛速度应该很快，然而事实证明，梯度法的收敛速度并不快特别是对于等值线（面）具有狭长深谷形状的函数，收敛速度更慢其原因是由于每次迭代后下一次搜索方向总是与前一次搜索方向相互垂直，如此继续下去就产生所谓的锯齿现象即从直观上看，在远离极小点的地方每次迭代可能使目标函数有较大的下降，但是在接近极小点的地方，由于锯齿现象，从而导致每次迭代行进距离缩短，因而收敛速度不快（如图5.3所示）,最速下降法的优点是算法简单，每次迭代计算量小
7、，占用内存量小，即使从一个不好的初始点出发，往往也能收敛到局部极小点，但它有一个严重缺点就是收敛速度慢,5.2 Newton法,如果目标函数 在 上具有连续的二阶偏导数，其Hesse矩阵 正定并且可以表达成为显式（今后为了简便起见，记 ，那么可以使用下述的Newton法这种方法一旦好用，收敛速度是很快的它是一维搜索Newton切线法的推广,一、Newton法基本原理为寻求收敛速度快的算法，我们考虑在应用基本迭代公式 中，每轮迭代在迭代的起始点 处用一个适当的二次函数来近似该点处的目标函数，由此用该点 指向近似二次函数极小点的方向来构造搜索方向 （如图5.4所示）,下面具体讨论Newton法设最
8、优化问题为 ，其中 二阶可导， Hesse矩阵 正定 不妨设经过 次迭代已获点 ，现将 在 处展 成二阶泰勒公式，于是有显然 是二次函数，特别由题设知 还是正定二次函 数，所以 是凸函数且存在唯一全局极小点为求此极小 点，令 即可解得 亦即 （5.9）,对照基本迭代格式易知，式（5.9）中的搜索方向步长因子 换句话说从点 出发沿搜索方向并取步长 即可得 的极小点 因此，是直指点 处近似二次函数 的极小点的方向此时称为从点 出发的Newton方向从初始点开始，每一轮从前当 迭代点出发，沿Newton方向并取步长 的算法称为 Newton法,二、Newton法迭代步骤,已知目标函数 及其梯度 ，H
9、esse矩阵 ，终止限 （1）选定初始点 ；计算 置 （2）计算 （3）由方程 解出 （4）计算（5）判别终止准则是否满足：若满足，则打印最优解 ， 停机；否则，置 ，转（2）Newton法的流程如图5.5所示,例5.2 试用Newton法求 的极小点，初始点取为 解 梯度为 ，Hesse矩阵为其 逆矩阵为由迭代公式（5.13）得第1 迭代点为由于此时 ，停止迭得因此，它就是极小点,从上述例5.2我们看到，用Newton法求解，只经一轮迭代就得到最优解这一结果并不是偶然的，因为从Newton方向的构造我们知道，对于正定二次函数，Newon方向就是指向其极小点的方向因此，用Newton法解目标函数为正定二次函数的无约束最优化问题，只需一次迭代就可得最优解对于目标函数是非二次函数的非约束最优化问题，一般地说，用Newton法通过有限轮迭代并不能保证可求得最优解但由于目标函数在最优解附近能近似于二次函数，因此当先取接近于最优解的初始点使用Newton法求解时，其收敛速度一般是快的事实上，可以证明在初始点离最优解不远的条件下，Newton法是二次收敛的但是当初始点选得离最优解太远时，Newton法并不一定是收敛的方法，甚至连其下降性也很难保证,
