12、DY 共轭梯度法的一般性理论

本文与之前的 FR 共轭梯度法的一般性理论相类似，旨在建立 DY 共轭梯度法的一般性理论。这些工作也是由 戴彧虹 和 袁亚湘 完成。

1、简介

对于无约束优化问题
$\min_{x\in\mathbb{R}^n}~f(x)\tag{1}$
其中 $~f(x):\mathbb{R}^n\rightarrow\mathbb{R}~$ 是连续可微函数，其梯度函数记为 $~g(x):\mathbb{R}\rightarrow\mathbb{R}^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}$
其中 $~g_k~$ 是迭代点 $~x_k~$ 处的梯度， $~\alpha_k~$ 是搜素步长， $~d_k~$ 是搜素方向， $~\beta_k~$ 为共轭参数。
考虑一般的 $~\beta_k~$ 与 $~\beta_k^{DY}~$ 的关系，定义
$\tau_k=\frac{\beta_k}{\beta_k^{DY}}\tag{4}$
$\beta_k^{DY}=\frac{\Vert g_k\Vert^2}{d_{k-1}^T(g_k-g_{k-1})}\tag{5}$
考虑 $~\rm{Wolfe}~$ 线搜索，即
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k d_k\tag{6}$
$g(x_k+\alpha_k d_k)^Td_k\ge\sigma g_k d_k\tag{7}$

2、收敛性分析

定理：设目标函数 $~f(x)~$ 下方有界，导数 $~\rm{Lipschitz}~$ 连续，考虑方法 $~(2)~$ 和 $~(3)~$ ，其中步长 $~\alpha_k~$ 满足 $~\rm{Wolfe}~$ 条件 $~(6)~$ 和 $~(7)~$ ，参数 $~\beta_k~$ 使得
$\tau_k\in[-\frac{1-\sigma}{1+\sigma},1]\tag{8}$
成立，则有
$~\lim\inf\Vert g_k\Vert=0\tag{9}$
证明：将 $~(3)~$ 两端与 $~g_k~$ 作内积，并利用 $~(4)~$ 和 $~(5)~$ ，得
$g_k^T d_k=\frac{g_{k-1}^T d_{k-1}+(\tau_k-1)g_k^T d_{}k-1}{d_{k-1}^T (g_k-g_{k-1})}\Vert g_k\Vert^2\tag{10}$
再次应用 $~(4)~$ 和 $~(5)~$ ，并利用 $~(10)~$ ，知
$\beta_k=\tau_k\beta_k^{DY}=\frac{\tau_kg_k^T d_k}{g_{k-1}^T d_{k-1}+(\tau_k-1)g_k^T d_{k-1}}=\zeta_k\frac{g_k^T d_k}{g_{k-1}^T d_{k-1}}\tag{11}$
其中
$\zeta_k=\frac{\tau_k}{1+(\tau_k-1)l_{k-1}}\tag{12}$
$l_{k-1}=\frac{g_k^T d_{k-1}}{g_{k-1}^T d_{k-1}}\tag{13}$
令 $~r_k=-\frac{g_k^T d_k}{\Vert g_k\Vert^2}~$ ，则由 $~(10)~$ 式得
$r_k=\frac{1+(\tau_k-1)l_{k-1}}{1-l_{k-1}}\tag{14}$
由于 $~d_1=-g_1~$ ，故 $~r_1=1>0~$ 。设 $~r_{k-1}>0~$ ，故
$l_{k-1}\le\sigma\tag{15}$
利用 $~(14)~$ 和上式，得
$1+(\tau_k-1)l_{k-1}\ge 1+(-\frac{1-\sigma}{1+\sigma}-1)\sigma=\frac{1-\sigma}{1+\sigma}\tag{16}$
注意到 $~\sigma<1~$ ，故 $~r_k>0~$ ，从而根据归纳法， $~r_k>0~$ 对所有的 $~k\ge 1~$ 成立。
进一步，由 $(8)$ 和 $(16)$ ，有
$1+(\tau_k-1)l_{k-1}\ge-\tau_k\tag{17}$
另一方面，利用 $~(15)~$ 以及 $~\tau_k\le 1~$ ，知
$(1-\tau_k)(1-l_{k-1})\ge 0\tag{18}$
或者等价地，
$1+(\tau_k-1)l_{k-1}\ge\tau_k\tag{19}$
结合 $~(17)~$ 和 $~(19)~$ 两式，得
$\vert 1+(\tau_k-1)l_{k-1}\vert\ge\vert \tau_k\vert\tag{20}$
根据 $~\zeta_k~$ 的定义，必有
$\vert \zeta_k\vert\le 1\tag{21}$
故有
$\beta_k^2\le\frac{(g_k^T d_k)^2}{(g_{k-1}^T d_{k-1})^2}\tag{22}$
假定命题不成立，即存在 $~\gamma>0~$ ，对任意的 $~k\ge 1~$
$\Vert g_k\Vert\ge\gamma\tag{23}$
因为 $~d_k+g_k=\beta_k d_{k-1}~$ ，利用 $~(22)~$ 有
$\begin{align}\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}&=\frac{\beta_k^2\Vert d_{k-1}\Vert^2}{(g_k^T d_k)^2}-\frac{\Vert g_k\Vert^2}{(g_k^T d_k)^2}-\frac{2}{g_k^T d_k}\\ &=\frac{\beta_k^2\Vert d_{k-1}\Vert^2}{(g_k^T d_k)^2}-(\frac{\Vert g_k\Vert}{g_k^T d_k}+\frac{1}{\Vert g_k\Vert})^2+\frac{1}{\Vert g_k\Vert^2}\\ &\le\frac{\beta_k^2\Vert d_{k-1}\Vert^2}{(g_k^T d_k)^2}+\frac{1}{\Vert g_k\Vert^2}\\ &\le\frac{\Vert d_{k-1}\Vert^2}{(g_{k-1}^T d_{k-1})^2}+\frac{1}{\Vert g_k\Vert^2}\end{align}\tag{24}$
根据递推，所有有
$\frac{\Vert d_k\Vert^2}{(g_k^T d_k)^2}\le\sum_{i=1}^k\frac{1}{\Vert g_i\Vert^2}\tag{25}$
利用 $~(23)~$ 和 $~(25)~$ ，我们有
$\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}\ge\frac{\gamma^2}{k}\tag{26}$
根据 $~(26)~$ 有
$\sum_{k\ge 1}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}=\infty$
上式和 $~\rm{Zoutendijk}~$ 条件相矛盾，故假设不成立。命题得证

