22、HZ 共軛梯度法

??本文將在 DL 共軛梯度法的基礎(chǔ)上，介紹 HZ 共軛梯度法。這是由 Hanger-Zhang 于 2005 年提出的一種非常經(jīng)典的共軛梯度法。我們所創(chuàng)新的共軛梯度法都會于 HZ 共軛梯度法進行數(shù)值實驗對比，所以 HZ 的理論分析就顯得尤為重要了。

1、介紹

??我們的問題是處理一個~n~維變量問題
\min~f(x),~~x\in\mathbb{R}^n\tag{1}
其中~f~是光滑的且~\nabla~f~是可以得到的。共軛梯度法是非常有用的處理問題~(1)~當(dāng)~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-1}, &k\ge 2,\end{cases}\tag{3}
Hanger-Zhang 提出如下參數(shù)~\beta_k~
\beta_k^{HZ}=\frac{g_k^T(y_{k-1}-2d_{k-1}\frac{\Vert y_{k-1}\Vert^2}{d_{k-1}^Ty_{k-1}})}{d_{k-1}y_{k-1}}\tag{4}
為建立對一般函數(shù)的收斂性理論，我們?nèi)?br> \overline{\beta_k}^{HZ}=\max\left\{\beta_k^{HZ},\eta_k\right\}\tag{5}
\eta_k=\frac{-1}{\Vert d_k\Vert\min\left\{\eta,\Vert g_{k-1}\Vert\right\}}\tag{6}
其中~\eta>0~為常數(shù)

2、一般性分析

定理 1：若假定~d_{k-1}^T y_{k-1}\neq 0~和
d_k=-g_k+\tau d_{k-1},~~~d_1=-g_1\tag{7}
其中~\tau\in[\beta_k^{HZ},\max\left\{\beta_k^{HZ},0\right\}]~，則有
g_k^T d_k\le-\frac{7}{8}\Vert g_k\Vert^2\tag{8}
證明：因為~d_1=-g_1~，故~(8)~式顯然成立。假定~\tau=\beta_k^{HZ}~，利用~(7)~式，有
\begin{align}g_k^T d_k&=-\Vert g_k\Vert^2+\beta_k^{HZ}d_{k-1}\\ &=-\Vert g_k\Vert^2+g_k^T d_{k-1}(\frac{g_k^T y_{k-1}}{d_{k-1}^Ty_{k-1}}-2\frac{g_k^T d_{k-1}\Vert y_{k-1}\Vert^2}{(d_{k-1}^T y_{k-1})^2})\\ &=\frac{-\Vert g_k\Vert^2(d_{k-1}^T y_{k-1})^2+g_k^T d_{k-1}d_{k-1}^T y_{k-1}g_k^T y_{k-1}-2(g_k^T d_{k-1})^2\Vert y_{k-1}\Vert^2}{(d_{k-1}^T y_{k-1})^2}\tag{9}\end{align}
我們應(yīng)用不等式
u^T v\le\frac{1}{2}(\Vert u\Vert^2+\Vert v\Vert^2)\tag{10}
在~(9)~中應(yīng)用
u=\frac{1}{2}(d_{k-1}^T y_{k-1})g_k,~~和~~v=2(g_k^T d_{k-1})y_{k-1}\tag{11}
所以~(8)~式成立。如果~\tau\neq \beta_k^{HZ}~，則~\beta_k^{HZ}\le\tau\le 0~，利用~(7)~式，有
g_k^T d_k=-\Vert g_k\Vert^2+\tau g_k^T d_{k-1}\tag{12}
若~g_k^T d_{k-1}\ge 0~，(8)~式顯然成立。如果~g_k^T d_{k-1}<0~，則
g_k^T d_k=-\Vert g_k\Vert^2+\tau g_k^Td_{k-1}\le -\Vert g_k\Vert^2+\beta_k^{HZ}g_k^T d_{k-1}\tag{13}
因為~\beta_k^{HZ}\le\tau\le 0~。因此，(8)~式也成立。證明完畢。
根據(jù)~(6)~式，\eta_k~的非負的，且
\overline{\beta}_k=\left\{\beta_k^N,\eta_k\right\}\in [\beta_k^N,\max \left\{\beta_k^N,0\right\}]\tag{14}
因此，由~(5)~和~(6)~式給出的方向為充分下降方向。

