15、PRP 共轭梯度法的一般收敛性理论

如果使用非精确线搜索如强 Wolfe 线搜索，戴彧虹在文献 $^{[1]}$ 中举出例子表明，即使 $~f(x)~$ 为一致凸函数，而且参数 $~\sigma\in (0,1)~$ 充分小，PRP 方法都可能产生一个上升搜索方向。如果每一个搜索方向都下降，则不难证明采取非精确线搜索方法对凸函数的收敛性，可参考文献 ${[2]}$ 和文献 ${[3]}$ 。对一般非凸函数，Powell 在综述性文献 ${[4]}$ 中建议 PRP 方法中的参数 $~\beta_k^{PRP}~$ 为非负：
$\beta_k=\max\left\{\beta_k^{PRP},0\right\}$
这样作的目的是避免当 $~\Vert d_k\Vert~$ 很大时，相邻两个搜索方向会趋于相反。 Gilbert 和 Nocedal $^{[5]}$ 考虑了 Powell 的上述建议，并在适当的线搜索条件下，建立了修正 PRP 方法对一般非凸函数的全局收敛性。然而， Gilbert 也举例表明，即使对于一致凸函数， $~\beta_k^{PRP}~$ 也可能为负。

1、PRP+ 方法的收敛性

PRP 共轭梯度法是由 Polak 和 Ribiere 和 Polyak 在 1969 年独立提出的一种非线性共轭梯度法，这种方法具有如下形式：
$x_{k+1}=x_k+\alpha_k d_k,\tag{1}$
$d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{2}$
其中参数 $~\beta_k~$ 由以下公式计算：
$\beta_k^{PRP}=\frac{g_k^T(g_k-g_{k-1})}{\Vert g_{k-1}\Vert^2}.\tag{3}$
为建立对一般非凸函数的收敛结果，令
$\beta_k=\left\{\beta_k^{PRP},0\right\}\tag{4}$
充分下降条件，即
$-g_k^T d_k\ge c\Vert g_k\Vert^2~~(~c>0~为某常数)\tag{5}$
后面的线搜索将会基于标准Wolfe 线搜索或强 Wolfe 线搜索，Wolfe 线搜索即
$\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k,\\ g(x_k+\alpha_k d_k)^T d_k\ge\sigma g_k^T d_k \end{cases}\tag{6}$
强 Wolfe 线搜索即
$\begin{cases} f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k,\\ \vert g(x_k+\alpha_k d_k)^T d_k\vert\le-\sigma g_k^T d_k \end{cases}\tag{7}$
限制参数 $~\beta_k^{PRP}~$ 非负的一个优点是：它可以避免当 $~\Vert d_k\Vert~$ 很大时，相邻的两个搜索方向趋于相反方向的现象。进一步，我们可以证明当 $~\Vert d_k\Vert~$ 很大时，方向 $~d_k~$ 的变化较为缓慢，因此如果目标函数的水平集有界，方法产生的大步长数不可能很多；如果小步长较多，则可证明 $~\Vert d_k\Vert~$ 最多线性增长，从而证明方法收敛性。

我们要想证明如下收敛关系式
$\lim\inf\Vert g_k\Vert=0\tag{8}$
我们使用反证法：即假定存在常数 $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge\gamma,~~\forall~k\ge 1\tag{9}$
此外，设 $~f(x)~$ 的水平集 $~\Omega=\left\{x\in\mathbb{R}^n:f(x)\le f(x_1)\right\}~$ 有界，即存在 $~B~$ ，使得
$\Vert x\Vert\le B,~~\forall~x\in\Omega\tag{10}$
这时，若 $~f(x)~$ 连续可微，则也存在正常数 $~\overline{\gamma}~$ ，使得
$\Vert g(x)\Vert\le\overline{\gamma},~~\forall~x\in\Omega\tag{11}$

