凸优化入门 - 基本概念与 Jensen 不等式-轻识

1引言

机器学习中经常会碰到希望优化某个函数值的问题。

例如，给定一个函数，我们想找一个使取最小值（或取最大值）。具体如最小二乘、逻辑回归和支持向量机等这些问题都可被视为优化问题。

事实上，找到函数的全局最优值在一般情况下可能是一项非常困难的任务。但是，对于一类特殊的优化问题，即凸优化问题，在许多情况下我们可以有效地找到全局最优解。

这意味着我们可以在合理的时间内解决许多实际问题，即从理论上来讲，我们可以在问题规模的多项式复杂度内及时解决问题。

2凸集

.定义

线段给定两点之间的线段，是指所有点

\theta x+(1-\theta) y

的集合，其中且。

凸集如果对于中任意两点，它们间的线段仍然属于，即对于且，都有

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

成立，则称集合是凸的。

直观地讲，这意味着如果我们在中任意取两个点，并在这两个点之间绘制一条线段，则该线段上的每一点也都属于。

点也称为点和的凸组合。下图显示了两个凸集（左、中图）和一个非凸集（右图）的示例。

.一些例子

所有

很明显，给定任意，都有

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

非负象限

非负象限由中的所有元素非负的向量组成，即

\mathbb{R}_{+}^{n}=\left\{x: x_{i} \geq 0 \quad \forall i=1, \ldots, n\right\}.

为了验证这是凸集，只需注意给定任意和，有

\begin{array}{l} &(\theta x+(1-\theta) y)_{i}\\[0.8em]&=\theta x_{i}+(1-\theta) y_{i} \\[0.8em]&\geq 0 \quad \forall i. \end{array}

范数球

假设是上某个范数（例如，欧几里得范数，，则集合是凸集。

假设，其中，以及，则有

\begin{array}{l} &\|\theta x+(1-\theta) y\| \\[0.8em]&\leq\|\theta x\|+\|(1-\theta) y\|\\[1em]&=\theta\|x\|+(1-\theta)\|y\| \\[1em]&\leq 1 \end{array}

这里使用了范数定义中的三角形不等式和正齐次性。

仿射子空间和多面体

给定矩阵和向量，仿射子空间是集合（请注意，如果不在的值域内，则仿射子空间为空）。

类似地，多面体是（再次可能是空的）集合，其中在这里表示分量不等式（即的所有元素均小于或等于的相应分量）。

为了证明这一点，首先考虑满足的，以及，有

\begin{array}{l} &A(\theta x+(1-\theta) y)\\[0.8em]&=\theta A x+(1-\theta) A y\\[0.8em]&=\theta b+(1-\theta) b\\[0.8em]&=b. \end{array}

同样，对于满足、以及的，有

\begin{array}{l} &A(\theta x+(1-\theta) y)\\[0.8em]&=\theta A x+(1-\theta) A y \\[0.8em]&\preceq \theta b+(1-\theta) b\\[0.8em]&=b. \end{array}

类似地，对于两个向量，表示的每个分量大于或等于的每个分量。有时候，用代替，具体可以根据上下文确定（即，不等式的两侧都是向量）。

凸集的交集

假设是凸集。然后他们的交集

\bigcap_{i=1}^{k} C_{i}=\left\{x: x \in C_{i} ,\;\forall i=1, \ldots, k\right\}

仍然是凸集。假设以及。然后，由凸集的定义可得，

\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}.

凸集的交集示例

但是请注意，凸集的并集通常不会是凸集。

凸集的并集示例

半正定矩阵

所有对称半正定矩阵的集合（通常称为半正定锥并表示为）是一个凸集（通常用表示对称矩阵的集合）。

当且仅当且对于所有，有成立，则矩阵是对称半正定的。

现在考虑两个对称半正定矩阵和。然后对于任意，有

\begin{array}{l} &x^{\top}(\theta A+(1-\theta) B) x\!\!\!\\[0.8em]&=\theta x^{\top} A x+(1-\theta) x^{\top} B x \\[0.8em]&\geq 0. \end{array}

