在~)
节，我们证明了
方法的收敛性。然而，即使~)
是一致凸函数，参数
也可能非负。在~)
节，我们知道采取精确线搜索的
方法对于一致凸函数的全局收敛性。于是，
和![~\rm{Lucidi}^{[1]}~](https://math.jianshu.com/math?formula=~%5Crm%7BLucidi%7D%5E%7B%5B1%5D%7D~)
致力于寻找这样的一种线搜索，以确保原始方法的收敛性。他们提出了一种
线搜索，并证明了在该线搜索下，原始方法对一般非凸函数的收敛性。
1、引言
PRP 共轭梯度法是由 Polak 和 Ribiere 和 Polyak 在 1969 年独立提出的一种非线性共轭梯度法，这种方法具有如下形式：
其中参数
由以下公式计算：
%7D%7B%5CVert%20g_%7Bk-1%7D%5CVert%5E2%7D.%5Ctag%7B3%7D)
和
提出的线搜索与下述条件密切相关：
%5Cle%20f(x_k)-%5Crho%5Calpha_k%5E2%5CVert%20d_k%5CVert%5E2%2C%5Ctag%7B4%7D)
其中
为常数。线搜索条件~)
由
等学者在考虑无约束优化的无导数方法时引入的，详见文献![{[2]}](https://math.jianshu.com/math?formula=%7B%5B2%5D%7D)
，与下式相比
%5Cle%20f(x_k)%2B%5Crho%5Calpha_k%20g_k%5ET%20d_k%2C%5Ctag%7B5%7D)
相比，)
当
大时，要求目标函数有较大的下降量，而当小时， 比)
更容易满足。
具体地，给定常数~)
，
和 
的线搜索的基本思想是计算
使得
和
满足 以及
其中
为事先给定的常数。下述引理表明，当满足一定条件时，确实存在这样的步长因子
，使得 和 )
成立，而且这样的步长因子不会太小。
2、收敛性分析
引理 1： 设函数 下方有界，导数
连续可微。考虑方法-(3)~)
，其中步长因子由 和 线搜索确定。则对于每个
，必存在这样的
，使得线搜索条件 和 成立。进一步地，存在常数
，使得
对所有
成立。
因为
，故
对
成立。设~)
对某成立。对任意的，定义和，记
%7D%7BL%20c_2%7D%3E0%5Ctag%7B10%7D)
利用连续和归纳假设，对任意的~)
，
故有
%5Ctag%7B12%7D)
另一方面，由中值定理及导数的连续性知
![\begin{align}f(x_{k+1})-f(x_k)&=\int_0^1g(x_k+t\alpha_k d_k)^T(\alpha_k d_k)\rm{d}\\ &=\alpha_k g_k^T d_k+\int_0^1[g(x_k+t\alpha_k d_k)-g_k]^T(\alpha_k d_k)\rm{dt}\\ &\le\alpha_k g_k^T d_k+\frac{1}{2}L\alpha_k^2\Vert d_k\Vert^2\end{align}\tag{13}](https://math.jianshu.com/math?formula=%5Cbegin%7Balign%7Df(x_%7Bk%2B1%7D)-f(x_k)%26%3D%5Cint_0%5E1g(x_k%2Bt%5Calpha_k%20d_k)%5ET(%5Calpha_k%20d_k)%5Crm%7Bd%7D%5C%5C%20%26%3D%5Calpha_k%20g_k%5ET%20d_k%2B%5Cint_0%5E1%5Bg(x_k%2Bt%5Calpha_k%20d_k)-g_k%5D%5ET(%5Calpha_k%20d_k)%5Crm%7Bdt%7D%5C%5C%20%26%5Cle%5Calpha_k%20g_k%5ET%20d_k%2B%5Cfrac%7B1%7D%7B2%7DL%5Calpha_k%5E2%5CVert%20d_k%5CVert%5E2%5Cend%7Balign%7D%5Ctag%7B13%7D)
于是
-f(x_k)%5Cle-%5Crho%5Calpha_k%5E2%5CVert%20d_k%5CVert%5E2%2C~~%5Cforall~%5Calpha_k%5Cin(0%2C%5Cfrac%7B2%7D%7BL%2B2%5Crho%7D%5Cfrac%7B%5Cvert%20g_k%5ET%20d_k%5Cvert%7D%7B%5CVert%20d_k%5CVert%5E2%7D).%5Ctag%7B14%7D)
由~)
和知，存在这样的，使得和~)
成立，而且~)
对
成立。由归纳法，~)
对所有的成立。
首先分两种情况：
和 
第一种情况易得
现设
，因此
不满足和。首先，假设不满足线搜索条件，则
%3Ef(x_k)-%5Crho%5Calpha_k%5E2%5CVert%20d_k%5CVert%5E2.%5Ctag%7B17%7D)
另一方面，由中值定理及导数的连续性知
-f(x_k)%26%3Df(x_k)%2B%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7Dg(z_k)%5ET%20d_k%5C%5C%20%26%3Df(x_k)%2B%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7Dg_k%5ET%20d_k%2B%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7D(g(z_k)%5ET%20d_k-g_k%5ETd_k)%5C%5C%20%26%5Cle%20f(x_k)%2B%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7D%20g_k%5ET%20d_k%2B(%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7D)%5E2L%5CVert%20d_k%5CVert%5E2%20%5Cend%7Balign%7D%5Ctag%7B18%7D)
其中~)
，由~)
和~)
得
另外，假设不满足线搜索条件，则下面的不等式至少有一个成立
%5ET(-g(w_k)%2B%5Cbeta_%7Bk%2B1%7Dd_k)%3E-c_1%5CVert%20g(w_k)%5CVert%5E2.%5Ctag%7B20%7D)
%5ET(-g(w_k)%2B%5Cbeta_%7Bk%2B1%7Dd_k)%3C-c_2%5CVert%20g(w_k)%5CVert%5E2.%5Ctag%7B21%7D)
其中
由~)
和得
%5CVert%5E2%26%3C-%5CVert%20g(w_k)%5CVert%5E2%2B%5Cvert%5Cbeta_%7Bk%2B1%7D%5Cvert%5Cvert%20g(w_k)%5ET%20d_k%5Cvert%5C%5C%20%26%5Cle-%5CVert%20g(w_k)%5CVert%5E2%2B%5Cfrac%7B%5CVert%20g(w_k)%5CVert%5CVert%20g(w_k)-g_k%5CVert%7D%7B%5CVert%20g_k%5CVert%7D%5Cvert%20g(w-k)%5ET%20d_k%5Cvert%5C%5C%20%26%5Cle-%5CVert%20g(w_k)%5CVert%5E2%2B%5CVert%20g(w_k)%5CVert%5E2%5Cfrac%7B%5CVert%20g(w_k)-g_k%5CVert%7D%7B%5CVert%20g_k%5CVert%5E2%7D%5CVert%20d_k%5CVert%5C%5C%20%26%5Cle%20-%5CVert%20g(w_k)%5CVert%5E2%2B%5Cfrac%7BL%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7D%5CVert%20d_k%5CVert%5E2%7D%7B%5CVert%20g_k%5CVert%5E2%7D%5CVert%20g(w_k)%5CVert%5E2%5Cend%7Balign%7D%5Ctag%7B22%7D)
由~)
可得
%5CVert%20g_k%5CVert%5E2%7D%7BL%5CVert%20d_k%5CVert%5E2%7D%5Ctag%7B23%7D)
由~)
和得
%5CVert%5E2%26%3E-%5CVert%20g(w_k)%5CVert%5E2%2B%5Cvert%5Cbeta_%7Bk%2B1%7D%5Cvert%5Cvert%20g(w_k)%5ET%20d_k%5Cvert%5C%5C%20%26%5Cge-%5CVert%20g(w_k)%5CVert%5E2-%5Cfrac%7B%5CVert%20g(w_k)%5CVert%5CVert%20g(w_k)-g_k%5CVert%7D%7B%5CVert%20g_k%5CVert%7D%5Cvert%20g(w_k)%5ET%20d_k%5Cvert%5C%5C%20%26%5Cge-%5CVert%20g(w_k)%5CVert%5E2-%5CVert%20g(w_k)%5CVert%5E2%5Cfrac%7B%5CVert%20g(w_k)-g_k%5CVert%7D%7B%5CVert%20g_k%5CVert%5E2%7D%5CVert%20d_k%5CVert%5C%5C%20%26%5Cge%20-%5CVert%20g(w_k)%5CVert%5E2-%5Cfrac%7BL%5Cfrac%7B%5Calpha_k%7D%7B%5Clambda%7D%5CVert%20d_k%5CVert%5E2%7D%7B%5CVert%20g_k%5CVert%5E2%7D%5CVert%20g(w_k)%5CVert%5E2%5Cend%7Balign%7D%5Ctag%7B24%7D)
由~)
可得
%5CVert%20g_k%5CVert%5E2%7D%7BL%5CVert%20d_k%5CVert%5E2%7D%5Ctag%7B25%7D)
即有
则进一步有
%5Cvert%20g_k%5ET%20d_k%5Cvert%7D%7BLc_2%5CVert%20d_k%5CVert%5E2%7D%5Ctag%7B28%7D)
则~)
进一步有
%5Cvert%20g_k%5ET%20d_k%5Cvert%7D%7BLc_2%5CVert%20d_k%5CVert%5E2%7D%5Ctag%7B29%7D)
结合~)
，~)
，~)
和~)
，我们可令
%7D%7BL%20c_2%7D%2C%5Cfrac%7B%5Clambda(c_2-1)%7D%7BL%20c_2%7D%5Cright%5C%7D%5Ctag%7B30%7D)
利用和两式可知，每步的函数值下降量具有量级%5E2%7D%7B%5CVert%20d_k%5CVert%5E2%7D~)
。因此，当目标函数有下界时，
条件成立。
%5E2%7D%7B%5CVert%20d_k%5CVert%5E2%7D%3C%5Cinfty%5Ctag%7B31%7D)
利用~)
以及
可以证明原始方法在
的线搜索下全局收敛性，而且为强收敛。
定理 2：设目标函数下方有界，导数连续可微。考虑方法，其中步长因子由的线搜索确定，则方法在下述意义下全局收敛：
证明：用直接法：由%2C(3)%2C(7)%2C(32)~)
和 导数的连续性、知
%5C%5C%20%26%5Cle%5CVert%20g_k%5CVert(1%2B%5Cfrac%7BL%20%5Calpha_%7Bk-1%7D%5CVert%20d_%7Bk-1%7D%5CVert%5E2%7D%7B%5CVert%20g_%7Bk-1%7D%5CVert%5E2%7D)%5C%5C%20%26%5Cle%5CVert%20g_k%5CVert(1%2B%5Cfrac%7B%5Ctau%20L%20%5Cvert%20g_%7Bk-1%7D%5ET%20d_%7Bk-1%7D%5Cvert%7D%7B%5CVert%20g_%7Bk-1%7D%5CVert%5E2%7D)%5C%5C%20%26%5Cle(1%2Bc_2%5Ctau%20L)%5CVert%20g_k%5CVert%5Cend%7Balign%7D%5Ctag%7B33%7D)
于是，利用%2C(31)%2C(33)~)
知
%5E2%7D%7B%5CVert%20d_k%5CVert%5E2%7D%5Cge%20c_1%5E2(1%2Bc_2%5Ctau%20L)%5E%7B-2%7D%5Csum_%7Bk%5Cge%201%7D%5CVert%20g_k%5CVert%5E2%2C%5Ctag%7B34%7D)
从而~)
成立。
)
表明，由方法产生的点列
的任意聚点都是目标函数的稳定点。这一结果比以前获得的收敛性结果都要强。在某种程度上，这一结果的取得归因于当
趋于零时，方法给出的方向
靠近于负梯度方向
。
3、参考文献
