[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$取负梯度方向，在当前的迭代点，目标函数是下降的最快的，所以梯度下降法也叫做最速下降法。

梯度下降法
:

给定初始点$x_0$,误差$\epsilon$
若$| - g_k|<\epsilon$停止迭代，否则，令$d_k = - g_k$
$\alpha_k = \arg\min f(x_k + \alpha d_k)$
$x_{k+1} = x_k + \alpha_k d_k$

虽然梯度下降法每一步都选择下降最快的方向作为搜索方向，但它是一种贪婪算法，从全局来看收敛速度并不快，它是一阶收敛的。

牛顿法

牛顿法的基本思想是在当前迭代点二阶近似目标函数，即目标函数在迭代点二阶泰勒展开得到：
$$
\phi_k(d) = f(x_k+d) \approx f(x_k)+g_k^T d+\frac{1}{2}d^TG_kd
$$
求解
$$
\min_{d \in R^n} \phi_k(d)
$$
假设G正定，得到
$$
d = -G_k^{-1}g_k
$$
我们称$-G_k^{-1}g_k$为当前迭代点的牛顿方向，若$G_k$不可逆，$d$由$$G_kd =-g_k $$解出。我们便可得到牛顿法的迭代步骤：

牛顿法
:

给定初始点$x_0$,误差$\epsilon$
若$| - g_k|<\epsilon$停止迭代，否则，令$d_k = -G_k^{-1}g_k$
$x_{k+1} = x_k + d_k$

牛顿法有比梯度下降法更快的收敛速度，它是局部二阶收敛的，也就是说它的收敛性依赖于初始点的选取，而梯度下降法具有整体收敛性。虽然有更快的收敛速率，但正如我们上面所看到的，牛顿法每一步迭代都需要求解一次线性方程组，因此牛顿法的计算量是相当大的。为了发挥出牛顿法二阶收敛的特性，后来提出了一些修正的牛顿法，比如，阻尼牛顿法、Goldfeld修正法、Cholesky分解法等。

共轭梯度法

共轭梯度法是介于梯度下降法和牛顿法之间的一种方法，梯度下降法只使用了一阶导数信息，收敛速率较慢，牛顿法虽二阶收敛，但计算量大，共轭梯度法也只使用一阶导数信息，因此计算量小于牛顿法，同时它具有二次终止性。共轭梯度法最开始是应用在正定二次目标函数的优化中，它的基本思想是利用负梯度方向和已有的搜索方向产生新的搜索方向，迭代过程中产生的这一组搜索方向是两两共轭的。

共轭性： 设$G$是$n$阶对称正定矩阵，$d_1,d_2,\dots,d_m(m\leq n)$为一组非零向量，如果$$d_i^TGd_j = 0,i \neq j,$$则称$d_1,d_2,\dots,d_m$关于$G$是共轭的。

显然，若$d_1,d_2,\dots,d_m$关于$G$共轭，那么它们必是线性无关的。那么我们如何利用当前迭代点的梯度和上一搜索方向构造当前点的搜索方向呢？假设我们需要求解的是目标函数为
$$
f(x) = \frac{1}{2}x^TGx + b^Tx + c,
$$并且，下一搜索方向为
$$
d_{k+1} = -g_{k+1} + \beta d_{k},
$$

我们希望$d_{k+1}$与$d_k$关于G共轭，也就是$d_{k+1}^TGd_k = 0,$那么$$-g_{k+1}^TGd_k + \beta d_k^TGd_k = 0,$$得到$$\beta = \frac{g_{k+1}^TGd_k}{d_k^TGd_k}.$$
因此我们就得到了共轭梯度法的迭代步骤。
共轭梯度法
:

给定初始点$x_0$, 误差$\epsilon$, $d_0 = -g_0$
若$| - g_k|<\epsilon$停止迭代
$\beta_{k-1} = \frac{g_{k}^TGd_{k-1}}{d_{k-1}^TGd_{k-1}},d_k = -g_{k} + \beta_{k-1}d_{k-1}$
$\alpha_k = \arg\min f(x_k + \alpha d_k)$
$x_{k+1} = x_k + \alpha_k d_k$

定理：对正定二次目标函数，$d_0 = -g_0,$ $ \beta_k = \frac{g_{k+1}^TGd_k}{d_k^TGd_k}$, $d_{k+1} = -g_{k+1} + \beta_k d_{k},$ 并且采用精确线搜索得到的共轭梯度法，在$m(\leq n)$次迭代后可求得目标函数的极小点。

上面的推导是基于目标函数为正定二次函数的，对于一般的非二次目标函数，$\beta_k$ 的更新需要修改一下，比较常用的有，FR公式：$\beta_k = \frac{g_{k+1}^Tg_{k+1}}{g_k^Tg_k}$ 或 PRP公式：$\beta_k = -\frac{g_{k+1}^T(g_{k+1}-g_k)}{g_k^Tg_k}.$ 虽然对于二次目标函数共轭梯度法有二次终止性，但是对于一般的非二次目标函数就没有那么好的性质，而且实际应用中会采用重启动策略，即重新选择负梯度方向作为搜索方向。

拟牛顿法

拟牛顿法是求解无约束优化问题最有效的方法之一，著名的拟牛顿法有DFP算法和BFGS算法。拟牛顿法的基本思想是模拟牛顿方向的生成途径，它利用两个迭代点的位移和梯度差来构造与二阶导数矩阵相似的正定矩阵。拟牛顿法的计算量要少于牛顿法，而且在一定条件下是超线性收敛的。

考虑$f$在$x_{k+1}$点的二阶泰勒展开：
$$
f(x) \approx f(x_{k+1}) + g_{k+1}^T(x-x_{k+1})+\frac{1}{2}(x-x_{x+1})^TG_{k+1}(x-x_{x+1}),
$$
对上式两边同时求导得到：
$$
g(x) = g_{k+1} + G_{k+1}(x-x_{x+1}),
$$
令$x=x_k$得
$$
G_{k+1}^{-1}y_k \approx s_k,
$$
其中$y_k = g_{k+1}-g_k$为梯度差，$s_k = x_{k+1}-x_k$为位移。显然，上式还是和牛顿法的迭代步骤一样，回想一下，牛顿法的计算代价主要花费在了二阶导数的计算和求解一个线性方程组上面，那么我们能否避开这两个缺点，同时还保留牛顿法超线性收敛的优点？所以拟牛顿法的基本出发点为用$H_{k+1}$近似$G_{k+1}^{-1},$同时满足
$$
H_{k+1}y_k \approx s_k,
$$
这个方程也叫做拟牛顿方程或拟牛顿条件。

关于构造满足拟牛顿条件的$H_{k+1},$有两个比较重要的算法。

DFP算法

DFP(Davidon, Fletcher, Powell)算法的校正公式为
$$
H_{k+1} = H_k - \frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k} + \frac{s_ks_k^T}{s_k^Ty_k}.
$$

定理： DFP在求解二次正定目标函数时,如果初始矩阵$H_0$是正定的，那么它产生的搜索方向为共轭方向，并且具有二次终止性。

BFGS算法

BFGS(Broyden, Fletcher, Goldfard, Shanno)算法的校正公式为
$$
H_{k+1} = H_k - \frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k} + \frac{s_ks_k^T}{s_k^Ty_k} + v_kv_k^T.
$$
其中$v_k = (y_k^TH_ky_k)^{\frac{1}{2}}\left(\frac{s_k}{s_k^Ty_k} - \frac{H_ky_k}{y_k^TH_ky_k} \right).$

References

[1] 袁亚湘院士，非线性优化计算方法
[2] 倪勤，最优化方法与程序设计