本文将介绍 PRP 共轭梯度法，我们又进入崭新的一页。方法的全局收敛性证明会有点难，所以在 1969 年提出 PRP 共轭梯度法，却在 1992 年才证明其全局收敛性。

1、引言

  PRP 共轭梯度法是由 Polak 和 Ribiere 和 Polyak在 1969 年独立提出的一种非线性共轭梯度法，这种方法具有如下形式：


其中参数由以下公式计算：

PRP 共轭梯度法的全程为 Polak-Pibiere-Polyak 共轭梯度法，以后我们只说其简称。
   PRP 共轭梯度法是目前认为数值表现最好的共轭梯度法之一。当算法产生一个小步长时，由 PRP 方法定义的搜索方向自动地靠近负梯度方向，从而有效地避免 FR 共轭梯度法可能连续产生小步长的缺点。基于此， Powell 在文献 中证明了当步长趋于零时 PRP 方法的全局收敛性。利用文献 中的结果即知采取精确线搜索的 PRP 方法对一致凸函数的全局收敛性。但是对于一般非凸函数，Powell 在文献 中举出了三维反列，表明即使按原则选取步长因子，即取为一维函数的第一个极小点，PRP 方法可能在六点附近循环，而其中任意一点都不是目标函数的稳定点。

2、精确线搜索下 PRP 方法的性质

  如果采取精确线搜索，即

则有以下关系式


利用 (3) 式。显然有

利用 (5)、(6) 和 (7)，有

故如果，并且导致步长非常小，以及，则由 (8) 式可知，

从而下一步的搜素方向将自动靠近负梯度方向。可见 PRP 方法当产生一个小步长时，具有自动地接近最速下降法的优点，从而有效地避免 FR 方法可能连续产生小步长的缺陷。到目前为止， PRP 方法仍被认为是数值表现最好的共轭梯度法之一。

定理 1：设目标函数下方有界，导数连续，考虑 PRP 共轭梯度法 (1)-(3)，其中步长因子由精确线搜索 (4) 求出，如果当，，则必有

证明：设定理不真，则存在常数，使得

由导数的连续性和步长趋于零知，存在正整数，使得

对所有的成立。注意对所有的，有

可以由 (8)、(12) 和 (13) 推出

故搜索方向与负梯度方向的夹角总小于某个小于的角度。由条件可知，。这与 (11) 相矛盾，从而 (10) 成立。

  若满足精确线搜索 (4)，或满足

袁亚湘对一致凸函数给出了如下函数下降量的估计式：

其中为常数。故当，必有，于是由 定理 1 可知，采取精确线搜索的 PRP 方法对一致凸函数是全局收敛的。

定理 2：设目标函数为一致凸函数，即存在常数，使得

对任何均成立，考虑 PRP 方法 (1)-(3)，其中步长因子由精确线搜索 (4) 求出，则必有 (10) 成立。

3、参考文献

[1] Polak E, Ribière G. Note surla convergence de directions conjugèes[J]. Rev Francaise Informat Recherche Operationelle, 1969, 3(16): 35--43.
[2] Polyak B T. The conjugate gradient method in extreme problems[J]. USSR Computational Mathematic and Mathematical Physics, 1969, 9(4): 94--112.
[3] Powell M J D. Restart procedures of the conjugate gradient method[J]. Math Program, 1977, 2: 241-254.
[4] 袁亚湘, 孙文喻. 最优化理论与方法[M].
[5] Powell M J D. Nonconvex minimization calculations and the conjugate gradient method. in: Lecture Notes in Mathematics vol 1066, Berlin: Springer-Verlag, 1984, 122~141.