凸优化

Convex Optimization Overview[1]

机器学习 数学基础

---

---

1 前言

在机器学习中，我们会经常优化函数的值，给定函数$f:\mathbb{R}^n\rightarrow\mathbb{R}$，我们要寻找该函数的最小值。最小二乘法(least-squares)、逻辑斯蒂回归(logistic regression)和支持向量机(support vector machines)等模型优化都可以看做一个优化问题。
一般来说，寻找函数的全局最优比较困难，但是有一种优化问题叫凸优化(optimazation problems)，我们可以在合理的时间内找到全局最优的结果。
以下是一个凸优化的简单介绍，如果有兴趣深入了解可以阅读书籍《Convex Optimization》[2]

2 凸集(Convex Sets)

凸优化中，凸集的定义如下：
定义2.1:集合C是凸的，如果对于所有的$x,y\in C$和$\theta\in\mathbb{R},0\leq\theta\leq 1$有

$$\theta x+(1-\theta)y\in C$$
直观上可以这样理解，在集合$C$中任选两点，在这两点的连线上的所有点都属于集合$C$。所以我们称点$\theta x+(1-\theta)y$为点$x$和$y$的凸组合。Figure 1展示了凸集和非凸集。

2.1 例子

• 所有的实数集空间$\mathbb{R}^n$：
  证明：当${\bf x},{\bf y}\in\mathbb{R}^n,0\leq\theta\leq 1$时，很明显，

  $$\theta {\bf x}+(1-\theta){\bf y}\in\mathbb{R}^n$$

• 非负象限$\mathbb{R}^n_+$：
  证明：当${\bf x},{\bf y}\in\mathbb{R}^n_+,0\leq\theta\leq 1$时，

  $$\theta {\bf x}+(1-\theta){\bf y}\geq0$$

• 标准化的球(Norm balls)：标准球面定义为$\{{\bf x}:||{\bf x}||=\sqrt{\sum_{i=1}^n x_i^2}\leq 1\}$。
  证明：当$||{\bf x}||,||{\bf y}||\leq 1,0\leq\theta\leq 1$时，
  

  $$||\theta{\bf x}+(1-\theta){\bf y}||\leq||\theta{\bf x}||+||(1-\theta){\bf y}||=\theta||{\bf x}||+(1-\theta)||{\bf y}||\leq 1$$

• 仿射面(Affine subspaces)：给定一个矩阵$A\in \mathbb{R}^{m\times n}$和向量$b\in\mathbb{R}^m$，仿射面定义为$\{x\in\mathbb{R}^n:Ax=b\}$，
  证明：当${\bf x},{\bf y}\in\mathbb{R}^n,A{\bf x}=b,A{\bf y}=b$时，有

  $$A(\theta{\bf x}+(1-\theta){\bf y})=\theta A{\bf x}+(1-\theta){\bf y}=\theta b+(1-\theta)b=b$$

• 多面体(polyhedra)：给定一个矩阵$A\in \mathbb{R}^{m\times n}$和向量$b\in\mathbb{R}^m$，多面体定义为$\{x\in\mathbb{R}^n:Ax\leq b\}$。
  证明：当${\bf x},{\bf y}\in\mathbb{R}^n,A{\bf x}\leq b,A{\bf y}\leq b$时，有

  $$A(\theta{\bf x}+(1-\theta){\bf y})=\theta A{\bf x}+(1-\theta){\bf y}\leq\theta b+(1-\theta)b=b$$

• 凸集的交集：当$C_i$是凸集时，$\bigcap\limits^k_{i=1}C_i=\{x:x\in C_i\ \forall i=1,\dots k\}$是一个凸集。但是要记住凸集的并集通常不是一个凸集。

• 半正定矩阵：半正定矩阵的定义是$A=A^T,当x\in\mathbb{R}^n$时，$x^TAx\geq0$。正定矩阵用符号$\mathbb{S}^n_+$表示，是一个凸集。
  证明：当$A,B\in\mathbb{S}^n_+,0\leq\theta\leq1,x\in\mathbb{R}^n$时，有

  $$x^T(\theta A +(1-\theta)B)x=\theta x^TAx+(1-\theta)x^TBx\geq0$$ 同样道理，正定矩阵、半负定矩阵、负定矩阵也是凸集。

