凸优化

梯度下降法和牛顿法等基于导数作为判据的优化算法，找到的都导数/梯度为 0 的点，而梯度等于 0 只是取得极值的必要条件而不是充分条件。即局部最优解不一定是全局最优解。

凸优化问题——满足下面两个限制条件的最优化问题。

• 目标函数是凸函数；

• 优化变量的可行域是凸集；

凸优化问题——局部最优解一定是全局最优解。

凸集

对于 n 维空间中点的集合 C，如果对集合中的任意两点 x 和 y，以及实数 0 ≤ θ ≤ 1，都有：

\[\theta x + ( 1 - \theta ) y \in C\]

则称该集合称为凸集。

n 维实向量空间 $R^n$

显然如果 $x , y \in R ^ { n }$，则有：

\[\theta x + ( 1 - \theta ) y \in \mathrm { R } ^ { n }\]

结论：如果一个优化问题是不带约束的优化，则其优化变量的可行域是一个凸集。

仿射子空间

给定 m 行 n 列的矩阵 A 和 m 维向量 b，仿射子空间定义为如下向量的集合：

\[\left\{ x \in \mathrm { R } ^ { n } : Ax = b \right\}\]

实际上，它就是非齐次线性方程组的解。

证明：仿射子空间是凸集

假设 $x , y \in R ^ { n }$ 并且 $A x = b , A y = b$，对于任意 $0 \leq \theta \leq 1$，有：

\[A ( \theta x + ( 1 - \theta ) y ) = \theta Ax + ( 1 - \theta ) Ay = \theta b + ( 1 - \theta ) b = b\]

结论：如果一组约束是线性等式约束，则它确定的可行域是一个凸集。

多面体

多面体定义为如下向量的集合：

\[\left\{ x \in \mathrm { R } ^ { n } : Ax \leq b \right\}\]

实际上，它就是线性不等式围成的区域。

证明：多面体是凸集

\[\forall \quad x , y \in R ^ { n } \Rightarrow A x \leq b , A y \leq b\] \[if \quad 0 \leq \theta \leq 1\] \[则 \quad A ( \theta x + ( 1 - \theta ) y ) = \theta Ax + ( 1 - \theta ) Ay \leq \theta b + ( 1 - \theta ) b = b\]

结论：如果一组约束是线性不等式约束，则它定义的可行域是凸集

证明：多个凸集的交集还是凸集

假设 $C _ { 1 } , \ldots , C _ { k }$ 为凸集，它们的交集为 $\bigcap _ { i = 1 } ^ { k } C i$。对于任意点 $X , Y \in \bigcap _ { i = 1 } ^ { k } C i$，并且 $0 \leq \theta \leq 1$，由于 $C _ { 1 } , \ldots , C _ { k }$ 为凸集，所以有：

\[\theta x + ( 1 - \theta ) y \in C _ { i } , \forall i = 1 , \ldots , k\]

由此：

\[\theta x + ( 1 - \theta ) y \in \bigcap _ { i = 1 } ^ { k } C _ { i }\]

结论：如果每个等式或者不等式约束条件定义的集合都是凸集，那么这些条件联合起来定义的集合还是凸集。

注意：凸集的并集并不是凸集。

下水平集

给定一个凸函数以及一个实数 $\alpha$，函数的 $\alpha$ 下水平集（sub-level set）定义为函数值小于等于 $\alpha$ 的点构成的集合：

\[\{ x \in D ( f ) : f ( x ) \leq \alpha \}\]

该集合是一个凸集。用于确保优化问题中一些不等式约束条件定义的可行域是凸集，如果是凸函数构成的不等式，则是凸集。

凸函数

在函数的定义域内，如果对于任意的 x、y，以及实数 $0 \leq \theta \leq 1$，都满足如下条件：

\[f ( \theta x + ( 1 - \theta ) y ) \leq \theta f ( x ) + ( 1 - \theta ) f ( y )\]

则函数为凸函数。如果把上面不等式中的等号去掉，则称函数是严格凸函数。