3、一致凸函數(shù)的收斂性分析

??盡管由 HZ 共軛梯度法形成的方向一定是充分下降方向，但是我們還是需要考慮線搜索建立全局收斂性。我們考慮~\rm{Goldstein}~條件
\delta_1\alpha_k g_k^T d_k\le f(x_k+\alpha_k d_k)-f(x_k)\le \delta_2\alpha_k g_k^T d_k\tag{15}
其中~0<\delta_2<\frac{1}{2}<\delta_1<1~和~\alpha_k>0~，或者考慮~\rm{Wolfe}~線搜索
f(x_k+\alpha_k d_k)-f(x_k)\le \delta\alpha_k g_k^T d_k\tag{16}
g(x_k+\alpha_k d_k)^T d_k\ge\sigma g_k^T d_k\tag{17}
其中~0<\delta\le\sigma<1~，這里我們并不需要強~Wolfe~線搜索就可建立全局收斂性。

定理 2：如果~d_k~是下降方向和~\nabla f(x)~滿足~\rm{Lipschitz}~連續(xù)
\Vert \nabla f(x)-\nabla f(y)\Vert\le L\Vert x-y\Vert\tag{18}
其中~\rm{L>0}~為常數(shù)，如果線搜索滿足~\rm{Goldstein}~條件，則
\alpha_k\ge\frac{1-\sigma_1}{L}\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{19}
如果線搜索滿足~\rm{Wolfe}~條件，則
\alpha_k\ge \frac{1-\sigma}{L}\frac{\vert g_k^T d_k\vert}{\Vert d_k\Vert^2}\tag{20}
證明：對~(15)~式利用中值定理和~\rm{Lipschitz}~連續(xù)
\begin{align}\delta_1\alpha_k g_k^T d_k&\le f(x_k+\alpha_k d_k)-f(x_k)\\ &=\alpha_k\nabla f(x_k+t\alpha_k d_k)\\ &\le\alpha_k g_k^T d_k+L\alpha_k^2\Vert d_k\Vert^2\end{align}\tag{21}
其中~t\in (0,1)~，很容易推出~(19)~。
對~(17)~利用~\rm{Lipschitz}~連續(xù)，有
(\sigma-1)g_k^T d_k\le (g_{k+1}-g_k)^T d_k\le\alpha_k L\Vert d_k\Vert^2\tag{22}
因為~d_k~是下降方向且~\sigma<1~，故~(20)~成立。

