本页使用了标题或全文手工转换

梯度下降法

维基百科,自由的百科全书
跳转至: 导航搜索

梯度下降法是一个最优化算法,通常也称为最速下降法

描述[编辑]

有關梯度下降法的描述

梯度下降法,基于这样的观察:如果实值函数 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 \ge 0.

因此可得到

F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \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) 就在这些山谷之中,并且谷底很平。优化过程是之字形的向极小值点靠近,速度非常缓慢。

Banana-SteepDesc.gif

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

The gradient descent algorithm in action. (1: contour)The gradient descent algorithm in action. (2: surface)

缺点[编辑]

由上面的兩個例子,梯度下降法的缺點是 [1]:

  • 靠近極小值时速度减慢。
  • 直線搜索可能會產生一些問題。
  • 可能會'之字型'地下降。

参阅[编辑]

参考文献[编辑]

  • 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