21、DL 共轭梯度法

共轭梯度法是一类重要的方法，特别是当维数很大时。本文将提出一种新的共轭条件，考虑其非精确线搜索。依据新的共轭条件，两种非线性共轭梯度法将会被提出，同时给出其收敛性分析。

1、介绍

我们的问题是处理一个 $~n~$ 维变量问题
$\min~f(x),~~x\in\mathbb{R}^n\tag{1}$
其中 $~f~$ 是光滑的且 $~\nabla~f~$ 是可以得到的。共轭梯度法是非常有用的处理问题 $~(1)~$ 当 $~n~$ 非常大时，其有如下形式：
$x_{k+1}=x_k+\alpha_k d_k,\tag{2}$
$d_k=\begin{cases} -g_k,\quad & k=1,\\ -g_k+\beta_k d_k, &k\ge 2,\end{cases}\tag{3}$
其中 $~\alpha_k~$ 是步长， $\beta_k~$ 是常数，且 $~g_k~$ 表示 $~\nabla f(x_k)~$ 。当 $~f~$ 是凸二次函数时
$f(x)=\frac{1}{2}x^T H x+g^T x\tag{4}$
其中 $~\alpha_k~$ 是一维线搜索，即
$\alpha_k=\arg\min_{\alpha>0}f(x_k+\alpha d_k)\tag{5}$
共轭梯度法即共轭条件成立，即
$d_i^T Hd_j=0,~~\forall~i\neq j\tag{6}$
定义 $~y_{k-1}~$ 为
$y_{k-1}=g_k-g_{k-1}\tag{7}$
对于一般的非线性函数，我们知道利用中值定理一定存在常数 $~t\in(0,1)~$ 使得
$\alpha_k^{-1}d_k^T y_{k-1}=d_k^T\nabla^2 f(x_{k_1}+t \alpha_{k-1} d_{k-1} )d_{k-1}d_{k-1}\tag{8}$
可以看出用如下条件替代 $~(6)~$ 式作为共轭条件是合理的，即
$d_{k-1}^T y_{k-1}=0\tag{9}$
利用 $~(1.3)~$ 和 $~(1.9)~$ ，我们给出 $~\beta_k~$ 的新公式
$\beta_k=\frac{g_k^Ty_{k-1}}{d_{k-1}^Ty_{k-1}}\tag{10}$
以上称为 HS 共轭梯度法，是由 Hestenes 和 Stiefel 于 1952 年提出来的。在实际计算中，HS 共轭梯度法类似于 PRP ，有良好的数值实验效果。
然而，共轭条件 $~(6)~$ 和 $~(9)~$ 是依赖于精确线搜索，在实际的计算中，我们会采取非精确线搜索。因此 $~g_{k+1}^T d_k\neq 0~$ ，共轭条件 $~(6)~$ 和 $~(9)~$ 可能有一些缺点。所有我们要给出新的共轭条件。

2、一种新的共轭条件和新的 $~\beta_k~$ 参数

在 BFGS 算法中
$d_k=-B_kg_k\tag{11}$
其中 $~B_k~$ 是 $~n\times n~$ 对称正定矩阵，在拟牛顿法中
$B_{k}y_{k-1}=s_{k-1}\tag{12}$
其中 $~s_{k-1}=\alpha_{k-1}d_{k-1}~$ ，利用 $~(11)~$ 和 $~(12)~$ ，我们有
$d_{k-1}^Ty_{k-1}=-(b_kg_k)^Ty_{k-1}=-g_k^T(B_ky_{k-1})=-g_k^Ts_{k-1}\tag{13}$
由 $~(13)~$ 可知，如果线搜索是精确的，则 $~d_{k-1}^Ty_{k-1}=0~$ 。然而在实际中会经常用到非精确线搜索，所以将共轭条件 $~(13)~$ 代替 $~(9)~$ 是合理的。为了更一般的情况，我们把 $~(13)~$ 替换成
$d_k^Ty_{k-1}=-tg_k^Ts_{k-1}\tag{14}$
其中 $~t\ge 0~$ 为常数。
为了确保 $~d_k~$ 满足共轭条件 $~(14)~$ ，根据 $~(3)~$ 式，我们有
$\beta_k=\frac{g_k^T(y_{k-1}-t s_{k-1})}{d_{k-1}^T y_{k-1}}\tag{15}$
显然有
$\beta_k=\beta_k^{HS}-t\frac{g_k^T s_{k-1}}{d_{k-1}^Ty_{k-1}}\tag{16}$
其中 $~t\in[0,\infty)~$ 。特别地，若 $~t=1~$ ，则
$\beta_k=\frac{g_k^T(y_{k-1}-s_{k-1})}{d_{k-1}^Ty_{k-1}}\tag{17}$