凸函数的一阶判定规则为：

\[f ( y ) \geq f ( x ) + \nabla f ( x ) ^ { T } ( y - x )\]

其几何解释为函数在任何点处的切线都位于函数的下方。

对于一元函数，凸函数的判定规则为其二阶导数大于等于 0，即：$f ^ { \prime \prime } ( x ) \geq 0$。如果去掉上面的等号，则函数是严格凸的。

对于多元函数，如果它是凸函数，则其 Hessian 矩阵为半正定矩阵。如果Hessian矩阵是正定的，则函数是严格凸函数。

Hessian矩阵是由多元函数的二阶偏导数组成的矩阵。如果函数二阶可导，Hessian 矩阵定义为：

$$ \left[ \begin{array} { c c c c } { \frac { \partial ^ { 2 } f } { \partial x _ { 1 } ^ { 2 } } } & { \frac { \partial ^ { 2 } f } { \partial x _ { 1 } \partial x _ { 2 } } } & { \dots } & { \frac { \partial ^ { 2 } f } { \partial x _ { 1 } \partial x _ { n } } } \\ { \frac { \partial ^ { 2 } f } { \partial x _ { 2 } \partial x _ { 1 } } } & { \frac { \partial ^ { 2 } f } { \partial x _ { 2 } ^ { 2 } } } & { \dots } & { \frac { \partial ^ { 2 } f } { \partial x _ { 1 } \partial x _ { n } } } \\ { \ldots } & { \ldots } & { \dots } & { \ldots } \\ { \frac { \partial ^ { 2 } f } { \partial x _ { n } \partial x _ { 1 } } } & { \frac { \partial ^ { 2 } f } { \partial x _ { n } \partial x _ { 2 } } } & { \dots } & { \frac { \partial ^ { 2 } f } { \partial x _ { n } ^ { 2 } } } \end{array} \right] $$

Hessian 矩阵是一个 n 阶对称矩阵。简写为 $\nabla ^ { 2 } f ( x )$。

根据多元函数极值判别法，假设多元函数在点 M 的梯度为 0，即 M 是函数的驻点，则有：

• Hessian 矩阵正定，函数在该点有极小值；
• Hessian 矩阵负定，函数在该点有极大值；
• Hessian 矩阵不定，还需要看更高阶的导数；

对于 n 阶矩阵 A，对于任意非 0 的 n 维向量 x 都有：$x ^ { T } Ax > 0$，则称矩阵 A 为正定矩阵。类似的，$x ^ { T } Ax \leq 0$，矩阵 A 为半正定矩阵。$x ^ { T } Ax < 0$，矩阵 A 为负定矩阵。

矩阵正定的判定方法：

• 矩阵的特征值全大于 0；
• 矩阵的所有顺序主子式都大于 0；
• 矩阵合同于单位阵 I；

凸函数的非负线性组合是凸函数。假设 $f _ { j }$ 是凸函数，并且 $w _ { i } \geq 0$，则：$f ( x ) = \sum _ { i = 1 } ^ { k } w _ { i } f _ { i } ( x )$ 是凸函数。

凸优化

如果一个最优化问题的可行域是凸集，并且目标函数是凸函数，则该问题为凸优化问题。

$$ \begin{align*} { \min _ { x \in C }} \quad & {f ( x ) } \\ \text{s.t.} \quad & { g _ { i } ( x ) \leq 0 , i = 1 , \ldots , m } \\ \quad & { h _ { i } ( x ) = 0 , i = 1 , \ldots , p } \end{align*} $$

$g _ { i } ( x )$ 是不等式约束函数，为凸函数。一个凸函数的 0-下水平集是凸集。

$h _ { i } ( x )$ 是等式约束函数，为仿射函数。仿射空间是凸集。

多个凸集的交集还是凸集，因此加上这些约束后可行域还是凸集。

局部最优解

对于一个可行点，如果存在一个大于 0 的实数 $\delta$，对于所有满足：$| x - z | _ { 2 } \leq \delta$ 即 x 的 $\delta$ 邻域内的点 z，都有：$f ( x ) \leq f ( z )$ 则称x为局部最优点。