3 凸函数(Convex Fuctions)

凸函数，是凸优化中一个重要的概念。
定义3.1:函数$f:\mathbb{R}^n\rightarrow\mathbb{R}$是凸函数，如果函数的定义域${\cal D}(f)$是一个凸集，并且对于所有的$x,y\in {\cal D}(f)$和$\theta\in\mathbb{R},0\leq\theta\leq1$，都有：

$$f(\theta x+(1-\theta)y)\leq\theta f(x)+(1-\theta)f(y)$$ 直观上可以这样理解，在函数上任意挑两点，两点的连线必然在两点间的函数值之上，如Figure 2所示：

3.1 凸性质的一阶条件

假设函数$f:\mathbb{R}^n\rightarrow\mathbb{R}$是处处可导的。$f$是凸的，当且仅当${\cal D}(f)$是凸集，并且对于所有$x,y\in{\cal D}(f)$都有：

$$f(y)\geq f(x)+\nabla_xf(x)^T(y-x)$$ 直观上可以这样理解，在函数上随便挑一个点，该点的切线必然在函数的下方，如Figure 3所示：

3.2 凸性质的二阶条件

假设函数$f:\mathbb{R}^n\rightarrow\mathbb{R}$处处二阶可导。$f$是凸的，当且仅当${\cal D}(f)$是凸集，并且其海塞矩阵(Hessian)是半正定的（即，对所有$x,y\in{\cal D}(f)$都有：

$$\nabla_x^2f(x)\succeq0$$
这里的符号$\succeq$表示矩阵半正定（positive semidefiniteness），而不是指矩阵中每个元素$X_{ij}\geq0$。但是如果再一维的情况下，这就代表二次导数$f^{''}(x)\geq0$。假如海塞矩阵是正定矩阵，那么$f$就是严格凸(strictly convex)的。