3、DL 共轭梯度法对一致凸函数的全局收敛性

本节我们都是假定
$g_k\neq 0~~\forall~k\ge 1\tag{18}$
否则稳定点已经得到。同时给出下降条件，即存在 $~c\ge 0~$ ，使得
$g_k^T d_k< -c\Vert g_k\Vert^2\tag{19}$
假定 1：
(i) 水平集 $~\varOmega=\left\{x\in\mathbb{R}^n|f(x)\le f(x_1)\right\}~$ 有界，即存在 $~B>0~$ 使得
$\Vert x\Vert\le B,~~\forall~x\in B\tag{20}$
(ii) 在水平集 $~\varOmega~$ 的某个邻域 $~N~$ 上, $f(x)~$ 的梯度函数 $~g(x)~$ 是_Lipschitz连续, 即存在~ $L>0$ ，使
$\Vert g(y)-g(x)\Vert\le L\Vert y-x\Vert,~~~~~\forall x,y\in N.\tag{21}$
在 $~(20)~$ 和 $~(21)~$ 的假定下，我们有存在 $~\overline{\gamma}\ge 0~$ 满足
$\Vert \nabla f(x)\Vert\le\overline{\gamma}\tag{22}$
步长 $~\alpha_k~$ 由强 Wolfe 线搜索决定，即
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k\tag{23}$
$\vert g(x_k+\alpha_k d_k)^T d_k\vert\le -\sigma g_k^Td_k\tag{24}$
其中 $~0<\rho<\sigma<1~$ .

我们首先给出如下引理，在前面的章节就证明过。
引理 2：若假定 1 成立，考虑任何形式的共轭梯度法(2)-(3)，其中 $~d_k~$ 是下降方向且 $~\alpha_k~$ 由强 Wolfe 线搜索决定，如果
$\sum_{k\ge 1}\frac{1}{\Vert d_k\Vert^2}=\infty\tag{25}$
我们有
$\lim\inf\Vert g_k\Vert=0\tag{26}$

定理 3：若假定 1 成立，考虑共轭梯度法(2)、(3) 和 (15)，其中 $~d_k~$ 是下降方向且 $~\alpha_k~$ 由强 Wolfe 线搜索决定，如果存在常数 $~u>0~$ ，使得
$(\nabla f(x)-\nabla f(y))^T(y-x)\ge u\Vert y-x\Vert^2,~~\forall~x,y\in N\tag{27}$
我们有
$\lim\Vert g_k\Vert=0\tag{28}$
证明：由 $~(27)~$ 可知， $f(x)~$ 为一致凸函数。即有
$d_{k-1}^T y_{k-1}\ge u\alpha_{k-1}\Vert d_{k-1}\Vert^2\tag{29}$
由 (3)、(15)、(21)、(22) 和 (29)，我们有
$\Vert d_k\Vert\le \Vert g_k\Vert+\frac{(L+t)\Vert g_k\Vert\Vert s_{k-1}\Vert}{u\alpha_{k-1}\Vert d_{k-1}\Vert^2}\Vert d_{k-1}\Vert^2\le u^{-1}(L+t+u)\overline{\gamma}\tag{30}$
上式表明 $~(25)~$ 成立，利用 引理 2，我们知道 $~(26)~$ 式成立，对于一致凸函数， $~(26)~$ 等价于 $~(28)~$ 。

3、DL 共轭梯度法对一般函数的全局收敛性

