凸优化

  • convex

posted on 22 Feb 2019 under category 算法珠玑

凸优化问题

凸优化定义

同时满足下面两个限制条件的最优化问题成为凸优化问题：

  1. 对目标函数，我们限定是凸函数。
  2. 对优化变量的可行域（注意还要包括目标函数定义域的约束），我们限定是凸集。

这类问题有一个非常好的性质，那就是局部最优解一定是全局最优解。

凸集

凸集定义

对于$n$维空间中点的集合$C$，如果对集合中的任意两点$x$和$y$，以及实数$0\le\theta\le1$，都有：

$\theta x + (1-\theta) y \in C$

则称该集合为凸集。

凸集例子

下面是一些凸集的例子，对后面理解算法非常有帮助。

$n​$维实向量空间$R^n​$，如果$x, y \in R^n​$，则有：

$\theta x + (1-\theta) y \in R^n$

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

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

${x \in R^n: Ax=b}$

回忆一下线性代数，它就是非齐次线性方程组的解。

假设$x, y \in R^n$，并且：

$Ax=b, Ay=b$

对于任意$0\le \theta \le 1$，有：

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

这一结论的意义在于，如果一组约束是线形等式约束，则它确定的可行域是凸集。

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

${x \in R^n: Ax \le b}$

它就是线性不等式围成的区域。

对于任意的$x, y \in R^n​$，并且$AX \le b, AY \le b​$，如果$0 \le \theta \le 1​$，则有：

$A(\theta x + (1-\theta)y) = \theta Ax + (1-\theta)Ay \le \theta b + (1-\theta) b = b$

这一结论的意义在于，如果一组约束是线性不等式约束，则它的可行域是凸集。

在实际应用中，我们遇到的等式和不等式约束一般是线性的，因此非常幸运，它们定义的可行域是凸集。

一个重要的结论是：多个凸集的交集还是凸集。证明：https://zhuanlan.zhihu.com/p/37108430

这个结论的实际价值是如果每个等式或者不等式约束条件定义的集合都是凸集，那么这些条件联合起来定义的集合还是凸集，而我们遇到的优化问题中，可能有多个等式和不等式约束，只要每个约束条件定义的可行域是凸集，则同时满足这下约束条件的可行域还是凸集。

需要注意的是，凸集的并集不是凸集。

个人理解，这三个例子可以说明为什么线性规划的可行域是凸集。

凸函数

凸函数的定义：

$f(\theta x+(1-\theta)y)\le \theta f(x) + (1-\theta)f(y)$

a

注意图片中的函数如果倒过来就不是凸函数了，凸函数上每个点都比这个点的切线上的点大。

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

$f(y) \ge f(x) + \triangledown f(x)^T(y-x)$

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

对于一元函数，凸函数的判定则为其二阶导数大于等于0。如果去掉等号，则函数是严格凸的。

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

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

  1. 如果Hessian矩阵正定，函数在该点有极小值

  2. 如果Hessian矩阵负定，函数在该点有极大值

  3. 如果Hessian矩阵不定，则不是极值点（鞍点）

这可以看作是一元函数极值判别法对多元函数对推广，Hessian矩阵正定相当于二阶导数大于0，其他的依次类推。

对于$n$阶矩阵$A$，对于任意非0的$n$维向量$x$都有：

$x^TAx>0$

则称矩阵$A$为正定矩阵。

判定矩阵正定的常用方法有以下几种：

  1. 矩阵的特征值全大于0。

  2. 矩阵的所有顺序主子式都大于0。

  3. 矩阵合同于单位阵I。

如果满足：

$x^TAx \ge 0$

则称矩阵$A$为半正定矩阵。

如果满足：

$x^TAx < 0$

则称矩阵$A$为负定矩阵。

凸优化求解算法

对于凸优化问题，可以使用的求解算法很多，包括最常用的梯度下降法，牛顿法，拟牛顿法等，它们都能保证收敛到全局极小值点。

线性回归，将损失函数定义为误差平方和的均值，则损失函数是凸函数。可以用梯度下降法或者牛顿法求解。

线性回归+岭回归，也可以证明是凸函数。

支持向量机，它的不等式约束都是线性的，因此定义的可行域是凸集。另外可以证明目标函数是凸函数。因此是一个凸优化问题。

支持向量机，通过拉格朗日对偶，转换为对偶问题，加上核函数后的对偶问题，这里的等式约束和不等式约束都是线性的，因此可行域是凸集。根据核函数的性质，我们可以证明目标函数是凸函数。

Logistic回归，也是一个不带约束的优化问题，目标函数是凸函数（通过证明Hessian矩阵是半正定的证明）

softmax回归，是logistic回归对多分类问题的推广。是一个不带约束的优化问题，同样目标函数可以证明是凸函数。

神经网络，目标函数不是凸函数，因此有陷入局部极小值和鞍点的风险，这是之前长期被人诟病的。

参考资料：

  1. https://zhuanlan.zhihu.com/p/37108430