數值計算之 線搜索法，Wolfe conditions

• 前言
• 梯度法的步長
• 線搜索法
• 非精確線搜索法
• • Armijo條件
  • Wolfe條件
  • Goldstein條件
• 回溯法
• 后記

前言

本篇是基于梯度的優化方法的補充篇

梯度法的步長

梯度下降法、牛頓法、擬牛頓法的主要目的都是求出增量方向。求出增量方向后，如果使用固定步長進行更新，當步長太大導致優化函數與其泰勒展開偏差太大時，可能出現優化函數不降反增的情況，導致迭代不收斂。

因此在獲得增量方向后，還需要確定迭代的步長。常用的方法是線搜索法。

線搜索法

線搜索法在求出優化函數$f(\mathbf{x})$在${\mathbf{x}}_{\mathbf{k}}$的增量方向后，構建以下問題：
$$\underset{\alpha }{\min }?(\alpha )=f({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}})$$

構造的函數是一元函數，其極值點處的導數為零：
$${?}^{\prime }(\alpha )=?f^T({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}}=0$$
這樣就能獲得步長的精確解，也就是所謂的精確線搜索方法。但是實際操作中，如果梯度沒有解析式，那么上面這個方程的解的計算是很困難的。

非精確線搜索法

非精確線搜索法不需要找到精確的步長，而是希望找到一個能夠使優化函數$f$穩定收斂并且下降速度較快的步長。此時的步長$\alpha$通常存在于一個或數個區間內。

Armijo條件

Armijo條件又被稱為充分下降條件，是使得$f$穩定收斂的充分條件，也是最簡單的條件。

如下圖所示，實線是函數$?(\alpha )=f({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}})$的圖像，虛線$l(\alpha )$表達式為：
$$\begin{gathered} {?}^{\prime }(\alpha )=?f^T({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}} \\ l(\alpha )=?(0)+c_1{?}^{\prime }(0)(\mathbf{x}?{\mathbf{x}}_{\mathbf{k}}),0<c_1<1 \end{gathered}$$
由圖可以看出，當實線在虛線下方時，$?(\alpha )\le ?(0)$，也就是函數必然下降。

這就是Armijo條件，用表達式來表示就是：
$$\begin{gathered} ?(\alpha )\le I(\alpha ) \\ \to f({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}})\le f({\mathbf{x}}_{\mathbf{k}})+c_1\alpha ?f^T({\mathbf{x}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}} \end{gathered}$$

Wolfe條件

Armijo條件有一個問題：雖然能夠保證梯度下降，但是當步長$\alpha$極小的時候，必然能夠滿足Armijo條件，但是下降的速度很慢，而且超小的步長可能導致迭代中的除零錯誤（Nan）。我們需要保證迭代的每一步都有充分的下降。

如下圖所示，如果我們限制${?}^{\prime }(\alpha )\ge c_1{?}^{\prime }(0)$，也就是$?(\alpha )$的斜率不夠陡，達到相對平緩的區域，就形成了Curvature

將Armijo條件與Curvature條件合并，就是Wolfe條件，其表達式如下：
$$\begin{gathered} f({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}})\le f({\mathbf{x}}_{\mathbf{k}})+c_1\alpha ?f^T({\mathbf{x}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}} \\ ?f^T({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}}\ge c_2?f^T({\mathbf{x}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}} \\ 0<c_1<c_2<1 \end{gathered}$$
Wolfe條件如下圖所示：

Goldstein條件

Wolfe條件需要求優化函數的梯度，比較麻煩。于是出現了只需要求優化函數值的Goldstein條件：
$$\begin{gathered} f({\mathbf{x}}_{\mathbf{k}})+(1?c_1)\alpha ?f^T({\mathbf{x}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}}\le f({\mathbf{x}}_{\mathbf{k}}+\alpha {\mathbf{p}}_{\mathbf{k}})\le f({\mathbf{x}}_{\mathbf{k}})+c_1\alpha ?f^T({\mathbf{x}}_{\mathbf{k}}){\mathbf{p}}_{\mathbf{k}} \\ 0<c_1<0.5 \end{gathered}$$
Goldstein條件的左邊使得步長不會太小，右邊保證梯度下降，但是可能出現找不到最優步長的情況，如下圖所示。

回溯法

由于Wolfe條件實現復雜，實際使用中，可以采用回溯法實現Armijo條件或者Goldstein條件，具體流程是：

選擇一個初始步長${\alpha }_0$，和一個縮小系數$\rho <1$

把${\alpha }_0$代入Armijo條件或者Goldstein條件

如果滿足，則$\alpha ={\alpha }_0$，結束線搜索；否則，${\alpha }_0=\rho {\alpha }_0$，回到步驟2

當初始${\alpha }_0$比較大時，回溯法搜索到的步長就不會太小。

后記

下篇可能會繼續學習共軛梯度法。

總結

以上是生活随笔為你收集整理的数值计算之 线搜索法，Armijo，Wolfe，Goldstein条件，回溯法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。