查看“梯度下降法”的源代码

{{NoteTA
|G1=Math
}}
'''梯度下降法'''（{{lang-en|Gradient descent}}）是一个一阶[[最优化]][[算法]]，通常也称为'''最速下降法'''。
要使用梯度下降法找到一个函数的[[最值|局部极小值]]，必须向函数上当前点对应[[梯度]]（或者是近似梯度）的''反方向''的规定步长距离点进行[[迭代]]搜索。如果相反地向梯度''正方向''迭代进行搜索，则会接近函数的[[最值|局部极大值]]点；这个过程则被称为'''梯度上升法'''。

==描述==
[[File:gradient descent.png|thumb|350px|梯度下降法的描述。]]

梯度下降方法基于以下的观察：如果实值函数<math>F(\mathbf{x})</math>在点<math>\mathbf{a}</math>处[[可微]]且有定义，那么函数<math>F(\mathbf{x})</math>在<math>\mathbf{a}</math>点沿着[[梯度]]相反的方向  <math>-\nabla F(\mathbf{a})</math>  下降最快。

因而，如果

:<math>\mathbf{b}=\mathbf{a}-\gamma\nabla F(\mathbf{a})</math>

对于<math>\gamma>0</math>為一個够小数值時成立，那么<math>F(\mathbf{a})\geq F(\mathbf{b})</math>。

考虑到这一点，我们可以从函数<math>F</math>的局部极小值的初始估计<math>\mathbf{x}_0</math>出发，并考虑如下序列
<math>\mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots</math>使得

:<math>\mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0</math>。

因此可得到

:<math>F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,</math>

如果顺利的话序列<math>(\mathbf{x}_n)</math>收敛到期望的极值。注意每次迭代''步长''<math>\gamma</math>可以改变。

右侧的图片示例了这一过程，这里假设<math>F</math>定义在平面上，并且函数图像是一个[[碗]]形。蓝色的曲线是[[等高线]]（[[水平集]]），即函数<math>F</math>为常数的集合构成的曲线。红色的箭头指向该点梯度的反方向。（一点处的梯度方向与通过该点的[[等高线]]垂直）。沿着梯度''下降''方向，将最终到达碗底，即函数<math>F</math>值最小的点。

===例子===
梯度下降法处理一些复杂的非线性函数会出现问题，例如[[Rosenbrock函數]]

: <math>f(x, y) =(1-x)^2 + 100(y-x^2)^2 .\quad </math>

其最小值在<math>(x, y)=(1, 1)</math>处，数值为<math>f(x, y)=0</math>。但是此函数具有狭窄弯曲的山谷，最小值<math>(x, y)=(1, 1)</math>就在这些山谷之中，并且谷底很平。优化过程是之字形的向极小值点靠近，速度非常缓慢。

[[File:Banana-SteepDesc.gif|400px|]]

下面这个例子也鲜明的示例了"之字"的'''上升'''（非下降），这个例子用'''梯度上升'''（非梯度下降）法求<math>F(x,y)=\sin\left(\frac{1}{2} x^2 - \frac{1}{4} y^2 + 3 \right) \cos(2 x+1-e^y)</math>的'''极大值'''（非极小值，实际是局部极大值）。

{|
[[File:gradient ascent (contour).png|350px|The gradient descent algorithm in action.（1: contour）]]
[[File:gradient ascent (surface).png|450px|The gradient descent algorithm in action.（2: surface）]]
|}

===缺点===
梯度下降法的缺點包括：<ref>{{cite web|url=http://www.boomer.org/c/p3/c11/c1104.html|title=Steepest Descent Method|language=en|author=David W. A. Bourne|deadurl=yes|archiveurl=https://web.archive.org/web/20090210084038/http://www.boomer.org/c/p3/c11/c1104.html|archivedate=2009年2月10日|df=}}</ref>
*靠近極小值时速度减慢。
*直線搜索可能會產生一些問題。
*可能會“之字型”地下降。

上述例子也已体现出了这些缺点。

==参阅==
{{col-begin}}
{{col-break}}
* [[共轭梯度法]]
* {{le|随机梯度下降法|Stochastic gradient descent}}
* [[最优化]]
{{col-break}}
* [[线搜索]]
*[[反向傳播算法]]
{{col-end}}

==参考文献==
{{reflist}}
* 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

== 外部链接 ==
* {{En}}[http://www.onmyphd.com/?p=gradient.descent Interactive examples of gradient descent and some step size selection methods]
* {{En}}[http://codingplayground.blogspot.it/2013/05/learning-linear-regression-with.html Using gradient descent in C++, Boost, Ublas for linear regression]

{{DEFAULTSORT:Gradient Descent}}
[[Category:最优化算法]]
[[Category:一阶方法]]