梯度下降法

梯度下降法（英語：Gradient descent）是一個一階最優化算法，通常也稱為最陡下降法，但是不該與近似積分的最陡下降法（英語：Method of steepest descent）混淆。 要使用梯度下降法找到一個函數的局部極小值，必須向函數上當前點對應梯度（或者是近似梯度）的反方向的規定步長距離點進行迭代搜索。如果相反地向梯度正方向迭代進行搜索，則會接近函數的局部極大值點；這個過程則被稱為梯度上升法。

描述

梯度下降法的描述。

梯度下降方法基於以下的觀察：如果實值函數$F(\mathbf {x} )$在點$\mathbf {a}$處可微且有定義，那麼函數$F(\mathbf {x} )$在$\mathbf {a}$點沿着梯度相反的方向 $-\nabla F(\mathbf {a} )$ 下降最多。

因而，如果

$\mathbf {b} =\mathbf {a} -\gamma \nabla F(\mathbf {a} )$

對於一個足夠小數值$\gamma >0$時成立，那麼$F(\mathbf {a} )\geq F(\mathbf {b} )$。

考慮到這一點，我們可以從函數$F$的局部極小值的初始估計$\mathbf {x} _{0}$出發，並考慮如下序列 $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots$使得

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0$。

因此可得到

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

如果順利的話序列$(\mathbf {x} _{n})$收斂到期望的局部極小值。注意每次迭代步長$\gamma$可以改變。

右側的圖片示例了這一過程，這裡假設$F$定義在平面上，並且函數圖像是一個碗形。藍色的曲線是等高線（水平集），即函數$F$為常數的集合構成的曲線。紅色的箭頭指向該點梯度的反方向。（一點處的梯度方向與通過該點的等高線垂直）。沿着梯度下降方向，將最終到達碗底，即函數$F$局部極小值的點。

例子

梯度下降法處理一些複雜的非線性函數會出現問題，例如Rosenbrock函數

$f(x,y)=(1-x)^{2}+100(y-x^{2})^{2}.\quad$

其最小值在$(x,y)=(1,1)$處，數值為$f(x,y)=0$。但是此函數具有狹窄彎曲的山谷，最小值$(x,y)=(1,1)$就在這些山谷之中，並且谷底很平。優化過程是之字形的向極小值點靠近，速度非常緩慢。

下面這個例子也鮮明的示例了"之字"的上升（非下降），這個例子用梯度上升（非梯度下降）法求$F(x,y)=\sin \left({\frac {1}{2}}x^{2}-{\frac {1}{4}}y^{2}+3\right)\cos(2x+1-e^{y})$的局部極大值（非局部極小值）。

|}

缺點

梯度下降法的缺點包括：

• 靠近局部極小值時速度減慢。
• 直線搜索可能會產生一些問題。
• 可能會「之字型」地下降。

上述例子也已體現出了這些缺點。

參閱

• 共軛梯度法
• 隨機梯度下降法
• 最優化

• 線搜索
• 反向傳播算法
• 量子退火

參考文獻

• Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Jan A. Snyman (2005). Practical Mathematical Optimization: An Introduction to Basic Optimization Theory and Classical and New Gradient-Based Algorithms. Springer Publishing. ISBN 0-387-24348-8

外部連結

• （英文）Interactive examples of gradient descent and some step size selection methods （頁面存檔備份，存於網際網路檔案館）
• （英文）Using gradient descent in C++, Boost, Ublas for linear regression （頁面存檔備份，存於網際網路檔案館）