定理 3：假定~f~在水平集上為一致凸函數(shù)和滿足~\rm{Lipschitz}~連續(xù)，水平集定義為
\Omega=\left\{x\in\mathbb{R}^n:f(x)\le f(x_1)\right\}\tag{23}
即存在~L>0~和~u>0~使得
\Vert \nabla f(x)-\nabla f(y)\Vert\le L\Vert x-y\Vert\tag{24}
u\Vert x-y\Vert^2\le(\nabla f(x)-\nabla f(y))(x-y)\tag{25}
對任何~x,y\in\Omega~都成立。如果共軛梯度法~(2)-(4)~使用線搜索滿足~\rm{Wolfe}~或者~\rm{Goldstein}~線搜索，則要么對某個~k~有~g_k=0~或者
\lim_{k\rightarrow\infty} g_k=0\tag{26}
證明：假定對所有的~k~都有~g_k\neq 0~，利用強收斂性假定
d_{k-1}^T y_{k-1}=d_{k-1}^T(g_k-g_{k-1})\ge u\alpha_{k-1}\Vert d_{k-1}\Vert^2\tag{27}
利用 定理 1 假定~g_k\neq 0~暗示~d_k\neq 0~，因為~\alpha_k>0~，利用~(27)~知道~d_{k-1}^T y_{k-1}>0~。因為~f~在水平集~\Omega~上是有界的。則
\sum_{k=1}^{\infty}-\alpha_k g_k^T d_k\le\infty\tag{28}
結(jié)合 定理 1 和 定理 2，我們有
\sum_{k=1}^{\infty}\frac{\Vert g_k\Vert^4}{\Vert d_k\Vert^2}<\infty\tag{29}
利用~\rm{Lipschitz}~條件~(18)~，有
\Vert y_{k-1}\Vert\le\Vert g_k-g_{k-1}\Vert\le L\alpha_{k-1}\Vert d_{k-1}\Vert\tag{30}
利用~(4),(27),(30)~有
\begin{align}\vert\beta_k^{HZ}\vert&=\vert \frac{g_k^T y_{k-1}}{d_{k-1}y_{k-1}}-2\frac{\Vert y_{k-1}\Vert^2g_k^T d_{k-1}}{(d_{k-1}^T y_{k-1})^2}\vert\\ &\le\frac{\Vert y_{k-1}\Vert\Vert g_k\Vert}{u\alpha_{k-1}\Vert d_{k-1}\Vert^2}+2\frac{\Vert y_{k-1}\Vert^2\Vert g_k\Vert\Vert d_{k-1}\Vert}{u^2\alpha_{k-1}^2\Vert d_{k-1}\Vert^4}\\ &\le\frac{L\alpha_{k-1}\Vert g_k\Vert\Vert d_{k-1}\Vert}{u\alpha_{k-1}\Vert d_{k-1}\Vert^2}+2\frac{L^2\alpha_{k-1}^2\Vert d_{k-1}\Vert^2\Vert g_k\Vert}{u^2\alpha_{k-1}^2\Vert d_{k-1}\Vert^4}\\ &\le(\frac{L}{u}+\frac{2L^2}{u^2})\frac{\Vert g_k\Vert}{\Vert d_{k-1}\Vert} \end{align}\tag{31}
因此，我們有
\begin{align}\Vert d_k\Vert&\le\Vert g_k\Vert+\vert \beta_k^{HZ}\vert\Vert d_{k-1}\Vert\\ &\le(1+\frac{L}{u}+\frac{2L^2}{u^2})\Vert g_k\Vert\end{align}\tag{32}
由~(32)~可以看出~\Vert d_k\Vert~有上界，利用~(29)~式，有
\sum_{k=1}^{\infty}\Vert g_k\Vert^2<\infty\tag{33}
從而~(26)~式成立。

4、一般函數(shù)的收斂性分析

