最优化方法刘.ppt

问题提出 最速下降法算法 收敛性分析 收敛性分析 最速下降法优点 最速下降法缺点 小结 基本思想 算法构造 牛顿法算法 牛顿法收敛定理 牛顿法优点 牛顿法缺点 阻尼牛顿法算法 阻尼牛顿法收敛定理 阻尼牛顿法收敛定理 带保护的牛顿法算法 Gill-Murray稳定牛顿法 算法特点 共轭方向及其性质 共轭方向法算法 共轭方向法基本定理 共轭梯度法 共轭梯度法基本性质 系数的其他形式 FR共轭梯度法算法 FR共轭梯度法收敛定理 再开始FR共轭梯度法算法 作业：FR共轭梯度法（上机） 基本思想 算法原理 拟牛顿算法 DFP校正公式 　DFP校正公式的正定继承性 　DFP算法的二次终止性 BFGS校正公式 对称秩一校正公式 Broyden族 Broyden族算法性质 作　业 注: （１）DFP算法具有二次终止性． （２）搜索方向是共轭方向： 引理2: 设 为 正定阵， 且 则： 为正定阵的充要条件是 定理5: 在DFP算法中， 如果 正定， 则整个矩阵列 都正定． 推论: 在上面定理条件下： （1） DFP算法至多经过 次迭代就可得到极 小点，即存在 有： （2） 若 则 问题1: 如何建立有效的算法？ 从二次模型到一般模型 问题2: 什么样的算法有效呢？ 二次终止性 § 4.3 共轭方向法 与共轭梯度法 （１）建立在二次模型上，具有二次终止性． （２）有效的算法，克服了最速下降法的慢 收敛性，又避免了牛顿法的计算量大和局部收 性的缺点． （３）算法简单，易于编程，需存储空间小等 优点，是求解大规模问题的主要方法． 定义1: 设 是 中任一组 非零向量， 如果： 则称 是关于 共轭的． 注： 若 则是正交的，因此共轭是 正交的推广． 定理1: 设 为 阶正定阵， 非零向量组 关于 共轭， 则必线性无关． 推论1: 设 为 阶正定阵， 非零向量组 关于 共轭， 则向量构成 的一组基． 推论2: 设 为 阶正定阵， 非零向量组 关于 共轭， 若向量 与 关于 共轭， 则 Step1: 给出 计算 和初始下降方向 Step2: 如果 停止迭代． Step3: 计算 使得 Step4: 采用某种共轭方向法计算 使得： Step5: 令 转Step2. 定义2: 设 维向量组 线性无关， 向量集合 为 与 生成的 维超平面． 引理1: 设 是连续可微的严格凸函数， 维向量组 线性无关， 则： 是 在 上 唯一极小点的充要条件是： 证： 构造： 分析： 是 (1) 维严格凸函数． (2) 是 在 上的极小点的 充要条件是 是 在 上的极小点． 定理2: 设 为 阶正定阵， 向量组 关于 共轭， 对正定二次函数 由任意 开始， 依次进行 次精确线搜索： 则： （１） （２） 是 在 上的极小点． 推论: 当 时， 为正定二次函数在 上的极小点． 记： 左乘 并使 得： （Hestenes-Stiefel公式） 取： 定理3: 对于正定二次函数， 采用精确线搜索 的共轭梯度法在 步后终止， 且对 成立下列关系式： （共轭性） （正交性） （下降条件） （１）FR公式 （1964） （2）PRP公式 （1969） Step1: 给出 Step2: 计算 如果 停． Step3: Step4: 由精确线搜索求 Step5: 转Step2. 例4： 用FR共轭梯度法求解： 解： 化成 形式 (1) (2) 例5： 用FR共轭梯度法求解： 解： 化成 形式 (1) (2) 定理4: 假定 在有界水平集 上连续可微， 且有下界， 那么采用精确线搜索下的 FR共轭梯度法产生的点列 至少有一个聚点 是驻点，即： (1) 当 是有穷点列时， 其最后一个点是 的驻点． (2) 当 是无穷点列时， 它必有聚点， 且任一 聚点都是 的驻点． Step1: 给出 Step2: 计算 如果 停， Step4: 否则 Step3: 由精确线搜索求 并令： 计算 若 令 转Step2; 如果 停. Step5: 若 令 转step2. Step6: 计算 Step7: 如果 令 转step2, 否则 转step3. 上机实现FR共轭梯度法． 并求解Rosenbrock函数， 初始点选 线搜索分别采用黄金分割法与强Wolfe线 搜索，并对比． § 4.4 拟牛顿法 本质上是基于逼近牛顿法的方法． 牛顿法每次都计算 1959年,Davidon提出 设想仅用每次迭代中得到的梯度信息来近似海 色阵，基于此导致了一类非常成功的拟牛顿法． 本节介绍Broyden族拟牛顿法： DFP算法和BFGS算法． 最速下降法和阻尼牛顿法的迭代公式可统一为： 思考： 要使上面的算法比最速下降法快，比牛顿 法计算简单，且整体收敛性好，关键在于构造 矩阵列 要求： 的选取既能逐步逼近 又无需计算 二阶导数， 且