对于一般的函数，因为 $~(15)~$ 在精确线搜索下等价于 PRP 共轭梯度法。由于在证明 PRP算法中我们取 $~\beta_k=\left\{0,\beta_k^{PRP}\right\}~$ 。所以在这里，我们也令
$\beta_k=\max\left\{\frac{g_k^T y_{k-1}}{d_{k-1}^T y_{k-1}},0\right\}-t\frac{g_k^T s_{k-1}}{d_{k-1}^Ty_{k-1}}\tag{31}$
引理 4：若假定1成立，考虑共轭梯度法 (2)，(3) 和 (31)，其中 $~d_k~$ 是下降方向， $~\alpha_k~$ 是由强 Wolfe 线搜索决定。如果存在一个常数 $~\gamma>0~$ 对于
$\Vert g_k\Vert\ge\gamma,~~\forall~k\ge 1\tag{32}$
有 $~d_k\neq 0~$ 和
$\sum_{k\ge 2}\Vert u_k-u_{k-1}\Vert^2<\infty\tag{33}$
其中 $~u_k=\frac{d_k}{\Vert d_k\Vert}~$
证明：由于 $~d_k~$ 是下降方向，故 $~d_k\neq 0~$ ，从而 $~u_k~$ 的定义是有意义的。通过 $~(32)~$ 和引理 2 可知
$\sum_{k\ge 1}\frac{1}{\Vert d_k\Vert^2}<\infty\tag{34}$
现将 $~(31)~$ 中的 $~\beta_k~$ 分为两个部分
$\beta_k^{(1)}=\max \left\{\frac{g_k^Ty_{k-1}}{d_{k-1}^Ty_{k-1}},0\right\} ~和~\beta_k^{(2)}=-t\frac{g_k^Ts_{k-1}}{d_{k-1}^T y_{k-1}}\tag{35}$
我们定义
$r_k=\frac{v_k}{\Vert d_k\Vert}~和~\delta_k=\frac{\beta_k^{(1)}\Vert d_{k-1}\Vert}{\Vert d_k\Vert}\tag{36}$
其中
$v_k=-g_k+\beta_k^{(2)}d_{k-1}\tag{37}$
由 $~(3)~$ 可知，当 $~t\ge 2~$ 时
$u_k=r_k+\delta_k u_{k-1}\tag{38}$
利用 $~\Vert u_k\Vert=\Vert u_{k-1}\Vert=1~$ 和 $~(38)~$ ，有
$\Vert r_k\Vert=\Vert u_k-\delta_k u_{k-1}\Vert=\Vert\delta_k u_k-u_{k-1}\Vert\tag{39}$
注意到 $~\delta_k>0~$ 和 $~(39)~$ ，有
$\begin{align}\Vert u_k-u_{k-1}&\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\\ &\le 2\Vert r_k\Vert\end{align}\tag{40}$
另一方面，利用线搜索 $~(24)~$ 有
$d_{k-1}^Ty_{k-1}\ge (\sigma-1)g_{k-1}^T d_{k-1}\tag{41}$
利用 $~(24)~$ 和 $~(41)~$ ，以及假定 $~g_{k-1}^T d_{k-1}<0~$ ，有
$\vert \frac{g_k^T d_{k-1}}{d_{k-1}^T y_{k-1}}\vert\le\frac{\sigma}{1-\sigma}\tag{42}$
利用 $~(20)~$ , $~(22)~$ , $~(37)~$ , $~(42)~$ ，有
$\Vert v_k\Vert\le\Vert g_k\Vert+t\vert \frac{g_k^T d_{k-1}}{d_{k-1}^T y_{k-1}}\vert\Vert s_{k-1}\Vert\le\overline{\gamma}+2t\sigma(1-\sigma)^{-1}B\tag{42}$
因此通过 $~(34),(36),(40),(42)~$ ，我们知道 $~(33)~$ 成立。故证明完毕。

现在我们给出 $~\beta_k~$ 的性质，这种相似但是又不同于 $性质(*)$ ，如果 $~(19)~$ 式对于某个 $~c>0~$ 成立，假定 $~0<\gamma\le\Vert g_k\Vert\le\overline{\gamma}~$ 以及 $~(24)~$ 成立，存在 $~b>1~$ 和 $~\lambda>0~$ 对于所有的 $~k~$ 有
$\vert\beta_k\vert\le b\tag{43}$
$\Vert s_{k-1}\Vert\le\lambda~\Rightarrow~\vert \beta_k\vert\le\frac{1}{b}\tag{44}$
实际上，利用 $~(19),(22),(41)~$ ，我们有
$d_{k-1}^T y_{k-1}\ge(\sigma-1)g_{k-1}^T d_{k-1}\ge(1-\sigma)c\Vert g_{k-1}\Vert^2\ge(1-\sigma)c\gamma^2\tag{45}$
利用 $~(20),(21),(45)~$ ，我们有
$\vert \beta_k\vert\le\frac{(L+t)\Vert g_k\Vert\Vert s_{k-1}\Vert}{(1-\sigma)c\gamma^2}\le\frac{2(L+t)\overline{\gamma}B}{(1-\sigma)c\gamma^2}=b\tag{46}$
注意到 $~b~$ 可以定义满足 $~b>1~$ ，所以我们可以定义 $~\lambda~$
$\lambda=\frac{(1-\sigma)c\gamma^2}{b(L+t)\overline{\gamma}}\tag{47}$
从 $~(46)~$ 的第一个不等式，如果 $~\Vert s_{k-1}\Vert\le\lambda~$ ，则
$\vert \beta_k\vert\le\frac{(L+t)\overline{\gamma}\lambda}{(1-\sigma)c\gamma^2}=\frac{1}{b}\tag{48}$
因此我们找到这样的 $~b~$ 和 $~\lambda~$ 使其满足 $~(43)~$ 和 $~(44)~$ 。