定理 4：若水平集~(23)~有界和~\rm{Lipschitz}~連續(xù)~(24)~成立，如果共軛梯度法~(2)-(6)~選擇~\rm{Wolfe}~線搜索~(16)~和~(17)~，則有
d_k\neq 0,~~\forall~k\ge 1\tag{34}
和
\sum_{k=1}^{\infty}\Vert u_{k+1}-u_k\Vert^2<\infty\tag{35}
其中~u_k=\frac{d_k}{\Vert d_k\Vert}~而且假定~\Vert g_k\Vert\ge\gamma>0~。
證明：利用假定和下降條件，可知~(34)~成立。且利用充分下降條件~(8)~和~\rm{Zoutendijk}~條件~(29)~，有
\gamma^4\sum_{k=1}^{\infty}\frac{1}{\Vert d_k\Vert^2}\le\sum_{k=1}^{\infty}\frac{\Vert g_k\Vert^4}{\Vert d_k\Vert^2}\le\frac{49}{64}\sum_{k\ge 1}^{\infty}\frac{(g_k^T d_k)^2}{\Vert d_k\Vert^2}<\infty\tag{36}
定義等式
\beta_k^+=\max\left\{\overline{\beta}_k^{HZ},0\right\},~~\beta_k^+=\min\left\{\overline{\beta}_k^{HZ},0\right\}\tag{37}
r_k=\frac{-g_k+\beta_k^-d_{k-1}}{\Vert d_k\Vert},~~\delta_k=\beta_k^+\frac{\Vert d_{k-1}\Vert}{\Vert d_k\Vert}\tag{38}
根據(jù)~(3)~和~(5),(6)~的定義
u_k=\frac{d_k}{\Vert d_k\Vert}=\frac{-g_k+(\beta_k^++\beta_k^-)d_{k-1}}{\Vert d_k\Vert}=r_k+\delta_k u_{k-1}\tag{39}
因為~u_k~是單位向量，故有
\Vert r_k\Vert=\Vert u_k-\delta_k u_{k-1}\Vert=\Vert \delta_k u_k-u_{k-1}\Vert\tag{40}
由于~\delta_k>0~，則
\begin{align}\Vert u_k-u_{k-1}\Vert &\le\Vert (1+\delta_k)(u_k-u_{k-1})\Vert\\ &\le\Vert u_k-\delta_ku_{k-1}\Vert+\Vert \delta_k u_k-u_{k-1}\Vert\\ &=2\Vert r_k\Vert\end{align}\tag{41}
根據(jù)~\beta_k^-~的定義和~\eta_k<0~以及~(5)~式中~\overline{\beta}_k^{HZ}\ge\eta_k~，我們可以得到~r_k~的分子有界。
\begin{align}\Vert -g_k+\beta_k^- d_{k-1}\Vert&\le\Vert g_k\Vert-\min\left\{\overline{\beta_k}^{HZ},0\right\}\Vert d_{k-1}\Vert\\ &\le\Vert g_k\Vert-\eta_{k-1}\Vert d_{k-1}\Vert\\ &\le\Vert g_k\Vert+\frac{1}{\Vert d_{k-1}\Vert\min\left\{\eta,\gamma\right\}}\Vert d_{k-1}\Vert\\ &\le\overline{\gamma}+\frac{1}{\min\left\{\eta,\gamma\right\}}\end{align}\tag{42}
其中
\overline{\gamma}=\max_{x\in \Omega}\Vert \nabla f(x)\Vert\tag{43}
我們令~c=\overline{\gamma}+\frac{1}{\min\left\{\eta,\gamma\right\}}~，利用~(41)~，則有
\Vert u_k-u_{k-1}\Vert\le 2\Vert r_k\Vert\le\frac{2c}{\Vert d_k\Vert}\tag{44}
利用~(36)~和~(44)~式，則命題得證。

定理 5：若水平集~(23)~有界和~\rm{Lipschitz}~連續(xù)~(24)~成立，如果共軛梯度法~(2)-(6)~選擇~\rm{Wolfe}~線搜索~(16)~和~(17)~，則或者對某個~k~使得~g_k=0~，或者
\lim\inf\Vert g_k\Vert=0\tag{45}
證明：我們首先假定
\Vert g_k\Vert\ge\gamma>0\tag{46}
否則，穩(wěn)定點已經(jīng)得到。下面的證明分為三步