注：这个结论非常有用，戴彧虹和袁亚湘还表明，这个 $\tau_k\in[-\frac{1-\sigma}{1+\sigma},1]$ 这个界限在常数意义下是最优的，否则，会有反列。

利用上面定理，我们定义 $\rm{DY}$ 方法与 $\rm{HS}$ 方法的如下杂交共轭梯度法，其中 $~\rm{b}~$ 为参数
$\beta_k=\begin{cases} &-b\beta_k^{DY},~~&当~~\beta_k^{HS}<-b\beta_k^{DY}\\ &\beta_k^{HS},~~&当~~-b\beta_k^{DY}\le\beta_k^{HS}\le\beta_k^{DY}\\ &\beta_k^{DY},~~&当~~\beta_k^{HS}>\beta_k^{DY} \end{cases}$
分别取 $~b=\frac{1-\sigma}{1+\sigma}~$ 和 $~b=0~$ ，对每一种取值分别使用 $~\rm{Wolfe}~$ 线搜索和强 $~\rm{Wolfe}~$ 线搜索测试上面杂交算法。数值结果表明，当 $~\rm{b=0}~$ 并使用 $~\rm{Wolfe}~$ 线搜索时，上述杂交算法的计算效果最为理想，可以与 $~\rm{PRP}~$ 算法媲美，对于比较困难的优化问题，计算效果比 $~\rm{PRP}~$ 方法好得多。这表明在共轭梯度法领域中不使用传统的强 $~\rm{Wolfe}~$ 线搜索，而仅使用 $~\rm{Wolfe}~$ 线搜索，也能得到数值表现良好的共轭梯度法。
如果线搜索条件为 $~(6)~$ 和
$\sigma g_k^T d_k\le g(x_k+\alpha_k d_k)^T d_k\le 0$
其中 $~0<\rho<\sigma<1~$ ，这时利用上面线搜索与 $~\beta_k^{CD}~$ 和 $~\beta_k^{DY}~$ 的定义，知
$0\le\beta_k^{CD}\le\beta_k^{DY}$
根据上面定理，我们可以得出共轭下降法的收敛性理论，内容就不写了。

3、结束语

在此还想强调一下，上面定理非常有用。本文的参考文献如下
[1] Dai Y H , Yuan Y X. An efficient hybrid conjugate gradient method for unconstrained optimization[J]. 2001, Annals of Operations Research, 103, 33-47.
[2] 戴彧虹. 非线性共轭梯度法[M]. 科学出版社, 2000.

12、DY 共轭梯度法的一般性理论