18、HS 共轭梯度法

本节我们将介绍另外一种经典的共轭梯度法，即是 $~\rm{HS}~$ 共轭梯度法。

1、引言

HS 共轭梯度法是由 $\rm{Hestenes}~$ 和 $~\rm{Stiefe}~$ 于1952 年在求解线性共轭梯度法中提出，后来被用于求解非线性无约束优化问题。
共轭梯度法的一般形式为：
$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^{HS}=\frac{g_k^T(g_k-g_{k-1})}{d_{k-1}^T(g_k-g_{k-1})}.\tag{3}$

2、收敛性分析

我们把方法 $~(1)-(3)~$ 称为 $~\rm{HS}~$ 方法。与 $~\rm{PRP}~$ 方法相比， $\rm{HS}$ 方法一个重要的性质是，我们令 $~y_{k-1}=g_k-g_{k-1}~$ ，则有如下共轭关系式成立
$d_{k}^Ty_{k-1}=0\tag{4}$
证明： $\begin{align}d_{k}^Ty_{k-1}&=(-g_k+\beta_k^{HS} d_{k-1})^Ty_{k-1}\\ &=-g_k^Ty_{k-1}+\frac{g_k^T y_{k-1}}{d_{k-1}^Ty_{k-1}}d_{k-1}^Ty_{k-1}=0\end{align}$
上面 $~(4)~$ 式不论线搜索是否精确，总是成立的。但 $~\rm{HS}~$ 方法的理论性质和计算表现与 $~\rm{PRP}~$ 方法很类似。如果线搜索是精确的，因为 $~d_{k-1}^T y_{k-1}=\Vert g_{k-1}\Vert^2~$ ，于是有
$\beta_k^{HS}=\beta_k^{PRP}\tag{5}$
同样也有，采取精确线搜索的 $~\rm{HS}~$ 方法对一般非凸目标函数不一定收敛。如果线搜索满足
$f(x_k+\alpha_k d_k)\le f(x_k)+\rho\alpha_k g_k^T d_k\tag{6}$
和
$g(x_k+\alpha_k d_k)^T d_k\ge\sigma g_k^T d_k\tag{7}$
其中 $~0<\rho<\sigma<1~$ ，以及线搜索使得充分下降条件成立，即存在 $~c>0~$ ，使得
$-g_k^T d_k\ge c\Vert g_k\Vert^2\tag{8}$
则显然有下式成立
$d_{k-1}^T y_{k-1}\ge(1-\sigma)\vert g_{k-1}^T d_{k-1}\vert\ge (1-\sigma)c\Vert g_{k-1}\Vert^2\tag{9}$
设存在 $~\gamma~$ 和 $~\overline{\gamma}~$ 使得下式成立，即
$0<\gamma\le\Vert g_k\Vert\le\overline{\gamma}\tag{10}$
对于 $~\rm{HS}~$ 方法，可以取
$b=\frac{2\overline{\gamma}^2}{(1-\sigma)c\gamma^2}\tag{11}$
以及
$\lambda=\frac{(1-\sigma)c\gamma^2}{2L\overline{\gamma}b}\tag{12}$
因为 $~(11)~$ 和 $~(12)~$ ，使得性质 $(*)$ 成立，令
$\beta_k=\left\{\beta_k^{HS},0\right\}\tag{13}$
则我们便有如下定理，证明过程类似与 $~\rm{PRP}~$ 方法，故省略。

定理 1：设目标函数 $~f(x)~$ 水平集有界，且导数 $~\rm{Lipschitz}~$ 连续，考虑 $~\rm{HS}^+~$ 方法(1)-(3)，其中步长因子 $~\alpha_k~$ 满足 $~\rm{Wolfe}~$ 条件 $~(6)~$ 和 $~(7)~$ 以及充分下降条件 $~(8)~$ ，则方法给出 $~\lim\inf\Vert g_k\Vert=0~$ 。

在线搜索满足强 $~\rm{Wolfe}~$ 条件的假定下，我们知道可以将 $~\rm{PRP}^{+}~$ 共轭梯度法中的充分下降条件改为下降条件。戚后铎 $^{[1]}$ 考虑了如下修正的 $~\rm{HS}~$ 方法：
$\beta_k=\max\left\{0,\min\left\{\beta_k^{HS},\frac{1}{\Vert g_k\Vert}\right\}\right\}$
并在无充分下降条件下，建立了方法的全局收敛性。

3、参考文献

[1] 戚后铎, 韩继页, 刘光辉. 修正 $~\rm{Hestense-Stiefel}~$ 共轭梯度法. 数学年刊, 1996(3): 277-284.
[2] 戴彧虹. 非线性共轭梯度法. 2000, 科学出版社.