(i)：~\overline{\beta}_k^{HZ}~有界
通過~\rm{Wolfe}~線搜索~(17)~可知~g_{k+1}^T d_k\ge\sigma g_k^T d_k~，我們有
d_{k-1}^T y_{k-1}=(g_k-g_{k-1})^T d_{k-1}\ge (\sigma-1)g_{k-1}^T d_{k-1}=-(1-\sigma)g_{k-1}^T d_{k-1}\tag{47}
由 定理 1 和~(46)~可知
-g_k^T d_k\ge\frac{7}{8}\Vert g_k\Vert^2\ge\frac{7}{8}\gamma^2\tag{48}
結(jié)合~(47)~和~(48)~有
d_{k-1}^T y_{k-1}\ge (1-\sigma)\frac{7}{8}\gamma^2\tag{49}
一方面，有
g_k^T d_{k-1}=d_{k-1}^T y_{k-1}+g_{k-1}^T d_{k-1}<d_{k-1}^T y_{k-1}\tag{50}
另一方面，利用~\rm{Wolfe}~線搜索知
g_k^T d_{k-1}\ge\sigma g_{k-1}^T d_{k-1}=-\sigma d_{k-1}^T y_{k-1}+\sigma g_k^T d_{k-1}\tag{51}
因為~\sigma<1~，結(jié)合~(51)~有
g_k^T d_{k-1}\ge\frac{-\sigma}{1-\sigma}d_{k-1}^T y_{k-1}\tag{52}
利用~(50)~和~(52)~有
\vert\frac{g_k^T d_{k-1}}{d_{k-1}^T y_{k-1}}\vert\le\max\left\{\frac{\sigma}{1-\sigma},1\right\}\tag{53}
通過~(5)~式中~\beta_k^{HZ}~的定義，有
\overline{\beta}_k^{HZ}=\beta_k^{HZ},~如果~\beta_k^{HZ}\ge 0
0\ge\overline{\beta}_k^{HZ}\ge\beta_k^{HZ},~~如果~\beta_k^{HZ}< 0
因此~\vert \overline{\beta}_k^{HZ}\vert\le\vert\beta_k^{HZ}\vert~對任意的~k~都成立，利用~(30),(47),(53)~以及上面的分析，有
\begin{align}\vert\overline{\beta}_k^{HZ}\vert&\le\vert \beta_k^{HZ}\vert\\ &\le\frac{1}{d_{k-1}^T y_{k-1}}(\vert g_k^T y_{k-1}\vert+2\Vert y_{k-1}\Vert^2\frac{\vert g_k^T d_{k-1}\vert}{\vert d_{k-1}^T y_{k-1}\vert})\\ &\le\frac{8}{7}\frac{1}{(1-\sigma)\gamma^2}(L\overline{\gamma}\Vert s_{k-1}\Vert+2\overline{\gamma}^2\Vert s_{k-1}\Vert^2\max\left\{\frac{\sigma}{1-\sigma},1\right\})\\ &\le C\Vert s_{k-1}\Vert \end{align}\tag{54}
其中
C=\frac{8}{7}\frac{1}{(1-\sigma)}(L\overline{\gamma}+2L^2D\max\left\{\frac{\sigma}{1-\sigma},1\right\})\tag{55}
D=\max\left\{\Vert y-z\Vert:x,y\in\Omega \right\}\tag{56}
(ii)：步長~s_k~的界
對于任意的~l>k~，有
x_l-x_k=\sum_{j=k}^{l-1}x_{j+1}-x_j=\sum_{j=k}^l\Vert s_j\Vert u_j=\sum_{j=k}^{l-1}\Vert s_j\Vert u_k+\sum_{j=k}^{l-1}\Vert s_j\Vert(u_j-u_k)\tag{57}
利用三角不等式
\sum_{j=k}^{l-1}\Vert s_j\Vert\le\Vert x_l-x_{k+1}\Vert+\sum_{j=k}^{l-1}\Vert s_j\Vert\Vert u_j-u_i\Vert\le D+\sum_{j=k}^{l-1}\Vert u_j-u_k\Vert\tag{58}
選擇正整數(shù)~\triangle~，使其充分大
\triangle\ge 4 C D\tag{59}
其中~C,D~為~(55)~和~(56)~中的定義，選擇充分大的~k_0~使其滿足
\sum_{i\ge k_0}\Vert u_{i+1}-u_i\Vert^2\le\frac{1}{4\triangle}\tag{60}
如果~j>k\ge k_0~和~j-k\le\triangle~，則
\begin{align}\Vert u_j-u_k\Vert&\le\sum_{i=k}^{j-1}\Vert u_{i+1}-u_i\Vert\\ &\sqrt{j-k}(\sum_{i=k}^{j=1}\Vert u_{i+1}-u_i\Vert^2)^{\frac{1}{2}}\\ &\le\sqrt{\triangle}(\frac{1}{4\triangle})^{\frac{1}{2}}=\frac{1}{2}\end{align}\tag{61}
結(jié)合~(58)~有
\sum_{j=k}^{l-1}\Vert s_j\Vert\le 2D\tag{62}
其中~l>k\ge k_0~且~l-k\le\triangle~。

(III)、證明~d_l~有界
??證明略，本人也沒有看的太懂，只是其實可以參考 PRP 或者 DL 的證明，也沒有必要這么證明，所以就不想看了。不管怎樣，Hanger-Zhang 共軛梯度法還是非常經(jīng)典的共軛梯度法。

5、參考文獻

[1] Hager W W, Zhang H C. A new conjugate gradient method with guaranteed descent and an efficient line search, SIAM Journal on Optimization, 2005, 1(16) : 170-192.

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容