全局最优解

对于一个可行点x，如果可行域内所有点z处的函数值都比在这点处大，即：$f ( x ) \leq f ( z )$ 则称x为全局最优点，全局最优解可能不止一个。

证明：凸优化问题的局部最优解就是全局最优解

反证法：

假设 x 是一个局部最优解但不是全局最优解，即存在一个可行解 y，有 $f ( x ) > f ( y )$。根据局部最优解的定义，不存在满足：$| x - z | _ { 2 } \leq \delta$ 并且 $f ( z ) < f ( x )$ 的点。

选择一个点：$z = \theta y + ( 1 - \theta ) x$，其中：$\theta = \frac { \delta } { 2 | x - y | _ { 2 } }$，则有：

$$ \begin{aligned} \| x - z \| _ { 2 } & = \left\| x - \left( \frac { \delta } { 2 \| x - y \| _ { 2 } } y + \left( 1 - \frac { \delta } { 2 \| x - y \| _ { 2 } } \right) x \right) \right \| _ { 2 } \\ & = \left\| \frac { \delta } { 2 \| x - y \| _ { 2 } } ( x - y ) \right\| _ { 2 } \\ & = \frac { \delta } { 2 } \leq \delta \end{aligned} $$

即该点在 x 的 $\delta$ 邻域内。另外：

$$ f ( z ) = f ( \theta y + ( 1 - \theta ) x ) \leq \theta f ( y ) + ( 1 - \theta ) f ( x ) < f ( x ) $$

这与 x 是局部最优解矛盾。如果一个局部最优解不是全局最优解，在它的任何邻域内还可以找到函数值比该点更小的点，这与该点是局部最优解矛盾。

求解算法

梯度下降法，牛顿法，拟牛顿法等，都能保证收敛到全局极小值点。

机器学习中的凸优化问题

线性回归

$$ \begin{align*} \text{预测函数：} & f ( x ) = w ^ { T } x \\ \text{目标函数：} & L = \frac { 1 } { 2 l } \sum _ { i = 1 } ^ { l } \left( f \left( x _ { i } \right) - y _ { i } \right) ^ { 2 } = \frac { 1 } { 2 l } \sum _ { i = 1 } ^ { l } \left( w ^ { T } x _ { i } - y _ { i } \right) ^ { 2 } \end{align*} $$

证明：这个目标函数是凸函数

$$ \begin{align*} \text{目标函数：} & L = \frac { 1 } { 2 l } \sum _ { i = 1 } ^ { l } \left( w ^ { T } x _ { i } - y _ { i } \right) ^ { 2 } = \frac { 1 } { 2 l } \sum _ { i = 1 } ^ { l } \left( \left( w ^ { T } x _ { i } \right) ^ { 2 } + y _ { i } ^ { 2 } - 2 y _ { i } w ^ { T } x _ { i } \right)\\ \text{二阶偏导数：} & \frac { \partial ^ { 2 } L } { \partial w _ { i } \partial w _ { j } } = \frac { 1 } { l } \sum _ { k = 1 } ^ { l } x _ { k , i } x _ { k , j } \end{align*} $$

Hessian 矩阵

$$ \frac { 1 } { l } \sum _ { k = 1 } ^ { l } \left[ \begin{array} { c c c } { x _ { k , 1 } x _ { k , 1 } } & { \dots } & { x _ { k , 1 } x _ { k , n } } \\ { \ldots } & { \dots } & { \dots } \\ { x _ { k , n } x _ { k , 1 } } & { \dots } & { x _ { k , n } x _ { k , n } } \end{array} \right] = \frac { 1 } { l } \left[ \begin{array} { c c c } { \sum _ { k = 1 } ^ { l } x _ { k , 1 } x _ { k , 1 } } & { \dots } & { \sum _ { k = 1 } ^ { l } x _ { k , 1 } x _ { k , n } } \\ { \cdots } & { \cdots } & { \cdots } \\ { \sum _ { k = 1 } ^ { l } x _ { k , n } x _ { k , 1 } } & { \dots } & { \sum _ { k = 1 } ^ { l } x _ { k , n } x _ { k , n } } \end{array} \right] $$

