[toc]

本文介绍几种求解无约束优化问题的基础算法，我们要求解如下形式的问题$$\min f(x),\quad x\in R^n,$$$f(x)$至少一阶可微。本文只介绍每个算法的基本步骤与推导形式，对于一些结论不作证明。我们一般采用基于迭代的方法来求解一个问题的极小值，即，开始确定一个初始点$x_0,$然后基于前一步的结果确定下一步的解：$$x_{k+1} = x_{x} + \alpha_k d_k,$$其中$\alpha_k$叫做步长，一般通过精确或非精确的线搜索得到，$d_k$为搜索方向,$\alpha_k d_k$叫做位移。$d_k$和$\alpha_k$的不同确定方法，就产生了各种各样的迭代算法。在下文中我们约定$g_k = \nabla_{x_k}f,G_k = \nabla_{x_k}^2f.$

梯度下降法的思想很朴素，以负梯度方向作为搜索方向。假设$f(x)$在$x_k$一阶可微，我们可以得到 $$f(x_k + \alpha d) = f(x_k)+\alpha g_k^Td + o(\alpha),$$那么$$f(x_k + \alpha d) - f(x_k) = \alpha g_k^Td + o(\alpha).$$假设$|d|=1,\cos\theta = \frac{-g_kTd}{|g_k||d|} = \frac{-g_kTd}{|g|},$ 那么$g_kTd = -|g_k| \cos\theta,$ 当$\cos\theta=1,\theta=\frac{\pi}{2}$时，$g_kTd$取最小值，$f$在$x_k$下降的最快，此时$d=-g_k,$所以每一步$d$取负梯度方向，在当前的迭代点，目标函数是下降的最快的，所以梯度下降法也叫做最速下降法。

梯度下降法: