凸优化--主要算法

本文对凸优化问题的解法进行简单的归纳整理，仅供引入，对于详细的使用与证明请自行查阅资料。

下降方法

无约束优化问题

\[ \min f(x) \]

其中 $f: \mathbb{R}^n → \mathbb{R}$ 是二次可微凸函数(这意味着 domf 是开集)。我们假定

该问题存在唯一的最优点，用 \[p^*\] 表示最优值 \[\inf_x f(x) = f(x^*)\]
目标函数在 $S$ 上是强凸的，存在 $m>0$ 使得 $\nabla ^2 f(x) > mI$ 对任意的 $x\in S$ 都成立。

无约束问题中我们讨论下降方法。方法需要一个适当的初始点 $x^{(0)}$ 必须属于 $f $，并且下水平集是闭集。

算法产生一个优化点列 $x^{(k)},k = 1,...$, 其中

\[ x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)} \]

且当 $x^{(k)}$ 不是最优点时，$t^{(k)} >0$。其中， $\Delta x\in \mathbb{R}^n$ 称为步径或搜索方向，$t^{(k)} \ge0$称为步长。对于下降方法，我们需要满足 $x^{(k)}$ 不是最优点时 $f(x^{(k+1)})<f(x^{(k)})$, 因此，搜索方向必须满足$\nabla f(x^{(k)})^T\Delta x^{(k)}<0$ , 即它与负梯度方向夹角必须是锐角，称这样的方向为下降方向。

对于步长考虑两种方法：

精确直线搜索： \[t = \arg\min_{s\ge0} f(x+s\Delta x)\], 即对得到的方向找到下降最大的步长

回溯直线搜索 ：给定下降方向与参数 $\alpha,\beta, 0<\alpha < 0.5, 0<\beta<1$。$t := 1$。当 $f(x+\Delta x)>f(x) + \alpha t\nabla f(x)^T\Delta x$ 时，令 $t:=\beta x$。回溯直线搜索并不需要得到一个精确的步长，只是希望得到一个步长使函数指有一定的减小，即 $f(x+\Delta x)\le f(x) + \alpha t\nabla f(x)^T\Delta x$，落在下图的虚线之间 (图源：《凸优化》，Stephen Boyd等著，王书宁等译)

接下来我们介绍几个下降方法

梯度下降方法

用负梯度作搜索方向，即令$\Delta x = -\nabla f(x)$，是一种自然的选择。相应的方法被称为梯度下降方法。

最速下降方法

规范化的最速下降方向：令 $\vert\vert \cdot \vert\vert$ 为 $\mathbb{R}^n$ 上的任意范数。定义一个规范化的最速下降方向 (相对于范数) 为

\[ \Delta x_{\mathrm{nsd}} = \arg\min\{\nabla f(x)^Tv\quad\vert \quad\vert\vert v\vert\vert = 1\} \]

非规范化的最速下降方向 ：\[\vert\vert\cdot\vert\vert_* \] 表示对偶范数

\[ \Delta x_{\mathrm{sd}} = \vert\vert\nabla f(x)\vert\vert_*\Delta x_{\mathrm{nsd}}, \]

当范数为 Euclid 范数时，最速下降方向就是负梯度方向。采用 Euclid 范数的最速下降方法就是梯度下降方法。

Newton 方法

对于 $x\in\mathbf{dom}f$，称向量

\[ \Delta x_{\mathrm{nt}} = -\nabla^2f(x)^{-1}\nabla f(x) \]

为 ( $f$ 在 $x$ 处的) Newton 步径。由 $\nabla ^2f(x)$ 的正定性可知，当 $\nabla f(x) \neq 0$，有

\[ \nabla f(x)^T\Delta x_{\mathrm{nt}} = -\nabla f(x)^T\nabla^2f(x)^{-1}\nabla f(x) < 0 \]

因此 Newton 步径是下降方向(除非 $x$ 是最优点)。

Newton 步径是 $x$ 处采用 Hessian 矩阵定义的二次范数 $\vert\vert u\vert\vert_{\nabla^2f(x)} = (y^t\nabla^2f(x)u)^{1/2}$ 导出的最速下降方法。函数 $f$ 在 $x$ 处的二阶 Taylor 近似是关于 $v$ 的二阶凸函数，且在 $v = \Delta x_{\mathrm{nt}}$ 时达到最小值。因此Newton 方法在 $x^*$ 附近二阶近似的方法。