凸优化简介

在machine learning 的很多问题中，我们最终往往要求解某个函数的最优值。用数学术语表示就是， 给定一个函数 $f: R^{n} \rightarrow R$，求 $ x \in R^{n} $使得$f(x)$ 取得最小（大）值。例如least-square, logistic regression, linear regression, svm, etc. 这类问题统称为优化问题。

1.引言

在一般情况下，求解任意一个函数的全局最优值是很困难的。但是对于一种特定类型的函数——凸函数（convex function）， 我们可以很有效的求解其全局最优值。这里的“有效”是指在实际问题求解中，能在多项式复杂度的时间里求解。 人们将这类函数的最值问题称为凸优化问题（Convex Optimal Problem）。下面我从凸集和凸函数讲起，然后 介绍凸优化的一般描述和典型问题举例。

2.凸集及其实例

凸集的定义：一个集合$C$是凸集，当且仅当对任意$x,y\in C$和$\theta \in R$且$0\leq \theta \leq 1$，都有

$\theta x + (1-\theta)y \in C$. 其几何意义在于，在集合C中任取两个点，连接两点的直线段上的任一点也在集合C中。下图是凸集和非凸集的例子：

凸集的实例： 以下列举几个简单的凸集实例
（1）所有Rn。很显然，对任意给定的$x,y\in R^{n}$ 都有 $\theta x + (1-\theta)y \in R^{n}$。 （2）非负卦限，R^{n}_{+}。很显然也符合定义。
（3）单位球。设$\parallel . \parallel$为$R^{n}$上的模（例如欧几里得空间的模为$\parallel x\parallel = sqrt(sum(x_{i}^{2}))$.）, 那么集合${x|\parallel x\parallel \leq 1}$是一个凸集。

3.凸函数及判定和Jensen不等式

凸优化中的一个核心概念就是凸函数。
凸函数定义：一个函数$f: R^{n} → R$是凸函数当且仅当其定义域（设为$D(f)$）是凸集， 且对任意的$x,y\in D(f)$和$\theta \in R$且$0\leq \theta \leq 1$，都有

$f(\theta x + (1-\theta)y \leq \theta f(x) + (1-\theta) f(y))$. 设$f(x)$为一元函数，那么上式的几何意义在于，曲线上任意两点处的割线在函数曲线的上方，如下图所示：

常见的凸函数有指数函数（$f(x) = a^{x}，a>1$）、负对数函数（$f(x)=-log_{a}x，a>1，x>0$）、开口向上的二次函数等。

凸函数第一判定定理：设函数$f: R^{n} → R$是一阶可导的，那么$f$是凸函数当且仅当对任意的$x,y \in D(f)$都有：

$f(y) \geq f(x) + f'(x)(y-x)$ 其中$f(x) + f'(x)(y-x)$称为$f(x)$在$x$处的一阶近似。

凸函数第二判定定理：设函数$f: R^{n} → R$是二阶可导的，那么$f$是凸函数当且仅当对任意的$x\in D(f)$都有：

$f''(x) \succeq 0$.

其中，当$f''(x)$是矩阵时，符号‘$ \succeq $’表示半正定，而非一个个的不等式（在一维的情况下，相当于'$\geq$'； 在二维情况下，不是表示对所有的$i$和$j$都有$X_{ij} \geq 0$，而是表示$X$为半正定矩阵）。

Jensen不等式：我们先看凸函数的定义中的不等式:

$f(\theta x+(1-\theta y)) \leq \theta f(x) + (1-\theta)f(y), for 0\leq \theta \leq 1$. 类似的可以将其推广到多个点的情况：
$f(\sum_{i=1}^{k}\theta_{i}x_{i}) \leq \sum_{i=1}{k}\theta_{i}f(x_{i}), for \sum_{i=1}^{k}\theta_{i} = 1, \theta_{i} \geq 0 \forall i$. 因为上式中的和为1，可以将其看作为是概率密度，则上式又可写为：
$f(E[x]) \leq E[f(x)]$. 这个不等式称为Jensen不等式。

4.凸优化问题举例

有了凸集和凸函数的定义，现在我们重点讨论凸优化问题的求解方法。凸优化的一般描述为：

$minimize f(x)$, $subject to x \in C$. 其中$f(x)$为凸函数，$C$是一个凸集，这是不带约束条件的情况下的凸优化问题。对于带约束条件的问题而言，其一般描述为：
$minimize f(x)$, $subject to g_{i}(x) \leq 0, i=1,2,...,m; h_{j}(x) = 0, j=1,2,...,p$. 其中$f(x)$为凸函数，$g_{i}(x)$对所有的$i$均为凸函数，$h_{j}(x)$均为仿射函数。注意$g_{i}(x)$不等式中不等号的方向。

