11、DY 共轭梯度法的内在性质

这篇文章同样出于戴彧虹 和 袁亚湘 老师之手，我个人感觉证明很巧妙。本文主要进一步分析 DY 共轭梯度法，在不特别给定线搜索和函数凸性的情况下，给出了 DY 共轭梯度法的内在性质，即是充分下降性对于大多数点列都成立。

1、介绍
共轭梯度法是解决无约束优化问题的常用方法之一，问题如下
$\min_{x\in\mathbb{R}^n} f(x)\tag{1}$
求解此问题，一般采取线搜索技巧，其基本迭代格式形如
$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}$
其中 $~g_k~$ 是迭代点 $~x_k~$ 处的梯度， $~\alpha_k~$ 是搜素步长， $~d_k~$ 是搜素方向， $~\beta_k~$ 为共轭参数。
不同的参数 $~\beta_k~$ 决定不同的共轭梯度法。在前一篇文章，我们主要介绍了由 戴彧虹 和 袁亚湘 提出的 DY 共轭梯度法，其 $~\beta_k~$ 的参数形式如下
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}(g_k-g_{k-1})}\tag{4}$
表明了其它标准 Wolfe 线搜索下能够建立全局收敛性，进一步，如果在强 Wolfe 线搜索下能够保证其充分下降性。我们还讨论了如果函数 $~f(x)~$ 为严格凸函数（一致凸函数），能够保证下降性（充分下降性）。
在此，我想表明的是，通过以上对 DY 算法的认识还远远不够，我们应该更加深入讨论 DY 共轭梯度法的内在性质，这些性质并不依赖于线搜索的选择和函数的凸性。最后我们利用这些性质，构造出几种特殊的线搜索来建立全局收敛性。

2、DY 共轭梯度法的内在性质
为了严谨，我们都是假定
$g_k\neq 0,~~~\forall ~k\neq 1\tag{5}$
否则，稳定点我们已经得到，迭代算法就会终止。
其次，我们定义两个后面会用到的两个量
$q_k=\frac{\Vert d_k\Vert^2}{(g_k^Td_k)^2}\tag{6}$
$r_k=-\frac{g_k^T d_k}{\Vert g_k\Vert^2}\tag{7}$
其中 $~q_k~$ 可看成一个反映方向 $~d_k~$ 长度的量， $~r_k~$ 则反映 $~d_k~$ 的下降程度。实际上，若 $~r_k>0~$ ，则 $~d_k~$ 是下降方向，若 $~r_k\ge c~$ 对某常数 $~c~$ 成立，则式 $~(7)~$ 表明 $~d_k~$ 是下降方向。
下面的这些东西，其实在上一篇文章的证明过程中也出现过，在此我们还是叙述一下
当 $~k\ge 2~$ 时， $~d_k=-g_k+\beta_k^{DY}d_{k-1}~$ ，两端与 $~g_k~$ 做内积。
$g_k^T d_k=-\Vert g_k\Vert^2+\beta_k^{DY}g_k^T d_{k-1}=\Vert g_k\Vert^2\frac{g_{k-1}^T d_{k-1}}{d_{k-1}^T(g_k-g_{k-1})}=\beta_k^{DY}g_{k-1}^T d_{k-1}\tag{8}$
当 $~k\ge 2~$ 时， $~d_k+g_k=\beta_k d_{k-1}~$ ，两端取模平方并移项，可得
$\Vert d_k\Vert^2=\beta_k^2\Vert d_{k-1}\Vert^2-2g_k^Td_k-\Vert g_k\Vert^2$
将上式除以 $~(g_k^T d_k)^2~$ ，并利用 $~(8)~$ 得
$\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}=\frac{\Vert d_{k-1}\Vert^2}{(g_{k-1}^Td_{k-1})}-\frac{2}{g_k^T d_k}-\frac{\Vert g_k\Vert^2}{(g_k^T d_k)^2}\tag{9}$
利用 $~(6)~$ 和 $~(7)~$ 的定义，则有
$q_{k}=g_{k-1}+\frac{1}{\Vert g_k\Vert^2}\frac{2}{r_k}-\frac{1}{\Vert g_k\Vert^2}\frac{1}{r_k^2}\tag{10}$
因此若 $~r_k>0~$ ，则式 $~(10)~$ 式右端的第二项将使 $~q_{k-1}~$ 增加，第三项将使得 $~q_{k-1}~$ 的值减小，它们关于 $~\frac{1}{r_k}~$ 的量级分别为一阶和二阶。同时考虑这两项，不难看出当且仅当 $~r_k\ge\frac{1}{2}~$ 时， $~q_{k-1}~$ 增加；而当 $~r_k~$ 趋于零时， $~q_{k-1}~$ 将显著减少。由于对所有的 $~k\ge 1~$ ，都有 $~q_k\ge 0~$ ，我们便可以对 $~r_k~$ 的下界进行估计。
我们先给出如下假定，存在正常数 $~\gamma~$ 和 $~\bar{\gamma}~$ 使得
$\gamma\le\Vert g_k\Vert\le\bar{\gamma},~~~\forall~ k\ge 1.\tag{11}$
**
定理1：考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 由 $~(4)~$ 计算， $~d_k~$ 满足 $~g_k^T d_k<0~$ 。若 $~(11)~$ 成立，则存在常数 $~\delta_1~$ ， $~\delta_2~$ 和 $~\delta_3~$ ，使得下述关系式
$-g_k^T d_k\ge\frac{\delta_1}{\sqrt{k}}\tag{12}$
$\Vert d_k\Vert^2\ge\frac{\delta_2}{k}\tag{13}$
$r_k\ge\frac{\delta_3}{\sqrt{k}}\tag{14}$
对所有 $~k\ge 1~$ 都成立.

