梯度下降法

梯度下降法（Gradient descent）或最速下降法（steepest descent）是求解无约束最优化问题的一种常用方法。

假设$f(x)$是$R^n$上具有一阶连续偏导数的函数。要求解的无约束最优化问题是：

$$\displaystyle\min_{x\in R^n} f(x)$$

$x^*$表示目标函数的极小值点。

梯度下降是一种迭代算法。选取适当的初始值$x^{(0)}$，不断迭代，更新$x$的值，进行目标函数的极小化，直到收敛。

梯度的相反方向是使得函数下降最快的方向，因此在迭代的每一步，以负梯度的方向更新$x$的值，从而达到减少函数值的目的。

由于$f(x)$具有一阶连续偏导数，若第$k$次迭代的值为$x^{(k)}$，则可将$f(x)$在$x^{(k)}$附件进行一阶泰勒展开：

$$f(x)=f(x^{(k)})+g^T_k(x-x^{(k)})$$

这里$g_k=g(x^{(k)}=\nabla f(x^{(k)})$为$f(x)$在$x^{(k)}$的梯度。

这里求出第$k+1$次迭代值$x^{(k+1)}$：

$$x^{(k+1)}\gets x^{(k)}+\lambda_k p_k$$

其中$p_k$是搜索方向，取负梯度方向$p_k=-\nabla f(x^{(k)})$，$\lambda_k>0$是步长。

在梯度下降法过程中，可以设置迭代的次数，或者迭代后的精度来决定是否结束迭代。

pic source: https://zh.wikipedia.org/wiki/梯度下降法

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

当目标函数是凸函数时，梯度下降法的解是全局最优解，一般情况下，其解不能保证是全局最优解。梯度下降法的收敛速度也未必是最快的，其他的方法有牛顿法（根据二阶连续偏导数求极值）等。