引理 1：设目标函数 $~f(x)~$ 水平集有界，且导数 $~\rm{Lipschitz}~$ 连续，考虑方法 (1) 和 (2)，其中参数 $~\beta\ge 0~$ ，步长因子 $~\alpha_k~$ 满足 $~\rm{Wolfe}~$ 条件 (6) 以及充分下降条件 (5)，如果 (9) 式成立，则 $~d_k\neq 0~$ 。进一步，令 $~u_k=\frac{d_k}{\Vert d_k\Vert}~$ ，有
$\sum_{k\ge 2}\Vert u_k-u_{k-1}\Vert^2<\infty\tag{12}$
证明：由 (5) 式可知， $\Vert d_k\Vert\neq 0~$ 。否则，有 $~g_k=0~$ ，故 $~u_k~$ 有定义，记
$r_k=\frac{-g_k}{\Vert d_k\Vert}~~~~~\delta_k=\frac{\beta_k\Vert d_{k-1}\Vert}{\Vert d_k\Vert},\tag{13}$
则由 (2) 式，对 $~k\ge 2~$ 有
$u_k=r_k+\delta_k u_{k-1}.\tag{14}$
利用上式及 $~\Vert u_k\Vert=\Vert u_{k-1}\Vert=1~$ 可证明
$\Vert r_k\Vert=\Vert u_k-\delta_k u_{k-1}\Vert=\Vert u_{k-1}-\delta_ku_k\Vert.\tag{15}$
显然， $\beta_k\ge 0~$ 隐含 $~\delta_k\ge 0~$ ，从而利用 (15) 和三角不等式，知
$\begin{align}\Vert u_k-u_{k-1}\Vert&\le\Vert(1+\delta_k)u_k-(1+\delta_k)u_{k-1}\Vert\\ &\le\Vert u_k-\delta_k u_{k-1}\Vert+\Vert \delta_k u_k-u_{k-1}\Vert\\ &=2\Vert r_k\Vert\end{align}\tag{16}$
利用 (5) 式和 $\rm{Zoutendijk}~$ 条件
$\sum_{k\ge 2}\frac{\Vert g_k\Vert^4}{\Vert d_k\Vert^2}=\sum_{k\ge 2}\Vert r_k\Vert^2\Vert g_k\Vert^2<\infty\tag{17}$
利用 (9) 式，则有
$\sum_{k\ge 2}\Vert r_k\Vert^2<\infty\tag{18}$
由上式及 (16) 式知 (12) 成立。
(12) 式并不意为序列 $~\left\{u_k\right\}~$ 收敛，但它表明了当 $~k~$ 充分大时，向量 $~u_k~$ 的变化非常缓慢。
当 PRP 方法在某一步产生一个很小的步长时，下一步的搜索方向靠近最速下降方向，而不会连续地产生小步长。这一性质实质上归因于 $~\beta_k^{PRP}~$ 当步长 $~s_{k-1}~$ 很小时趋于零的性质。这个性质的严格表述最早由 Gilbert 和 Nocedal 给出的，并称之为性质( $\rm{*}$ )。

性质（ $\rm{*}$ ）考虑形如 (1) 和 (2) 的方法，并假定
$0<\gamma<\Vert g_k\Vert<\overline{\gamma}\tag{19}$
我们说方法具有性质( $\rm{*}$ )，如果存在常数 $~b>1~$ 和 $~\lambda>0~$ ，使得对所有的 $~k~$ 有下式成立：
$\vert \beta_k\vert\le b.\tag{20}$
以及
$\Vert s_{k-1}\Vert\le\lambda\Rightarrow\vert \beta_k\vert\le\frac{1}{2b}\tag{21}$
对于 PRP 方法，可取 $~b=\frac{2\overline{\gamma}}{\gamma^2}~$ 和 $~\lambda=\frac{\gamma^2}{2L\lambda b}~$ ，使得 (20) 和 (21) 两式成立，事实上，利用 (3) 式有
$\vert \beta_k^{PRP}\vert\le\frac{\Vert g_k\Vert\Vert g_k-g_{k-1}\Vert}{\Vert g_{k-1}\Vert^2}\le\frac{2\overline{\gamma}^2}{\gamma^2}=b.\tag{22}$
而若 $~\Vert s_{k-1}\Vert\le\lambda~$ ，则由导数的 $~\rm{Lipschitz}~$ 连续性知
$\vert \beta_k^{PRP}\vert\le\frac{\Vert y_{k-1}\Vert\Vert g_k\Vert}{\Vert g_{k-1}\Vert^2}\le\frac{L\lambda\overline{\gamma}}{\gamma^2}=\frac{1}{2b}\tag{23}$
显然，当 $~\beta_k~$ 具有性质( $\rm{*}$ )时， $\beta_k^{+}=\max\left\{\beta_k,0\right\}~$ 亦具有性质( $\rm{*}$ )。