证明: 利用 $~r_1=1~$ ，对 $~(10)~$ 式求和，得
$q_k=\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}(\frac{2}{r_i}-\frac{1}{r_i^2})\tag{15}$
因为 $~q_k\ge 0~$ ，上式表明
$\frac{1}{\Vert g_k\Vert^2}(-\frac{2}{r_k}+\frac{1}{r_k^2})\le\sum_{i=1}^{k-1}\frac{1}{\Vert g_i\Vert^2}(\frac{2}{r_i}-\frac{1}{r_i^2})\tag{16}$
利用 $~(11)~$ 、 $~(16)~$ 及关系
$\frac{2}{r_i}-\frac{1}{r_i^2}\le 1\tag{17}$
即得
$\frac{1}{r_k^2}-\frac{2}{r_k}-\frac{\bar{\gamma^2}}{\gamma^2}(k-1)\le 0\tag{18}$
从上式及 $~r_k>0~$ ，不难证得
$\frac{1}{r_k}\le 1+\sqrt{1+\frac{\bar{\gamma}^2}{\gamma^2}(k-1)}\le1+\frac{\bar{\gamma}}{\gamma}\sqrt{k}\le\frac{2\bar{\gamma}}{\gamma}\sqrt{k}\tag{19}$
因此对 $~(14)~$ 对 $~\delta_3=\frac{\gamma}{2\bar{\gamma}}~$ ，注意到
$-g_k^T d_k=\Vert g_k\Vert^2r_k\tag{20}$
以及
$\Vert d_k\Vert\ge\Vert g_k\Vert r_k\tag{21}$
即对关系式 $~(13)~$ 和 $~(14)~$ 中的 $~\delta_1=\delta_3\gamma^2~$ 和 $~\delta_2=\delta_3^2\gamma^2~$ 也成立。

**注1****： 在上面的定理中，关系式 $~(14)~$ 并不表明充分下降在每一步都成立。虽然如此，我们可以证明 DY 共轭梯度法的充分下降性质对大部分点列都成立。

定理 2：考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 由 $~(4)~$ 计算， $~d_k~$ 满足 $~g_k^T d_k<0~$ ，若 $~(11)~$ 成立，则对任意的 $~p\in(0,1)~$ ，存在正常数 $~\delta_4~$ ， $~\delta_5~$ ， $~\delta_6~$ ，使得对所有的 $~k\ge 1~$ ，关系式
$-g_i^T d_i\ge \delta_4\tag{22}$
$\Vert d_i\Vert^2\ge\delta_5\tag{23}$
以及
$r_i\ge\delta_6\tag{24}$
对 $~[1,k]~$ 中至少 $~[pk]~$ 个 $~i~$ 成立

