最优化方法第四次幻灯片.ppt

《最优化方法第四次幻灯片.ppt》由会员分享，可在线阅读，更多相关《最优化方法第四次幻灯片.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、们就从二次函数出发，寻找比较有效的搜索方向。第4页，共21页，编辑于2022年，星期六 考虑正定二次函数 由于A为正定矩阵，从而函数的等值线为平 面上的一簇椭圆。第5页，共21页，编辑于2022年，星期六 显然，如果椭圆非常狭长，则最速下降法锯齿形迭代的步长越来越小。能否找到理想的搜索方向，使算法用最短的迭代找到极小点呢？下面的分析告诉我们，对于只包含两个变量的正定二次函数，最多只要两次迭代即可找到极小点。在初始点 处，取负梯度方向为搜索方向，即 ，沿 下降至 处。假设在 处，选择适当的搜索方向 ,沿 即 第6页，共21页，编辑于2022年，星期六可直接找到极小点 ，即有 ,使 。由最优性条件

3、 ，即 ，代入得 ，亦即 。用 乘上式后得到 。由最速下降法知，从而 。第7页，共21页，编辑于2022年，星期六 因为 与 正交，当然线性无关，从而它们构成二维平面的基底，故 可表示为它们的线性组合 ，用左乘上式得 ，考虑到 ，得 从而 第8页，共21页，编辑于2022年，星期六 定定义义2.1 设 为 中的k个非零向量，A为n阶正定矩阵。若对任意 均有 ，则称 关于A两两共轭。当A为单位矩阵时，意味着 两两正交，所以共轭是正交的推广。第9页，共21页，编辑于2022年，星期六 定理定理2.2 设A为n阶正定矩阵，若 关于A两两共轭，则 是线性无关的。证 设有 ，使得用 左乘上式，得因为A正

4、定，得 ，即线性无关。第10页，共21页，编辑于2022年，星期六 2.n元正定二次函数的共轭梯度法元正定二次函数的共轭梯度法 对n元正定二次函数有下面两个重要定理。定理定理2.3 对n元正定二次函数 设 关于A两两共轭。从任意初始点 出发，依次沿方向 执行一维搜索到 ，第11页，共21页，编辑于2022年，星期六则 垂直于前面所有的搜索方向，即 定理定理2.4：对n元正定二次函数 设 关于A两两共轭。从任意初始点 出发，依次沿 执行一维搜索到 ，则 即为极小点。第12页，共21页，编辑于2022年，星期六 2.正定二次函数的共轭梯度法正定二次函数的共轭梯度法 仿照 与 的关系，我们构造下列搜

5、索方向，据此可证明定理2.5。第13页，共21页，编辑于2022年，星期六 定理定理2.5：对n元正定二次函数 从任意初始点 出发，依次按上述搜索方向经次迭代下降至 ，即则 即为极小点。如果一个算法能用有限步求出二次函数的极小点（从理论上说），则称这个算法具有二阶收敛性或有限步收敛性。第14页，共21页，编辑于2022年，星期六 3.一般函数的共轭梯度法一般函数的共轭梯度法 对于一般函数，已无正定矩阵A和共轭的概念，因此必须寻求一种与共轭方向表达式等价的形式，其中不含有矩阵A。由 ，得从而第15页，共21页，编辑于2022年，星期六又故最终 第16页，共21页，编辑于2022年，星期六 综上所

6、述，对于一般目标函数，可按下述规则确定搜索方向：此方法称为F-R(Fletcher-Reeves)共轭梯度法。第17页，共21页，编辑于2022年，星期六3.拟牛顿法拟牛顿法 一、牛顿法一、牛顿法 最速下降法的本质是用线性函数逼近目标函数。因此，要想得到快速算法，需要考虑用高次函数逼近。如果采用二次多项式逼近，则称为牛顿法。在给定点 附近将 展为二阶Taylor展式，即 第18页，共21页，编辑于2022年，星期六 记 ，则 。若 正定，则 为凸函数,有惟一极小点,满足 ，即 ，。记 ，则 ,称之为牛顿迭代，称为牛顿方向。牛顿迭代可以理解为从 出发，沿牛顿方向 取步长 。显然，对正定二次函数,

7、从任意初始点出发，牛顿迭代一步即可达到第19页，共21页，编辑于2022年，星期六最小点。理论分析表明，当初始点 离 较近时，牛顿迭代法能以二阶速度收敛到 。但当 离 较远时，牛顿迭代可能不收敛，甚至迭代过程无法进行，原因如下：若 为奇异阵，无意义，迭代无法进行；即使 非奇异，但 不一定正定，从而不能保证 ，即牛顿方向 第20页，共21页，编辑于2022年，星期六 不一定是下降方向；即使 正定，是下降方向，但牛顿迭代取步长 ，也不能保证 。其实，即便牛顿迭代可以正常进行且收敛，但由于它在每次迭代时要计算 Hesse矩 阵及其逆，从而得出迭代方向，这使得每次迭代的计算量太大，大大降低了牛顿迭代的实用性。第21页，共21页，编辑于2022年，星期六