下面我们证明，对于具有性质( $\rm{*}$ ) 的方法，如果 (9) 式成立，则小步长的数目不可能太多，否则， $\Vert d_k\Vert~$ 最多线性增长，从而与 (9) 式矛盾。为此，我们记 $~\mathbb{Z}^+~$ 为正整数集，并对任意的 $~\lambda>0~$ ，定义 $K_{k,\triangle}^{\lambda}\triangleq\left\{i\in Z^+:k\le i\le k+\triangle+1,\Vert s_{i-1}\Vert>\lambda\right\}\tag{24}$
用 $~\vert K_{k,\triangle}^{\lambda}\vert~$ 表示 $~K_{k,\triangle}^{\lambda}~$ 中元素的个数。

引理 2：设目标函数 $~f(x)~$ 水平集有界，且导数 $~\rm{Lipschitz}~$ 连续。考虑方法 (1) 和 (2)，其中参数 $~\beta_k\ge 0~$ ，步长因子 $~\alpha_k~$ 满足 Wolfe 线搜索 (6) 以及充分下降条件 (5)。如果 $~\beta_k~$ 具有性质( $\rm{*}$ )，且 (9) 式成立，则存在 $~\lambda>0~$ ，使得对任意的 $~\triangle\in Z^+~$ 和指标 $~k_0~$ ，均存在指标 $~k\ge k_0~$ ，满足
$~\vert K_{k,\triangle}^{\lambda}\vert>\frac{\triangle}{2}\tag{25}$
证明：用反证法，假设对任意 $~\lambda>0~$ ，总存在 $~\triangle\in Z^+~$ 和 $~k_0~$ ，使得
$\vert K_{k,\triangle}^{\lambda}\vert\le\frac{\triangle}{2},~~\forall~k\ge k_0.\tag{26}$
由 (9) 和 (11) 知 (19) 成立。因为方法具有性质( $\rm{*}$ )，故 (20) 和 (21) 对某 $~\lambda>0~$ 和 $~b>1~$ 为真。对此 $~\lambda>0~$ 选取 $~\triangle~$ 和 $~k_0~$ 满足 (26)。
对 $~l\ge k_0+1~$ ，我们有
$\begin{align}\Vert d_l\Vert^2&\le(\Vert g_l\Vert+\vert \beta_l\vert\Vert d_{l-1}\Vert)^2\\ &\le 2\Vert g_l\Vert^2+2\beta_l^2\Vert d_{l-1}\Vert^2\\ &\le 2\overline{\gamma}^2+2\beta_l^2\Vert d_{l-1}\Vert^2 \end{align}\tag{27}$
将上式递推，可得
$\Vert d_l\Vert^2\le c_1(1+2\beta_l^2+2\beta_l^2\beta_{l-1}^2+\dots+2\beta_l^22\beta_{l-1}^2\dots2\beta_{k0}^2)\tag{28}$
其中 $~c=\max\left\{2\overline{\gamma}^2,\Vert d_{k_0-1}\Vert\right\}~$ 是与 $~l~$ 无关的常数，考虑 (28) 中的一个典型项
$2\beta_l^22\beta_{l-1}^2\dots2\beta_k^2,\tag{29}$
其中
$k_0\le K\le l,\tag{30}$
我们将 (29) 中的 $2(l-k+1)$ 个因子每 $2\triangle$ 个分成一组。记 $~m=[(l-k+1)/\triangle]~$ 为不超过 $~(l-k+1)/\triangle~$ 的最大整数，则 $(28)$ 的因子可分为 $m$ 或 $m+1$ 项：
$(2\beta_{l1}^2\dots2\beta_{k1}^2),\dots,(2\beta_{lm}^2\dots2\beta_{km}^2),\tag{31}$
以及可能的一项
$(2\beta_{l_m+1}^2\dots2\beta_k^2),\tag{32}$
其中 $~l_i=l-(i-1)\triangle~,~k_i=l_{i+1}-1~$ 。显然 $~k\ge k_0~$ 对 $~i=1,2\dots,m~$ 成立，故由反证法假设 (26) 知
$p_i\triangleq\vert K_{k,\triangle}^{\lambda}\vert\le\frac{\triangle}{2},~~i=1,2,\dots,m\tag{33}$
这表明在 $~[k_i,k_i+\triangle+1]~$ 内恰好有 $~p_i~$ 个指标 $~j~$ 使得 $~\Vert s_{j-1}\Vert>\lambda~$ ，而对另 $~(\triangle-p_i)~$ 个指标有 $~\Vert s_{j-1}\Vert\le\lambda~$ ，根据 (20)、(21) 两式，我们对 (31) 中的每一项有如下估计量：
$\begin{align} (2\beta_{l_i}^2\dots2\beta_{k_i}^2)&\le 2\triangle b^{2p_i}(\frac{1}{2b})^{2(\triangle-p_i)}\\ &=2^{\triangle-2\triangle+2p_i}b^{2p_i-2\triangle+2p_i}\\ &=(2b^2)^{2p_i-\triangle}\\ &\le 1 \end{align}\tag{34}$
在 $~(34)~$ 的推导中用到了 $~(33)~$ 以及 $~2b^2>1~$ 。可见 $~(31)~$ 中的每一项均小于或等于 $~1~$ 。对 $~(32)~$ 中的项，利用 $~(20)~$ 可得
$(2\beta_{l_m+1}^2\dots2\beta_k^2)<(2b^2)^{\triangle}\tag{35}$
故 $~(28)~$ 中右端括号中的每一项都小于 $~(2b^2)^{\triangle}~$ ，从而有
$\Vert d_k\Vert^2\le c_1(2b^2)^{\triangle}(l-k_0+2)\tag{36}$
上式表明 $~\Vert d_l\Vert^2~$ 最多线性增长。而由充分下降条件 $~(5)~$ 和 $~\rm{Zoutendijk}~$ 条件知
$\gamma^4\sum_{k\ge 1}\frac{1}{\Vert d_k\Vert^2}\le\sum_{k\ge 1}\frac{\Vert g_k\Vert^4}{\Vert d_k\Vert^2}<\infty\tag{37}$
这和 $~\rm{Zoutendijk}~$ 条件相矛盾，从而也表明引理为真。

