1、 20XX 年度本科生毕业论文（设计） 一种修正的 PRP 共轭梯度法 院 系： 数学学院 专 业： 信息与计算科学 年 级： 学生姓名： 学 号： 导师及职称： 20XX 年 4 月 红河学院本科毕业论文（设计） 摘要 非线性共轭梯度算法是无约束优化问题中的一个重要组成部分，时常用来 解决一些大规模的无约束最优化问题本文提出一个修正的 PRP 共轭 梯度法， 并在广义的 Wolfe 线搜索下，证明了该算法的充分下降性和全局收敛性 . 关键词 ：共轭梯度法；充分下降；全局收敛性 红河学院本科毕业论文（设计） ABSTRACT The nonlinear conjugate gradient m
2、ethod ， which was used for solving unconstrained optimization problems ， is an important component of optimization methods In the paper ， the author proposed a modified PRP conjugate gradient method In the suitable conditions， the sufficient descent and global convergence can be proved Keywords： Con
3、jugate gradient method； The sufficient descent property； Global convergence 红河学院 本科毕业论文（设计） 目录 第一章 绪论 . 1 1.1 研究背景与意义 . 1 1.1.1 最优化问题 . 1 1.1.2 无约束最优化问题的解法 . 1 1.2 非精确线搜索 . . 2 1.3 经典的非线性共轭梯度法回顾 . 3 1.3.1 PRP 方法 . 3 1.3.2 CD 方法 . 3 1.3.3 FR 方法 . 3 1.3.4 HS 方法 . 3 1.3.5 DY 方法 . 4 第二章 一个修正 PRP 共轭梯度法的提
4、出 . 5 第三章 算法的充分下降性以及全局收敛性 . 6 3.1 算法的下降性分析 . 6 3.2 算法的全局收敛性分析 . 7 第四章 总结与展望 . 10 参考文献 . 11 致谢 . 12 红河学院本科毕业论文（设计） 第一章 绪论 1.1 研究背景与意义 1.1.1 最优化问题 最优化问题在生活中是一类很实用的问题，它是一门应用性 质很强的学科 , 在许多领域（如工程设计、化学、环境科学、生物科学等）有着广泛的应用最 优化理论与方法是计算科学的一个重要组成部分，实质上是一个求极值的问题如 今，其在工程设计与科学应用中无处不在，对发展科技起到非常大的作用本文 主要考虑求解无约束最优化问
5、题的共轭梯度法，用来求解某些问题的最优解，构 造寻求最优解的方法 最优化问题的数学模型一般如下 : min f x s.t ci x 0, i 1,2, , m. ci x 0, i m 1, , p. 其中 x x1 , x2 , , xn R n ， f : R n R , ci : R n R i 1,2 , P 是连续函数 ,一般还要求连续可微 , x 是决策变量， f (x) 为目标函数 ,ci x ,i 1,2, , p 是约束条件 ci x 0,i 1,2, , m 为等式约束 ， ci x 0,i m 1 , p 为不等式约束在 现实生活中，我们要将实际问题转化为数学模型，并且
6、用最优化算法求解 1.1.2 无约束最优化问题的解法 关于求解最优化问题，如果不考虑它的约束条件，就变成了求解无约束优化 问题目前，求 解无约束最优化问题的方法主要有牛顿法、拟牛顿法、最速下降 法、共轭梯度法等 牛顿法 1最初由艾萨克 牛顿于 1736 年在 Method of Fluxions 中公开提 出是一种经典的无约束最优化方法，牛顿法收敛速度非常快，具有二次收敛的 优点但是在使用牛顿法求解时，需要 2 f (xk ) 正定，否则 k 不一定是下降方 向且牛顿法方向构造困难，计算复杂，占用内存相当的大 拟牛顿法 (Quasi-Newton Methods) 1最初是由美国物理学家 W.
7、 C. Davidon 于 20 世纪 50 年代所提出，此算法具有收敛速度较快的优点，但在大规模问题上， 存储方面的开销是巨大的 1 第一章 绪论 最速下降法 1也称梯度下降法，大多数有效的算法都是以它为基础而得到 的，最速下降法是用负梯度方向为搜索方向的，最速下降法 (Steepest Descent Methods) 和拟牛顿法一样只需计算每一步迭代时目标函数的梯度但是，最速 下降法越接近目 标值，步长越小，前进越慢 共轭梯度法 1是共轭方向法中的一个典型的方法，它计算方便，易编程实现， 共轭梯度法只用它的梯度值和目标函数，从而降低了计算量和存储量因此，它 是求解无约束最优化问题的一种有
8、效又实用的方法共轭梯度法不要求精确的直 线搜索但是，不精确的直线搜索可能导致迭代出来的向量不再共轭，从而降低 方法的效能 1.2 非精确线搜索 (1) Armijo 线搜索 2： 给定 0,1 , 0,1 ，求 k max j , j 0,1,2 满足条件 f (xkk d k ) - f (xk )k g kT d k (1-1) (2) 强 Wolfe 线搜索 2： 求 k 满足条件 f (xkk dk ) - f (xk )k gkT dk ， (1-2) dkT g(xkk dk ) gkT dk (1-3) 其中 01 (3) 广义的 Wolfe 线搜索 2： 求 k 满足条件 f
9、(xkk dk ) f (xk )k gkT dk ， (1-4) 1 gkT dk g(xkk dk )T d k2 gkT dk (1-5) 这里 1 ( ,1) ， 2 0 (4) Wolfe 线搜索 2： 求 k 满足条件 f (xkk dk ) f (xk )k gkT dk ， (1-6) gkT dk g(xkk dk )T d k (1-7) (5) Goldshein 线搜索 3： 2 红河学院本科毕业论文（设计） 求 k 满足条件 g T d k f (x k k d k ) - f (x k ) 2 k g T d k ， (1-8) 1 k k k 其中 :0 2 12
10、 1 1 1.3 经典的非线性共轭梯度法回顾 一般的共轭梯度法形式如下： xk 1 xk k dk ， dk gk , k 1， gk k dk 1 , k 2 下面主要介绍几种经典非线性共轭梯度法，不同的 k 代表着不同的共轭梯 度法 1.3.1 PRP 方法 PRP 方法 4是 1969 年被 Polak 和 Ribieren 和 Polyakn 所提出，迄今为止是 被 认为数值表现最好的共轭梯度法之一，它的参数 kPRP 公式如下： PRP g T g k g k 1 k k gk 1 2 1.3.2 CD 方法 共轭下降法 4最早于 1987 年被 Fletcher 引入的，它的参数公
11、式如下： CD g k 2 k dkT 1 gk 1 1.3.3 FR 方法 FR 共轭梯度法 5最早于 1964 年被 Fletcher 和 Reeves 提出，它是最早的共轭 梯度算法，其参数 kFR 公式如下： kFR g k 22 gk 1 1.3.4 HS 方法 HS 共轭梯度法 6由 Hestenes-stiefel 提出，该算法和 PRP 算法有许多类似的 性质，并且计算效果也很不错，它的参数 kHS 公式如下： 3 第一章 绪论 HS g T g k 1 k k dkT gk 1 1.3.5 DY 方法 Dai 与 Yuan 于 1995 年提出了 DY 共轭梯度法 7，它的参
12、数 kDY 如下： DY g k 2 k dkT 1 yk 1 4 红河学院本科毕业论文（设计） 第二章 一个修正 PRP 共轭梯度法的提出 考虑无约束优化问题： min f (x) | x Rn (2-1) f : R n R 连续可微， f (x) 的梯度函数 f (x) 记为 g(x) ，共轭梯度法不仅算法简洁，并且存储需求小，其迭代公式为 xk 1xk k dk ， (2-2) dk gk , k 1， (2-3) , k 2 gkk dk 1 式中：为 k 搜索步长， f (x) 简记为 gk 本文的主要工作是构造一个新的参数 k ，从而构造一个新的搜索方向 dk ， 从新的搜索方向 dk 出发，提出一个修正的非线性共轭梯度法 新的参数 k 的计算公式如下 : gkT (gk g k gk 1 ) k gk 1 (2-4) gk 1 2 2.1 算法 步骤 1给出初始值 x1 R n ， 0 .令 d1 g1 ，若 g1 则停止 ,否则 k 1 ，转步骤 2 步骤 2.求出符合广义 Wolfe 线搜索的步长 k 0 步骤 3.令 xk 1 xk k dk , g k 1 g(xk 1 ) 若 g k 1 则停止否则转步骤 4 步骤 4.用式 (2-4)来计算 k ，用式 (2-3)来计算 dk 1 步骤 5.令 k : k 1 转步骤 2 5