证明： 对任意的 $~p\in (0,1)~$ ，我们选取 $~\delta_6>0~$ ，使其满足
$\delta^{'}\triangleq\frac{1}{\delta_6^2}-\frac{2}{\delta_6\gamma}\ge\frac{\bar{\gamma^2}p}{\gamma^2(1-p)}\tag{25}$
对此 $~\delta_6~$ 和任意的 $~k~$ ，定义集合
$I_k=\left\{i\in[1,k]:r_i\ge\delta_6\right\}\tag{26}$
并记 $~\vert I_k\vert~$ 为 $~I_k~$ 中元素的个数，利用 $~(10)~$ 、 $~(11)~$ 以及 $~q_k\ge 0~$ ，不难看出
$\sum_{i\in [1,k]\backslash I_k}(-\frac{2}{r_i}+\frac{1}{r_i^2})\le\frac{\bar{\gamma}^2}{\gamma^2}\sum_{i\in I_k}(\frac{2}{r_i}-\frac{1}{r_i^2})\tag{27}$
于是，由 $~(17)~$ ， $~(27)~$ 以及 $~I_k~$ 的定义可得
$\delta^{'}(k-\vert I_k\vert)\le\frac{\bar{\gamma}^2}{\gamma^2}\vert I_k\vert\tag{28}$
其中 $~\delta^{'}~$ 由 $~(25)~$ 给出，上式和 $~(25)~$ 表明了
$\vert I_k\vert\ge\frac{\delta^{'}\gamma^2}{\delta^{'}\gamma^2+\bar{\gamma}^2}k\ge p k\ge [pk]\tag{29}$
故对任意的 $~p\in (0,1)~$ ，如果选取 $~\delta_6>0~$ 满足 $~(25)~$ 、 $~\delta_4=\delta_6\gamma^2~$ ， $~\delta_5=\delta_6^2\gamma^2~$ ，则从 $~(11)~$ ， $~(20)~$ ， $~(21)~$ 和 $~(29)~$ 知，关系式 $~(22)-(24)~$ 至少对 $~[pk]~$ 个 $~i~$ 都成立。

注2：上述证明证明过程，本人看了很久，奈何水平有限，感觉理解不了。比如式 $~(25)~$ 的定义， $~(27)~$ 和 $~(28)~$ 的推导，就不明白，如果有人了解，还望不吝赐教。

3、DY 共轭梯度法在一般线搜索条件下的全局收敛性

现在设线搜索满足如下较为一般的条件
$f_k-f_{k+1}\ge c\min\left\{-g_k^T d_k,\Vert d_k\Vert^2,q_k^{-1}\right\}\tag{30}$
其中 $~c>0~$ 为常数，而 $~q_k~$ 由 $~(6)~$ 式给出。因为对标准 Wolfe 线搜索可证明
$f_k-f_{k+1}\ge cq_k^{-1}\tag{31}$
对标准 Armijo 线搜索， $~\alpha_k=\max \left\{\lambda^m:m\ge 0,m\in\mathbb{N}\right\}~$ 满足下式
$f(x_k+\alpha_k d_k)-f(x_k)\le\sigma\alpha_k g_k^Td_k$
则有下式成立
$f_k-f_{k+1}\ge c\left\{-g_k^Td_k,q_k^{-1}\right\}\tag{32}$
对另一种 Armijo 型线搜索， $~\alpha_k=\max \left\{\lambda^m:m\ge 0,m\in\mathbb{N}\right\}~$ 满足下式
$f(x_k+\alpha_k d_k)-f(x_k)\le-\delta\alpha_k^2 g_k^Td_k$
则有下式成立
$f_k-f_{k+1}\ge c\min\left\{\Vert d_k\Vert^2,q_k^{-1}\right\}\tag{33}$
其上： $~\lambda,\sigma\in(0,1)，\delta>0~$

注：上面的 $~(31)~$ 其实是标准 Wolfe 显然得出的结论，或许有对 Armijo 型线搜索不熟悉，可以私信交流 $~(32)~$ 和 $~(33)~$ 。以上的分析只是想说明，我们给出的线搜索 $~(30)~$ t条件很好满足而已。

定理3： 设目标函数 $~f(x)~$ 有下界，导函数 $~g(x)~$ 是 $~Lipschitz~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中 $~\beta_k~$ 由 $~(4)~$ 计算， $~d_k~$ 满足 $~g_k^T d_k<0~$ ，而步长因子 $~\alpha_k~$ 满足 $~(30)~$ ，如果存在常数 $~\bar{\gamma}>0~$ ，使得
$\Vert g_k\Vert\le\bar{\gamma},~~\forall ~k\ge 1 \tag{34}$
则方法在下述意义下是全局收敛的：
$\lim_{k\rightarrow\infty}\inf\Vert g_k\Vert=0\tag{35}$

证明： 对 $~(30)~$ 式求和，并注意到 $~f(x)~$ 有下界，得
$\sum_{k\ge 1}\min\left\{-g_k^T d_k,\Vert d_k\Vert^2,q_k^{-1}\right\}\le+\infty\tag{36}$
现用反证法，假设 $~(35)~$ 不成立，即存在常数 $~\gamma>0~$ ，使得
$\Vert g_k\Vert\ge\gamma,~~\forall~k\ge1\tag{37}$
由 定理2 可知，关系式 $~(12)~$ 和 $~(13)~$ 对某正常数 $~\delta_1~$ 和 $~\delta_2~$ 成立，此外，在 $~(15)~$ 中应用 $~(17)~$ 和 $~(37)~$ ，得
$q_k\le q_{k-1}+\frac{1}{\gamma^2}$
上式及 $~q_1=1~$ 表明了
$q_k^{-1}\ge\frac{\gamma^2}{k}\tag{38}$
于是利用 $~(12)~$ 、 $~(13)~$ 和 $~(38)~$ ，得到
$\sum_{k\ge 1}\min \left\{-g_k^T d_k,\Vert d_k\Vert^2,q_k^{-1}\right\}=+\infty$
上式和 $~(36)~$ 相矛盾，则表明 $~(35)~$ 式成立。

4、结束语
其实上面的过程我也看了很久，也有一些不懂的地方，也都用注进行标记，之所以还要写出来，也希望遇见一个研究无约束优化特别是共轭梯度法的朋友，能够相互探讨，相互学习吧。

上面的内容参考 戴彧虹 的文章
[1] New properties of a nonlinear conjugate gradient method. Numerische Matheematik, 89, 83-98.

11、DY 共轭梯度法的内在性质

推荐阅读更多精彩内容