一厂二厂免费大片,亚洲精品蜜桃久久精品

本節(jié)我們將介紹另外一種經(jīng)典的共軛梯度法，即是 $~\rm{HS}~$ 共軛梯度法。

1、引言

??HS 共軛梯度法是由 $\rm{Hestenes}~$ 和 $~\rm{Stiefe}~$ 于1952 年在求解線性共軛梯度法中提出，后來被用于求解非線性無約束優(yōu)化問題。
??共軛梯度法的一般形式為：
$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}$
其中參數(shù) $~\beta_k~$ 由以下公式計(jì)算：
$\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}$ 方法一個(gè)重要的性質(zhì)是，我們令 $~y_{k-1}=g_k-g_{k-1}~$ ，則有如下共軛關(guān)系式成立
$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}~$ 方法的理論性質(zhì)和計(jì)算表現(xiàn)與 $~\rm{PRP}~$ 方法很類似。如果線搜索是精確的，因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=~d_%7Bk-1%7D%5ET%20y_%7Bk-1%7D%3D%5CVert%20g_%7Bk-1%7D%5CVert%5E2~" alt="~d_{k-1}^T y_{k-1}=\Vert g_{k-1}\Vert^2~" mathimg="1">，于是有
$\beta_k^{HS}=\beta_k^{PRP}\tag{5}$
??同樣也有，采取精確線搜索的 $~\rm{HS}~$ 方法對(duì)一般非凸目標(biāo)函數(shù)不一定收斂。如果線搜索滿足
$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}$
設(shè)存在 $~\gamma~$ 和 $~\overline{\gamma}~$ 使得下式成立，即
$0<\gamma\le\Vert g_k\Vert\le\overline{\gamma}\tag{10}$
對(duì)于 $~\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}$
因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=~(11)~" alt="~(11)~" mathimg="1">和 $~(12)~$ ，使得性質(zhì) $(*)$ 成立，令
$\beta_k=\left\{\beta_k^{HS},0\right\}\tag{13}$
則我們便有如下定理，證明過程類似與 $~\rm{PRP}~$ 方法，故省略。

定理 1：設(shè)目標(biāo)函數(shù) $~f(x)~$ 水平集有界，且導(dǎo)數(shù) $~\rm{Lipschitz}~$ 連續(xù)，考慮 $~\rm{HS}^+~$ 方法(1)-(3)，其中步長(zhǎng)因子 $~\alpha_k~$ 滿足 $~\rm{Wolfe}~$ 條件 $~(6)~$ 和 $~(7)~$ 以及充分下降條件 $~(8)~$ ，則方法給出 $~\lim\inf\Vert g_k\Vert=0~$ 。

??在線搜索滿足強(qiáng) $~\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\}$
并在無充分下降條件下，建立了方法的全局收斂性。