我们定义 $~N^{+}~$ 为正整数集，对于任意的 $~\lambda>0~$ 和正整数 $~\triangle~$ ，定义
$K_k^{\triangle}=\left\{i\in N^{+}:k<i<k+\triangle-1,\Vert s_{i-1}\Vert>\lambda\right\}\tag{49}$
让 $~\vert K_k^{\triangle}\vert~$ 表示 $~K_k^{\triangle}~$ 的数目，则公式 $~(31)~$ 具有这样的性质。

引理 5：若假定1成立，考虑共轭梯度法 (2)，(3) 和 (31)，其中 $~d_k~$ 是充分下降方向， $~\alpha_k~$ 满足强 $~\rm{Wolfe}~$ 线搜索，若 $~(32)~$ 成立，则存在 $~\lambda>0~$ ，使得对任意的 $~\triangle\in N^{+}~$ 和任意的指标 $~k_0~$ ，均存在 $~k\ge k_0~$ ，满足
$\vert K_k^{\triangle}\vert>\frac{\triangle}{2}\tag{50}$
证明：反证法，假定对任意的 $~\lambda>0~$ ，存在 $~\triangle\in N^{+}~$ 和 $~k_0~$ 有
$\vert K_k^{\triangle}\vert\le\frac{\triangle}{2}~~~~\forall~k\ge k_0\tag{51}$
因为 $~(31)~$ 满足 $~(43)~$ 和 $~(44)~$ ，即存在 $~\lambda>0~$ 和 $~b>1~$ 。对此 $~\lambda>0~$ 选取 $~\triangle\in N^{+}~$ 和 $~k_0~$ ，根据 $~(43),(44),(51)~$ ，有
$\prod \limits_{k_0+i\triangle+1}^{k_0+(i+1)\triangle}\vert \beta_k\vert\le b^{\frac{\triangle}{2}}(\frac{1}{b})^{\frac{\triangle}{2}}=1，~~\forall~i~\ge 0\tag{52}$
如果 $~\beta_k=0~$ ，则 $~(3)~$ 中的方向自动变为 $~-d_k~$ ，如果此时不收敛的话，我们就把 $~x_k~$ 看出新的起点。所以为了不失一般性，我们总是假定
$\beta_k\neq 0,~~\forall~k\ge 1\tag{53}$
由 $~(52)~$ 和 $~(53)~$ 知
$\prod \limits_{j=2}^{k_0+i\triangle}\beta_j^{-2}\ge\prod\limits_{j=2}^{k_0}\beta_j^{-2},~~\forall~i\ge 0\tag{54}$
由 $~(54)~$ 式，则
$\sum_{k\ge 2}\prod\limits_{j=2}^k\beta_j^{-2}=\infty\tag{55}$
利用 $~(51)~$ 式，以及前面的在标准 $~\rm{Wolfe}~$ 线搜索下的一般理论，我们可知 $~\lim\inf\Vert g_k\Vert=0~$ ，这与 $~(32)~$ 式相矛盾，故假设不成立。在 戴彧虹 的原文中，不是这样写的，但是中心思想都差不多，如有兴趣可以参考原文的文献。

定理 6：若假定1成立，考虑共轭梯度法 (2)，(3) 和 (31)，其中 $~d_k~$ 是充分下降方向， $~\alpha_k~$ 满足强 $~\rm{Wolfe}~$ 线搜索，则有
$\lim\inf\Vert g_k\Vert=0\tag{56}$
证明：证明的过程省略，和当时 PRP 共轭梯度法一样，没有一点区别。

4、结束语

由于 DL 共轭梯度法是对 HS 共轭梯度法的改进，而 HS 共轭梯度法的收敛性证明又和 PRP 共轭梯度法几乎相同，所以此处的相同证明省去不写。参考文献如下
[1] Dai Y H, Liao L Z. New conjugacy conditions and related Nonlinear conjugate gradient methods[J]. Applied Mathmatics Optimization, 2001, 43: 87-101.
[2] 戴彧虹. 非线性共轭梯度法[M]. 2000, 科学出版社。