最优化方法第四次

最优化方法第四次第一页，共二十一页，编辑于2023年，星期三

6.牛顿法的缺陷。7.编写最速下降法程序。(建议用数学软件)第二页，共二十一页，编辑于2023年，星期三二、共轭梯度法1.共轭方向从前面已经看出，负梯度方向并不是理想的搜索方向，要提高算法的收敛速度，需要寻找其它搜索方向。为了给寻找搜索方向提供依据，我们先来考虑判断算法优劣的方法。二次函数是一种比较简单的函数，而一般的目标函数在极小点附近的性态又近似于二次函数，所以可以设想，一个算法如果对第三页，共二十一页，编辑于2023年，星期三于二次函数比较有效，就可望对于一般函数（至少在极小点附近）也有较好的效果。下面我们就从二次函数出发，寻找比较有效的搜索方向。

第四页，共二十一页，编辑于2023年，星期三考虑正定二次函数

由于A为正定矩阵，从而函数的等值线为平面上的一簇椭圆。第五页，共二十一页，编辑于2023年，星期三显然，如果椭圆非常狭长，则最速下降法锯齿形迭代的步长越来越小。能否找到理想的搜索方向，使算法用最短的迭代找到极小点呢？下面的分析告诉我们，对于只包含两个变量的正定二次函数，最多只要两次迭代即可找到极小点。在初始点处，取负梯度方向为搜索方向，即，沿下降至处。假设在处，选择适当的搜索方向,沿即第六页，共二十一页，编辑于2023年，星期三可直接找到极小点，即有,使。由最优性条件，即，代入得，，亦即。用乘上式后得到。由最速下降法知，，从而。第七页，共二十一页，编辑于2023年，星期三因为与正交，当然线性无关，从而它们构成二维平面的基底，故可表示为它们的线性组合，用左乘上式得，考虑到，得

从而第八页，共二十一页，编辑于2023年，星期三定义2.1设为中的k个非零向量，A为n阶正定矩阵。若对任意均有，则称关于A两两共轭。当A为单位矩阵时，意味着两两正交，所以共轭是正交的推广。第九页，共二十一页，编辑于2023年，星期三定理2.2设A为n阶正定矩阵，若关于A两两共轭，则是线性无关的。证设有，使得用左乘上式，得因为A正定，，得，即线性无关。第十页，共二十一页，编辑于2023年，星期三2.n元正定二次函数的共轭梯度法对n元正定二次函数有下面两个重要定理。定理2.3对n元正定二次函数设关于A两两共轭。从任意初始点出发，依次沿方向执行一维搜索到，第十一页，共二十一页，编辑于2023年，星期三则垂直于前面所有的搜索方向，即

定理2.4：对n元正定二次函数

设关于A两两共轭。从任意初始点出发，依次沿执行一维搜索到，则即为极小点。第十二页，共二十一页，编辑于2023年，星期三2.正定二次函数的共轭梯度法仿照与的关系，我们构造下列搜索方向，据此可证明定理2.5。第十三页，共二十一页，编辑于2023年，星期三定理2.5：对n元正定二次函数从任意初始点出发，依次按上述搜索方向经次迭代下降至，即则即为极小点。如果一个算法能用有限步求出二次函数的极小点（从理论上说），则称这个算法具有二阶收敛性或有限步收敛性。第十四页，共二十一页，编辑于2023年，星期三3.一般函数的共轭梯度法对于一般函数，已无正定矩阵A和共轭的概念，因此必须寻求一种与共轭方向表达式等价的形式，其中不含有矩阵A。由，得从而第十五页，共二十一页，编辑于2023年，星期三又故最终第十六页，共二十一页，编辑于2023年，星期三综上所述，对于一般目标函数，可按下述规则确定搜索方向：此方法称为F-R(Fletcher-Reeves)共轭梯度法。第十七页，共二十一页，编辑于2023年，星期三§3.拟牛顿法一、牛顿法最速下降法的本质是用线性函数逼近目标函数。因此，要想得到快速算法，需要考虑用高次函数逼近。如果采用二次多项式逼近，则称为牛顿法。在给定点附近将展为二阶Taylor展式，即第十八页，共二十一页，编辑于2023年，星期三记，则。若正定，则为凸函数,有惟一极小点,满足，即，。记，则,称之为牛顿迭代，称为牛顿方向。牛顿迭代可以理解为从出发，沿牛顿方向取步长。显然，对正定二次函数,从任意初始点出发，牛顿迭代一步即可达到第十九页，共二十一页，编辑于2023年，星期三最小点。理论分析表明，当初始点离较近时，牛顿迭代法能以二阶速度收敛到。但当离较远时，牛顿迭代可能不收敛，甚至迭代过程无法进行，原因如下：①若为奇异阵，无意义，迭代无法进行；②即使非奇异，但不一定正定，从而不能保证，即牛顿方向第二十页，共二十一页，编辑于2023年，星期三不一定是下降方向；③即使