共轭梯度法学时OK.ppt

这三个公式对应的共轭梯度法分别称为FR, DM 和 PRP算法. 4.一般函数的共轭梯度法 (4-32) 称为FR公式 (4-33) 称为DM公式 (4-34) 称为PRP公式 无约束问题4-4 四.共轭梯度法 共轭方向及其性质 二次函数共轭梯度法的迭代原理 二次函数共轭梯度法的迭代步骤 一般函数的共轭梯度法 PRP算法的迭代步骤 共轭梯度法的注释 无约束问题4-4 5.PRP算法的迭代步骤 无约束问题4-4 在PRP算法中,每n次迭代中的第一步取负梯度方向为其搜索方向,这种做法简称为“n步重新开始”.这是为了减少舍入误差的影响,加快收敛速度。 无约束问题4-4 5.PRP算法的迭代步骤 无约束问题4-4 四.共轭梯度法 共轭方向及其性质 二次函数共轭梯度法的迭代原理 二次函数共轭梯度法的迭代步骤 一般函数的共轭梯度法 PRP算法的迭代步骤 共轭梯度法的注释 无约束问题4-4 6.共轭梯度法的注释 结论： 是 f (X)在 X(k) 处的下降方向。 证明： 所以共轭梯度法对一般目标函数是下降算法， 因此共轭梯度法是收敛算法。 无约束问题4-4 6.共轭梯度法的注释 所以共轭梯度法对一般目标函数是下降算法， 因此共轭梯度法是收敛算法。 在PRP算法中,每n次迭代中的第一步取负梯度方向为其搜索方向,这种做法简称为“n步重新开始”.这是为了减少舍入误差的影响,加快收敛速度。 是 f (X)在 X(k) 处的下降方向。 无约束问题4-4 当 时，就变为最速下降法。 共轭梯度法优于最速下降法,但是非“n步重新开始”的共轭梯度法也仅仅具有线性收敛速度.对于“n步重新开始”的PRP的算法,可以证明它具有n步二阶收敛速度. 和Newton法相比较,共轭梯度法的另一个优点是:计算机存储量小，因为它不涉及矩阵，仅仅存放向量。所以它适于求解较高维的问题。 6.共轭梯度法的注释 所以共轭梯度法是最速下降法的一种改进算法。 无约束问题4-4 四.共轭梯度法 共轭方向及其性质 二次函数共轭梯度法的迭代原理 二次函数共轭梯度法的迭代步骤 一般函数的共轭梯度法 PRP算法的迭代步骤 共轭梯度法的注释 作业：P245 16 作业：P155 16 4.1 非线性规划数学模型 4.2 凸函数和凸规划 4.3 一维搜索 4.4 无约束优化问题的解法 第四章 无约束最优化问题 第四节 无约束优化问题的解法 最速下降法 Newton法 拟Newton法 共轭梯度法 第四章 无约束最优化问题 四.共轭梯度法 共轭方向及其性质 二次函数共轭梯度法的迭代原理 二次函数共轭梯度法的迭代步骤 一般函数的共轭梯度法 PRP算法的迭代步骤 共轭梯度法的注释 无约束问题4-4 则向量组 正交。 1.共轭方向及其性质 定义4-13 设Q是n阶对称正定矩阵，若向量组 满足： 则称该向量组Q共轭(Q正交)。 当 Q = E ,(4-24)就是通常的正交条件: 无约束问题4-4 解 。 经n次一维搜索收敛于 的最优 任意一点X(1)出发,依次以 为搜索方向的 1.共轭方向及其性质 定理4-14 分析： 共轭方向法具有二次终止性. 设 对于对称正定矩阵Q共轭，则从 下述算法： 结论： 无约束问题4-4 解 。 经n次一维搜索收敛于 的最优 任意一点X(1)出发,依次以 为搜索方向的 1.共轭方向及其性质 定理4-14 设 对于对称正定矩阵Q共轭，则从 下述算法： 推论： 则 g(k+1)与 的任意线性组合都正交。 无约束问题4-4 四.共轭梯度法 共轭方向及其性质 二次函数共轭梯度法的迭代原理 二次函数共轭梯度法的迭代步骤 一般函数的共轭梯度法 PRP算法的迭代步骤 共轭梯度法的注释 无约束问题4-4 2.二次函数共轭梯度法的迭代原理 求 的最优解X *。Q是对称正定矩阵。 无约束问题4-4 2.二次函数共轭梯度法的迭代原理 求 的最优解X *。Q是对称正定矩阵。 无约束问题4-4 2.二次函数共轭梯度法的迭代原理 求 的最优解X *。Q是对称正定矩阵。 已知 p(3)与p(2), p(2)与p(1)都Q共轭, p(3)与p(1)是否Q共轭? 无约束问题4-4 2.二次函数共轭梯度法的迭代原理 证明： p(3)与p(1)是否Q共轭 无约束问题4-4