3.3 琴生不等式(Jensen's Inequality)

假设凸函数$f$的基本定义为:

$$f(\theta x+(1-\theta)y)\leq\theta f(x)+(1-\theta)f(y)\ \ \ \text{for} \ \ \ 0\leq\theta\leq1$$
上述等式可以扩展到多个点:
$$f\left(\sum_{i=1}^k\theta_ix_i\right)\leq\sum_{i=1}^k\theta_if(x_i)\ \ \ \text{for}\ \ \ \sum_{i=1}^k\theta_i=1,\theta_i\geq0 \ \ \forall i$$
再将上述等式扩展到积分形式:
$$f\left(\int p(x)xdx\right)\leq\int p(x)f(x)dx\ \ \ \text{for}\ \ \ \int p(x)dx=1,p(x)\leq0\ \ \forall x$$
由于$p(x)$积分为1，我们可以把$p(x)$看作是一个概率密度函数，所以尚属等式可以用以下形式表达：
$$f(\mathbb{E}[x])\leq\mathbb{E}[f(x)]$$
最后一条等式就是著名的琴生不等式。

3.4 水平子集(Sublevel Sets)

$\alpha$-sublevel set是比较重要的一种凸函数。给定一个凸函数$f:\mathbb{R}^n\rightarrow\mathbb{R}$，和一个实数$\alpha\in R$，$\alpha$-sublevel set定义如下：

$$\{x\in {\cal D}(f):f(x)\leq\alpha\}$$
换而言之，$\alpha$-sublevel set就是所有的点$x$都符合$f(x)\leq\alpha$的凸函数。

3.5 例子[TODO]

这里举一些凸函数的例子，先从单变量开始，然后推广到多变量。

• 指数函数(Exponential)： $$f:\mathbb{R}\rightarrow\mathbb{R},f(x)=e^{ax}\ \ \ for\ \ \ \forall a\in \mathbb{R}$$
• 负对数(Negative logarithm)： $$f:\mathbb{R}\rightarrow\mathbb{R},f(x)=-\log x\ \ \ for\ \ \ \mathcal{D}(f)=\{x:x>0\}$$
• 仿射函数(Affine fuctions)： $$f:\mathbb{R}^n\rightarrow\mathbb{R},f(x)=b^Tx+c\ \ \ for\ \ \ b\in\mathbb{R}^n,c\in\mathbb{R}$$
• 二次型函数(Quadratic fuctions)： $$f:\mathbb{R}^n\rightarrow\mathbb{R},f(x)=\frac{1}{2}x^TAx+b^Tx+c\ \ \ for\ \ \ A\in \mathbb{S}^n,b\in\mathbb{R}^n,c\in\mathbb{R}$$

4 凸优化问题(Convex Optimization Problems)

凸优化问题可以看做是以下形式：

$$\begin{align*} \text{minimize}\ &f(x)\\ \text{subject to}\ &x\in C \end{align*}$$
其中$f$是凸函数，$C$是凸集，$x$是优化变量。为了更加具体，我们可以改为以下形式：
$$\begin{align*} \text{minimize}\ &f(x)\\ \text{subject to}\ &g_i(x)\leq0,\ \ \ i=1,\dots,m\\ &h_i(x)=0,\ \ \ i=1,\dots,p \end{align*}$$
其中$f$是凸函数，$g_i$是凸函数，$h_i$是仿射函数,$x$是优化变量。

值得注意的是，凸函数$g_i$一定小于等于0。因为$g_i\leq0$是0-sublevel set，可行域是多个凸集的交点，所以可行域也是凸的。如果我们限制某些凸函数$g_i\geq0$，这样可行域将不会是凸集，这样我们就不能保证能找到全局最优解。同时，我们要注意，只有仿射函数才可以是等式约束。我们可以把等式约束看做是两个不等式约束，$h_i\leq0,h_i\geq0$，所以只有当$h_i$即是凸集又是凹集的时候才是一个有效的约束。

将优化问题的最优值表示为$p^*$或者是$f^*$ ,它等于目标方程再可行域中的最小值：

$$p^*=\min\{f(x):g_i(x)\leq0,i=1,\dots,m,h_i(x)=0,i=1,\dots,p\}$$
当优化问题无解时，$p^*$取值为$+\infty$，当优化问题存在解使得$f(x)$无下界时，$p^*$取值为$-\infty$。当$f(x^*)=p^*$时，$x^*$称为最优解，当$p^*$有界时，有可能有多个最优解。

4.1 凸优化问题的全局最优(Global Optimality)

首先，我们要定义两个概念，局部最优(locally optimal)和全局最优(globally optimal)。局部最优可以认为是一个可行解附近没有比自己有更低的目标值的解。而全局最优是所有可行解中目标值最低的解。具体我们可以定义为：

定义4.1 当$x$是可行解，并且存在$R>0$使得所有的可行解$z\in\{||x-z||_2\leq R\}$满足$f(x)\leq f(z)$时，$x$是局部最优解

定义4.2 当$x$是可行解，并且对于所有$z$都满足足$f(x)\leq f(z)$时，$x$是全局最优解。

在凸优化问题中，一个最关键的点就是对于一个凸优化问题，所有的局部最优解都是全局最优解。直观上凸优化确实就是这么一回事，但我们可以证明：
假设$x$是局部最优解，而不是全局最优解，所以存在一个可行解使得$f(x)>f(y)$。在局部最优解的定义中，不存在一个可行解$z\in\{||x-z||_2\leq R\}$并且$f(z)\leq f(x)$，但是我们可以选出一个点：

$$z=\theta y+(1-\theta)x\ \ \ 且\ \ \ \theta=\dfrac{R}{2||x-y||_2}$$
然后
$$\begin{align*} ||x-z||_2 &= \left|\left| x-\left(\dfrac{R}{2||x-y||_2}y+\left(1-\dfrac{R}{2||x-y||_2}x\right)\right)\right|\right|_2\\ &=\left|\left|\dfrac{R}{2||x-y||_2}(x-7)\right|\right|_2\\ &=R/2\leq R \end{align*}$$
然后，通过凸函数性质，得到：
$$f(x)=f(\theta y+(1-\theta)x)\leq\theta f(y)+(1-\theta)f(x)<f(x)$$
并且当可行域是个凸集，$x,y,z=\theta y+(1-\theta)x$都是可行解。所以$z$是可行解并且$||x-z||_2\leq R$，时$f(z)<f(x)$，这与局部最优解的定义相违背，因此$x$不可能是局部最优解。

4.2 凸优化问题的某些特定问题

因为各种原因，考虑一般凸规划问题的特定问题会更方便。对于这些特定问题，我们经常会设计一些可以解决大型问题并且十分高效的算法，因此你会看到这些特殊例子就是人们经常使用的凸优化技术。

• 线性规划(Linear Programming) 当目标方程$f$和不等式约束$g_i$是仿射函数时，我们说这是一个LP，线性规划问题。其形式如下：
  

  $$\begin{align*} \text{minimize}\ &c^T+d\\ \text{subject to}\ &Gx\leq h\\ &Ax=b \end{align*}$$
  其中$x\in \mathbb{R}^n$是优化变量，$c\in\mathbb{R}^n,G\in\mathbb{R}^{m\times n},h\in\mathbb{R}^m,A\in\mathbb{R}^p$。

• 二次规划(Quadratic Programming)
  当不等式约束$g_i$是仿射函数，但目标方程是凸的二次函数食，我们说这是一个二次规划问题。其形式如下：
  

  $$\begin{align*} \text{minimize}\ &\frac{1}{2}x^TPx+c^T+d\\ \text{subject to}\ &Gx\leq h\\ &Ax=b \end{align*}$$
  这里增加了$P\in\mathbb{S}^n_+$，是一个对称半正定矩阵。

• 平方约束的二次规划(Quadratically Constrained Quadratic Programming)
  当目标方程$f$和不等式约束$g_i$都是凸的二次函数时，我们说这是一个平方约束的二次规划问题。其形式如下：
  

  $$\begin{align*} \text{minimize}\ &\frac{1}{2}x^TPx+c^T+d\\ \text{subject to}\ &\frac{1}{2}x^TQ_ix+r_i^Tx+s_i\leq 0,\ \ i=1,\dots,m\\ &Ax=b \end{align*}$$
  这里增加了$Q_i\in\mathbb{S}^n_+,r_i\in\mathbb{R}^n,s_i\in\mathbb{R},\text{for}\ i=1,\dots,m$。

• 半定规划(Semidefinite Programming)
  半定规划在机器学习中越来越常用，所以我们最好要弄懂它。半定规划有以下形式：
  

  $$\begin{align*} \text{minimize}\ &tr(CX)\\ \text{subject to}\ &tr(A_iX)=b_i,\ \ \ i=1,\dots,p\\ &X\succeq0 \end{align*}$$
  其中对称矩阵$X\in\mathbb{S}^n$是优化变量，对称矩阵$C,A_1,\dots,A_p\in\mathbb{S}^n$是由问题决定的，约束$X\succeq0$意味着我们要约束$X$是半正定矩阵。与前面的优化问题不一样的是，优化变量现在是一个矩阵，而不再是一个向量。

其实，二次规划是线性规划的一般形式，平方约束的二次规划又是二次规划的一般形式，然而半定规划是平方约束的二次规划的更一般形式。

4.3 实例

在此之前，我们已经看到了凸优化中的大量的让人厌烦的数学和公式，接下来我们会进入最有趣的部分：使用这些技术去解决真正的问题。
- 支持向量机(Support Vector Machines,SVM)
凸优化在机器学习领域使用的最流行的其中一个应用就是SVM分类器。优化SVM分类器的算法可以描述为一个带有松弛变量的优化问题：

$$\begin{align*} \text{minimize}\ &\frac{1}{2}||w||_2^2+C\sum_{i=1}^m\xi_i\\ \text{subject to}\ &y^{(i)}(w^tx^{(i)}+b)\geq1-\xi_i,\ \ &i=1,\dots,m\\ &\xi_i\geq0,&i=1,\dots,m \end{align*}$$
其中$w\in\mathbb{R}^m,\xi\in\mathbb{R}^m,b\in\mathbb{R}$是优化变量，其中$C\in\mathbb{R}$和$x^{(i)},y{(i)},i=,\dots,m$是由问题决定的。我们要将问题化为前面提到的形式。首先，我们定义优化变量为:
$$\begin{align*} x\in\mathbb{R}^k\equiv\begin{bmatrix} w\\ \xi\\ b\\ \end{bmatrix}\ \ ,\ \ k=n+m+1 \end{align*}$$
然后定义矩阵：
$$\begin{align*} P\in\mathbb{R}^{k\times k}= \begin{bmatrix} I &0 &0\\ 0 &0 &0\\ 0 &0 &0\\ \end{bmatrix},\ \ c\in\mathbb{R}^k= \begin{bmatrix} 0\\ C\cdot{\bf -1}\\ 0\\ \end{bmatrix},\ \ G\in\mathbb{R}^{2m\times k}= \begin{bmatrix} -diag(y)X &-I &-y\\ 0 &-I &0\\ \end{bmatrix},\ \ h\in\mathbb{R}^{2m}= \begin{bmatrix} {\bf -1}\\ 0 \end{bmatrix} \end{align*}$$
这里的$I$是单位矩阵，$\bf 1$是全为1的向量，X是所有训练数据的特征向量形成的矩阵，y是对应X每行的类标签：
$$\begin{align*} X\in\mathbb{R}^{m\times n}= \begin{bmatrix} x^{(1)^T} \\ x^{(2)^T} \\ \vdots \\ x^{(m)^T} \\ \end{bmatrix},\ \ y\in\mathbb{R}^m= \begin{bmatrix} y{(1)}\\ y{(2)}\\ \vdots \\ y{(m)}\\ \end{bmatrix} \end{align*}$$
在定义了这些矩阵后，SVM优化问题就可以转化为一个二次规划问题了。事实上，很容易就可以看出SVM规划问题有一个二次目标方程和线性约束，所以我们不需要将它化为标准形式了，只有当我们需要用一个要求输入是一个标准形式的解决方法时才需要。

• 带约束的最小二乘法(Constrained least squares)
  最小二乘法问题是在已知$A\in\mathbb{R}^{m\times n}$和$b\in\mathbb{R}^m的情况下最小化$$||Ax-b||_2^2$。该问题虽然可以通过标准方程(normal equations)来求得解析解，但是假如我们对优化变量$x$加入约束范围，形式如下：
  

  $$\begin{align*} \text{minimize}\ \ &\frac{1}{2}||Ax-b||_2^2\\ \text{subject to}&l\leq x\leq u \end{align*}$$
  其中$x$是优化变量，$A\in\mathbb{R}^{m\times n},b\in\mathbb{R}^m,l\in\mathbb{R}^n,u\in\mathbb{R}^n$是根据问题而定的。这是一个二次规划问题，我们将矩阵定义如下：
  $$\begin{align*} P\in\mathbb{R}^{n\times n}=\frac{1}{2}A^TA,c\in\mathbb{R}^n =-b^TA,d\in\mathbb{R}=\frac{1}{2}b^Tb,\\ G\in\mathbb{R}^{2n\times 2n}= \begin{bmatrix} -I &0\\ 0 &-I \end{bmatrix},h\in\mathbb{2n}= \begin{bmatrix} -l\\ u\\ \end{bmatrix} \end{align*}$$

• 求逻辑回归最大似然(Maximum Likelihood for Logistic Regression)
  该模型的对数似然的形式如下：
  

  $$\ell(\theta)=\sum_{i=1}^n\{y^{(i)}\ln{g(\theta^Tx^{(i)})}+(1-y^{(i)})\ln{(1-g(\theta^Tx^{(i)}))}\}$$
  其中$g(z)$是logistic函数$g(z)=1/(1+e^{-z})$，最大似然估计可以转换为最小化对数似然函数：
  $$\text{minimize}\ \ -\ell(\theta)$$
  虽然很难将该问题转化为标准的规划问题形式，但是我们知道$\ell$是一个凸函数，所以可以通过一些算法（如牛顿迭代）来求得全局最优解。

4.4 实现:使用python实现线性SVM[TODO]

我们可以使用一些现成的软件包来解决凸优化问题，这是一种快速构建模型的方式，但是这些现成的包的实现会比最好的实现要慢，所以假如你有需要用一个更快的实现时，你需要自己完整实现一个。