矩阵形式

$$ \frac { 1 } { l } \left[ \begin{array} { c } { x _ { 1 } ^ { T } } \\ { \dots } \\ { x _ { l } ^ { T } } \end{array} \right] \left[ \begin{array} { l l l } { x _ { 1 } } & { \dots } & { x _ { l } } \end{array} \right] = \frac { 1 } { l } x ^ { T } x $$

其中 X 是所有样本的特征向量按照列构成的矩阵。对于任意不为 0 的向量 x，有：

\[x ^ { T } x ^ { T } Xx = ( Xx ) ^ { T } ( Xx ) \geq 0\]

因此 Hessian 矩阵是半正定矩阵，上面的优化问题是一个不带约束条件的凸优化问题。可以用梯度下降法或牛顿法求解。

岭回归

岭回归是加上正则化项之后的线性回归。加上L2正则化之后，训练时优化的问题变为：

\[\min _ { w } \sum _ { i = 1 } ^ { l } \left( w ^ { T } x _ { i } - y _ { i } \right) ^ { 2 } + \lambda w ^ { T } w\]

同样的，我们可以证明这个函数的 Hessian 矩阵半正定，事实上，如果正则化项的系数大于 0，它是严格正定的。

支持向量机

支持向量机训练时求解的原问题为：

$$ \begin{align*} { \min } \quad & { \frac { 1 } { 2 } w ^ { T } w + C \sum _ { i = 1 } ^ { l } \xi _ { i } } \\ {s.t.} \quad & { y _ { i } \left( w ^ { T } x _ { i } + b \right) \geq 1 - \xi _ { i } }\\ & { \xi _ { i } \geq 0 , i = 1 , \ldots , l } \end{align*} $$

显然，这些不等式约束都是线性的，因此定义的可行域是凸集，另外我们可以证明目标函数是凸函数，因此这是一个凸优化问题。

通过拉格朗日对偶，我们转换为对偶问题，加上核函数后的对偶问题为：

$$ \begin{align*} { \min _ { \alpha } } \quad & {\frac { 1 } { 2 } \sum _ { i = 1 } ^ { l } \sum _ { j = 1 } ^ { l } \alpha _ { i } \alpha _ { j } y _ { i } y _ { j } K \left( x _ { i } ^ { T } x _ { j } \right) - \sum _ { k = 1 } ^ { l } \alpha _ { k } } \\ {s.t.} \quad & { 0 \leq \alpha _ { i } \leq C } \\ & { \sum _ { i = 1 } ^ { l } \alpha _ { j } y _ { j } = 0 } \end{align*} $$

这里的等式约束和不等式约束都是线性的，因此可行域是凸集。根据核函数的性质，我们可以证明目标函数是凸函数。

logistic回归

logistic回归也是一种常用的有监督学习算法。加上L2正则化项之后，训练时求解的问题为：

\[\min _ { w } f ( w ) = \frac { 1 } { 2 } w ^ { T } w + C \sum _ { i = 1 } ^ { l } \log \left( 1 + e ^ { - y _ { i } w ^ { T } x _ { i } } \right)\]

这是一个不带约束的优化问题，我们可以证明这个函数的 Hessian 矩阵半正定。

softamx回归

softamx 回归是 logistic 回归对多分类问题的推广。它在训练时求解的问题为：

\[L ( \theta ) = - \sum _ { i = 1 } ^ { l } \sum _ { j = 1 } ^ { k } \left( 1 _ { y _ { i } = j } \log \frac { \exp \left( \theta _ { j } ^ { T } x _ { i } \right) } { \sum _ { t = 1 } ^ { k } \exp \left( \theta _ { t } ^ { T } x _ { i } \right) } \right)\]

这是一个不带约束的优化问题，同样的可以证明这个目标函数是凸函数。