最优化方法第四次精品文稿.ppt

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

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

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

3、 关，从而 它 们 构 成 二 维 平 面 的 基 底，故 可 表 示 为它们的线性组合，用左乘上式得，考虑到，得 从而 第8 页，本讲稿共21 页 定 义2.1 设 为 中 的k个非 零 向 量，A 为n阶 正 定 矩 阵。若 对 任 意 均有，则称 关于A 两两共轭。当A 为单位矩阵时，意味着 两两正交，所以共轭是正交的推广。第9 页，本讲稿共21 页 定理2.2 设A 为n阶正定矩阵，若 关于A 两两共轭，则 是线性无关的。证 设有，使得用 左乘上式，得因为A 正定，得，即线性无关。第10 页，本讲稿共21 页 2.n 元正定二次函数的共轭梯度法 对n元 正 定 二 次 函 数 有 下

4、面 两 个 重 要 定理。定理2.3 对n元正定二次函数 设 关 于A 两 两 共 轭。从 任 意 初 始点 出 发，依 次 沿 方 向 执 行 一 维 搜 索到，第1 1 页，本讲稿共21 页则 垂直于前面所有的搜索方向，即 定理2.4：对n元正定二次函数 设 关于A 两两共轭。从任意初始点 出发，依次沿 执行一维搜索到，则 即为极小点。第12 页，本讲稿共21 页 2.正定二次函数的共轭梯度法 仿 照 与 的 关 系，我 们 构 造 下 列 搜 索 方向，据此可证明定理2.5。第13 页，本讲稿共21 页 定理2.5：对n元正定二次函数 从 任 意 初 始 点 出 发，依 次 按 上 述

5、搜 索 方 向经次迭代下降至，即则 即为极小点。如 果 一 个 算 法 能 用 有 限 步 求 出 二 次 函数 的 极 小 点（从 理 论 上 说），则 称 这 个 算法具有二阶收敛性或有限步收敛性。第14 页，本讲稿共21 页 3.一般函数的共轭梯度法 对 于 一 般 函 数，已 无 正 定 矩 阵A 和 共轭 的 概 念，因 此 必 须 寻 求 一 种 与 共 轭 方 向表达式等价的形式，其中不含有矩阵A。由，得从而第15 页，本讲稿共21 页又故最终 第16 页，本讲稿共21 页 综上所述，对于一般目标函数，可按下述规则确定搜索方向：此方法称为F-R(Fletcher-Reeves)共

6、轭梯度法。第17 页，本讲稿共21 页3.拟牛顿法 一、牛顿法 最速下降法的本质是用线性函数逼近目标函数。因此，要想得到快速算法，需要考虑用高次函数逼近。如果采用二次多项式逼近，则称为牛顿法。在给定点 附近将 展为二阶Taylor 展式，即 第18 页，本讲稿共21 页 记，则。若 正定，则 为凸函数,有惟一极小点,满足，即，。记，则,称之为牛顿迭代，称为牛顿方向。牛顿迭代可以理解为从 出发，沿牛顿方向 取步长。显然，对正定二次函数,从任意初始点出发，牛顿迭代一步即可达到第19 页，本讲稿共21 页最小点。理论分析表明，当初始点 离 较近时，牛顿迭代法能以二阶速度收敛到。但当 离 较远时，牛顿迭代可能不收敛，甚至迭代过程无法进行，原因如下：若 为奇异阵，无意义，迭代无法进行；即使 非奇异，但 不一定正定，从而不能保证，即牛顿方向 第20 页，本讲稿共21 页 不一定是下降方向；即使 正定，是下降方向，但牛顿迭代取步长，也不能保证。其 实，即 便 牛 顿 迭 代 可 以 正 常 进 行 且 收敛，但 由 于 它 在 每 次 迭 代 时 要 计 算 Hesse 矩 阵及 其 逆，从 而 得 出 迭 代 方 向，这 使 得 每 次 迭代 的 计 算 量 太 大，大 大 降 低 了 牛 顿 迭 代 的 实用性。第21 页，本讲稿共21 页