相同道理，可以证明所有正定、负定和半负定矩阵的集合也都是凸集。

3凸函数

.定义

凸函数 对于函数，如果它的定义域是一个凸集，并且对于所有，，，有

\begin{array}{c} &f(\theta x+(1-\theta) y)\\[0.8em]& \leq \theta f(x)+(1-\theta) f(y) \end{array}

则函数称为凸函数。

为了更加形象地理解凸函数，我们画个图看看。假设，如果取凸函数上的两点并在它们之间连一条线段，那么两点之间的函数部分都会在这条线段之下。请看下图中的蓝色曲线，而橙色曲线对应的函数就不是凸函数啦。

进一步定义，如果上述定义对且的条件成立，则称函数为严格凸函数。如果函数为凸的，则定义为凹的，严格凹函数的定义以此类推。

注意: 这里要求的域是凸集主要是为了确保是有定义的（如果不是凸的，即使，那么也可能不在定义域内，因此未定义。

请指出下图中哪些是凸函数，哪些不是凸函数。

4凸性条件

有了凸函数的定义，那是不是想知道凸函数有些什么特别之处呢？反过来满足什么性质的函数是凸函数呢？

.凸性的一阶条件（First Order Condition for Convexity）

假设函数可微（即对于所有，导数恒存在），当且仅当为凸集且对于所有，

f(y) \geq f(x)+\nabla_{x} f(x)^{\top}(y-x)

都成立的时候，可以称函数是凸函数。

函数在点处称为函数的一阶逼近。

直观地讲，这可以认为是与其在点处的切线近似。

凸度的一阶条件说，当且仅当切线整体在函数的下面时，才是凸的。

可以通过下面的图来直观地理解什么是凸性的一阶条件: 对于凸函数上的任一点，该点处的切平面都将在函数下方。

.凸性的二阶条件（Second Order Condition for Convexity）

假设函数是两次可微的（即，的定义域中的所有点都有定义 Hessian 矩阵）。当且仅当为凸集且其 Hessian 矩阵为半正定数时，才是凸的: 即对于任何，有

\nabla_{x}^{2} f(x) \succeq 0.

此处，该符号如果跟矩阵结合使用时，指该矩阵是半正定的，而不是分量不等式。当一维时，这等价于二阶导数始终非负。

类似于凸性一阶条件的定义，如果的 Hessian 为正定，则为严格凸，如果 Hessian 为半负定，则为凹，如果 Hessian 为负定，则为严格凹。

5Jensen 不等式

我们从凸函数的基本定义出发，对于，有

\begin{array}{c} &f(\theta x+(1-\theta) y) \\[0.8em]&\leq \theta f(x)+(1-\theta) f(y). \end{array}

使用归纳法，可以很容易地将其扩展到多个点的凸组合，对于，有

f\left(\sum_{i=1}^{k} \theta_{i} x_{i}\right) \leq \sum_{i=1}^{k} \theta_{i} f\left(x_{i}\right).

实际上，这也可以扩展为无限项之和以及积分。对于积分，当时，有

f\left(\int p(x) x d x\right) \leq \int p(x) f(x) dx.

由于积分为，因此通常将其视为概率密度函数，在这种情况下，可以用期望来改写前面的等式，

f(\mathbf{E}[x]) \leq \mathbf{E}[f(x)].

最后这个不等式被称为琴生不等式或者詹森不等式。

可以结合下图来理解上面的不等式。至于这个公式的意义和应用等后面再来揭示哈。

⟳参考资料⟲

[1]

Zico Kolter, Honglak. Lee: http://cs229.stanford.edu/section/cs229-cvxopt.pdf.

凸优化入门 - 基本概念与 Jensen 不等式

1引言

2凸集

.定义

.一些例子

3凸函数

.定义

4凸性条件

.凸性的一阶条件（First Order Condition for Convexity）

.凸性的二阶条件（Second Order Condition for Convexity）

5Jensen 不等式

⟳参考资料⟲

.相关阅读

拉格朗日乘子法的来历与直观解释

雅可比矩阵几何意义的直观解释及应用

最优化理论发展简史 - 群英璀璨，全知道就服你！