定理 3：设目标函数 $~f(x)~$ 水平集有界，且导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(1)~$ 和 $~(2)~$ ，其中 $~\beta_k\ge 0~$ ，步长因子 $~\alpha_k~$ 满足 Wolfe 线搜索 (6) 以及充分下降条件 (5)。如果 $~\beta_k~$ 具有性质( $\rm{*}$ )，则方法给出 $~\lim\inf\Vert g_k\Vert=0~$ 。
证明：用反证法，假设 $~(8)~$ 式不成立，从而 引理 1 和 引理 2 的条件满足。仍定义 $~u_i=\frac{d_i}{\Vert d_i\Vert}~$ ，则对任意整数 $~l,k~(l\ge k)~$ 有
$\begin{align} x_l-x_{k-1}&=\sum_{i=k}^l\Vert s_{i-1}\Vert u_{i-1}\\ &=\sum_{i=k}^l\Vert s_{i-1}\Vert u_{k-1}+\sum_{i=k}^l\Vert s_{i-1}\Vert(u_{i-1}-u_{k-1}) \end{align}\tag{38}$
对上式两端取模，并利用 $~(10)~$ 得
$\sum_{i=k}^l\Vert s_{i-1}\Vert\le 2B+\sum_{i=k}^l\Vert s_{i-1}\Vert\Vert u_{i-1}-u_{k-1}\Vert.\tag{39}$
设 $~\lambda~$ 由 引理 2 给出，并记 $~\triangle=[\frac{8B}{\lambda}]~$ 为不小于 $~\frac{8B}{\lambda}~$ 的最小整数。则由 引理 1 可知，存在指标 $~k_0~$ ，使得
$\sum_{i\ge k_0}\Vert u_{i+1}-u_i\Vert^2\le\frac{1}{4\triangle}.\tag{40}$
由 引理 2 可知，存在 $~k\ge k_0~$ ，使得
$~\vert K_{k,\triangle}^{\lambda}\vert>\frac{\triangle}{2}\tag{41}$
对任意的 $~i\in [k,k+\triangle-1]~$ ，利用 $\rm{Cauchy-Schwarz}$ 不等式及 (40)，得
$\begin{align}\Vert u_{i-1}-u_i\Vert&\le\sum_{j=k}^{i-1}\Vert u_j-u_{j-1}\Vert\\ &\le(i-k)^{\frac{1}{2}}(\sum_{j=k}^{i-1}\Vert u_j-u_{j-1}\Vert^2)^{\frac{1}{2}}\\ &\le\triangle^{\frac{1}{2}}(\frac{1}{4\triangle})^{\frac{1}{2}}=\frac{1}{2} \end{align}\tag{42}$
利用上式，及 $~(39)~$ 和 $~(41)~$ ，得
$2B\ge\frac{1}{2}\sum_{i=k}^{k+\triangle-1}\Vert s_{i-1}\Vert>\frac{\lambda}{2}\vert K_{k,\triangle}^{\lambda}\vert>\frac{\lambda\triangle}{4},\tag{43}$
故 $~\triangle<\frac{8B}{\lambda}~$ ，这与 $~\triangle~$ 的定义相矛盾，于是定理得证。