凸问题中的全局优化：首先要分清楚什么是局部最优，什么是全局最优。局部最优是指在该最优值附近的点对应的函数值 都比该最优值大，而全局最优是指对可行域里所有点，其函数值都比该最优值大。对于凸优化问题，它具有一个很重要的特性， 那就是所有的局部最优值都是全局最优的（关于其证明这里就不讲了，感兴趣的可以自行查查资料或后文中的参考文献）。

几类特殊的凸优化问题：

（1）线性规划（Linear Programing, LP）: 目标函数和约束条件函数都是线性函数的情况，一般形式如下：

$minimize c^{T}x +d$, $subject to Gx \preceq h; Ax = b$.

（2）二次规划（Quadratic Programing, QP）: 目标函数为二次函数，约束条件为线性函数，一般形式为：

$minimize 1/2 x^{T}Px + c^{T}x +d$, $subject to Gx \preceq h; Ax = b$. LP可以看做是QP的特例，QP包含LP。

（3）二次约束的二次规划（Quadratically Constrained Quadratic Programming, QCQP）: 目标函数和约束条件均为 二次函数的情况，一般形式为：

$minimize 1/2 x^{T}Px + c^{T}x +d$, $subject to 1/2 x^{T}Qx + r^{T}x + s \preceq h, i=1,2,...,m; Ax = b$. QP可以看做是QCQP的特例，QCQP包含QP。

半正定规划（Semidefinite Programming，SDP）: 其一般形式为：

$minimize tr(CX)$, $subject to tr(A_{i}X) = b_{i},i=1,2,...,p; 0 \preceq X$. 其中对称矩阵$X\inS^{n}$为决策变量，矩阵$C$，$A_{i}$均为对称矩阵，条件$0 \preceq X$的作用为约束$X$为半正定的。 QCQP可以看做是SDP的特例，SDP包含QCQP。SDP在machine learning中有非常广泛的应用。

5.凸优化应用举例

下面我们来看几个实例。
（1）支持向量机（Support Vector Machines，SVM）：凸优化在machine learning中的一个典型的应用就是基于支持向量机分类器， 它可以用如下优化问题表示：

$minimize 1/2 \parallel x \parallel ^{2} + C \xi _{i}$, $subject to y^{(i)}(w^{T}x^{(i)}+b) \geq 1 - \xi _{i}, \xi_{i} \geq 0, i = 1,2,...,m$. 其中决策变量$w\in R^{n}, \xi \in R^{n}, b \in R$. $C\in R, x(i), y(i), i=1,2, ... , m$由 具体问题定义。可以看出，这是一个典型的QP问题。

（2）带约束的least squares问题：其一般描述为

$minimize 1/2\parallel Ax-b \parallel ^{2} $, $subject to l \preceq x \preceq u$. 这也是一个很典型的QP问题。

（3）Maximum Likelihood for Logistic Regression：该问题的目标函数为:

$l (\theta) = \sum_{i=1}^{n}[y^{(i)}ln g(\theta^{T}x^{(i)}) + (1-y^{(i)})ln(1-g(\theta^{T}x^{(i)}))]$ 其中$g(z)$为Sigmoid函数，关于Logistic Regression请参见Andrew Ng的Machine Learning的第6讲。

6.凸优化问题求解简介

上文中提到了几类特殊的凸优化问题，并举了几个应用实例，但并没有给出解法。对于凸优化问题，目前没有一个通用的解析式的 解决方案，但是我们仍然可以用非解析的方法来有效的求解很多问题。内点法（后续文章中会详细介绍）被证明是很好的解决方案， 特别具有实用性，在某些问题中，能够在多项式时间复杂度下，将解精确到指定精度。

我们将会看到，经过10到100次的迭代，内点法可以解决一般的凸优化问题，其中每次迭代的时间复杂度为

$max{n^{3},n^{2}m,F}$. 其中$F$为计算目标函数和约束条件函数的一阶、二阶导数的总时间代价。如同用解析法求解线性规划问题，内点法也是非常可靠的， 在一般的PC机上，它可以在几十秒的时间内求解含有上百个变量、上千个约束条件的凸优化问题。对于一些特殊的结构（如稀疏的）， 内点法可以求解包含上千个变量和约束条件的凸优化问题。

对于一般的凸优化问题的求解，还没有像求解最小二乘和线性规划那么成熟的技术，基于内点法的一般凸优化问题求解依然是 当前的一个研究热点。虽然目前还没有公认的最好的解决方案，但我们有理由相信，在不久的将来，内点法求解一般的凸优化问题 是一项技术。事实上，对于一些特定的凸优化问题，如二次锥规划和几何规划问题（后续文章将会介绍），内点法在向一项技术迈进。

参考文献

[1]Book: Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004
[2]Slide: Zico Kolter (updated by Honglak Lee). Convex Optimization Overview. October 17, 2008
[3]Standford Convex Optimization Course I：http://www.stanford.edu/class/ee364a/lectures.html