8、CD 共轭梯度法

前面介绍了 FR 共轭梯度法，给出了其他不同线搜素下的全局收敛性。本节将讲述 CD 共轭梯度法，与 FR 的性质相类似，有了前面的基础，所以收敛性的证明很简单。
1987 年，Fletcher $^{[1]}$ 提出了 CD 共轭梯度法，也被称为共轭下降法。这种算法的独特优点在于使用强 Wolfe 条件，CD 共轭梯度法显然满足充分下降性，显然对于 FR 共轭梯度法这是不能办到的。

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,&k=1,\\-g_k+\beta_k d_{k-1},&k\ge2,\end{cases}\tag{3}$
其中 $~\beta_k~$ 是参数。不同的 $~\beta_k~$ 决定不同的共轭梯度法。
1987 年，Fletcher $^{[1]}$ 提出了 CD 共轭梯度法，其形式为
$\beta_k=\frac{\Vert g_k\Vert^2}{-g_{k-1}^Td_{k-1}}\tag{4}$
我们考虑推广的 Wolfe 线搜素，其条件为
$f(x_k)-f(x_k+\alpha_kd_k)\ge -\rho\alpha_kg_k^T d_k\tag{5}$
$\sigma_1g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le-\sigma_2g_k^T d_k\tag{6}$
其中参数 $~0<\rho<\sigma_1<1~$ 以及 $~0\le\sigma_2<1~$ 。显然，如果 $~\sigma_1=\sigma_2~$ ，则上述搜素条件就是强 Wolfe 条件，由 (3) 和 (4)，知
$-g_k^T d_k=\Vert g_k\Vert^2(1+\frac{g_k^Td_{k-1}}{g_{k-1}^T d_{k-1}})$
利用上式和 (6) 式，得
$1-\sigma_2\le\frac{-g_k^T d_k}{\Vert g_k\Vert^2}\le 1+\sigma_1\tag{7}$
从上式中的第一个不等式及 $~\sigma_2<1~$ ，则 $~d_k~$ 必为下降方向，并使得充分下降条件
$-g_k^T d_k\ge c\Vert g_k\Vert^2\tag{8}$
对某常数 $~c>0~$ 成立
在充分下降条件 (8) 和 Zoutendijk 条件成立的情况下，如果
$\sum_{k\ge 1}\frac{\Vert g_k\Vert^t}{\Vert d_k\Vert^2}=\infty\tag{9}$
对某 $~t\in [0,4]~$ 成立，不难推知收敛关系式 $~\lim\inf\Vert g_k\Vert=0~$ 成立。 $\color{red}{对于采取强 \rm{Wolfe} 非精确线搜素的共轭梯度法，下节我们给出一个一般性的定理。}$
$\color{red}{该定理表明，只要搜素方向下降，即}$
$\color{red}{g_k^T d_k<0,~~\forall~k\ge 1}$
$\color{red}{则 ~(9)~即可保证形如 (2) 和 (3) 方法的收敛性。这一结果并不需要方向 ~\rm{d_k}~是充分下降条件，而且适用于一般的共轭梯度法。 }$
设线搜素条件 (5) 和 (6) 中的参数满足
$\sigma_1<1,~~~\sigma_2=0\tag{10}$
根据 $~\beta_k^{FR}=\frac{\Vert g_k\Vert^2}{\Vert g_{k-1}\Vert^2}~$ 和 (4) 式及 (7) 式，不难看出
$0\le\beta^{CD}\le\beta_k^{FR}$
这时，类似于 FR 的收敛性，可证明
$\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\le c\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}$
对某常数 $~c>0~$ 成立，故如果方法不收敛，序列 $~\left\{\frac{\Vert d_k\Vert^2}{\Vert g_k\Vert^4}\right\}~$ 最多线性增长，从而 (9) 式成立，则 $~\lim\inf\Vert g_k\Vert=0~$ ，导致矛盾，因此当参数 $~\sigma_1~$ 和 $~\sigma_2~$ 满足 (10) 式时，共轭下降法必全局收敛。

2、收敛性分析

定理：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑 CD 共轭梯度法 $~\rm{(2)-(4)}~$ ，其中步长因子 $~\alpha_k~$ 满足推广的 $\rm{Wolfe}$ 线搜素 $~\rm{(5)-(6)}~$ 。如果 $~\sigma_1<1~$ 且 $~\sigma_2=0~$ ，则有 $~\lim\inf\Vert g_k\Vert=0~$ 。

注：上述定理证明很简单，类似于 FR 共轭梯度法，不在此给出。对于 $~\sigma_1\ge 1~$ 和 $~\sigma_2>0~$ ，戴彧虹表明 CD 共轭梯度法会不收敛，因此 (10) 中的条件对于 CD 共轭梯度法的收敛性是充分必要的。这些反例的构造挺难的，我个人感觉不是很重要，也不想给出。

3、参考文献

[1] Fletcher R. Practical methods of optimization, vol I: unconstrained optimization[M]. New York: John Wiley and Sons, 1987.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.

8、CD 共轭梯度法

1、简介

2、收敛性分析

3、参考文献

推荐阅读更多精彩内容