既然由 $~(4)~$ 式给出的 $~\beta_k~$ 非负，而且具有性质 $~(*)~$ ，从 定理 3 可立即推出：

推论 4：设目标函数 $~f(x)~$ 水平集有界，且导数 $~\rm{Lipschitz}~$ 连续，考虑 $~\rm{PRP^{+}}~$ 方法 $~(1)~$ 和 $~(2)~$ ，其中 $~\beta_k~$ 由 $~(3)~$ 和 $~(4)~$ 给出，步长因子 $~\alpha_k~$ 满足 $\rm{Wolfe}$ 线搜索 $~(6)~$ 以及充分下降条件 $~(5)~$ ，则方法给出 $~\lim\inf\Vert g_k\Vert=0~$

依据前面的内容，通过对共轭梯度法的一般收敛性分析可知，如果线搜索满足强 $~\rm{Wolfe}~$ 线搜索条件，则 推论 4 中的充分下降条件 $~(5)~$ 可以削弱为下降条件 $~g_k^T d_k<0~$ 。文献 [6]、[7] 给出了这样的例子，使得对 $~\epsilon>0~$ ，则方法 (1) 和 (2) ( 其中 $\beta_k=\max\left\{\beta_k^{PRP},-\epsilon\right\}$ ) 不收敛。这一例子在一定程度上限制参数 $~\beta_k^{PRP}\ge 0~$ 的必要性。而且在文献 [6]、[7] 也给出例子，表明 定理 3 中水平集有界的条件是必不可少的。

2、参考文献

[1] 戴彧虹. 非线性共轭梯度法. 2000, 科学出版社.
[2] Yuan Y X. Analysis on the conjugate gradient method. Optimization Methods and Software, 1993, 2: 19-29.
[3] 徐大川, 沙玉英, 杜秀梅. PR 方法的收敛性. 中科院计算数学报告, 1999.
[4] Powell M J D. Convergence properties pf algirithms for nonlinear optimization. SIAM Review, 1986, 28: 487-500.
[5] Gilbert J C, Nocedal J. Global convergence properties of conjugate gradient methods for optimization, SIAM, J. Optimization. 1992, 2(1): 21-42.

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 202,056评论 5赞 474
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 84,842评论 2赞 378
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 148,938评论 0赞 335
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,296评论 1赞 272
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,292评论 5赞 363
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,413评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,824评论 3赞 393
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,493评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,686评论 1赞 295
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,502评论 2赞 318
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,553评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,281评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,820评论 3赞 305
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,873评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,109评论 1赞 258
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,699评论 2赞 348
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,257评论 2赞 341

15、PRP 共轭梯度法的一般收敛性理论

1、PRP+ 方法的收敛性

2、参考文献

推荐阅读更多精彩内容