Introduction

机器学习中出现了许多情况,我们都想优化某些函数的值。也就是说,给定一个函数 $f:R^n \rightarrow R$,我们想要最小化(或者最大化)$f(x)$。我们现在已经知道一些优化问题的示例:最小二乘,逻辑回归和支持向量机都被看作是优化问题。

事实证明,在一般情况下,找到函数的全局最优值可能是一项非常艰难的任务。但是对于称为凸优化的一类特殊的优化问题,我们可以在许多情况下有效地找到全局解。在这里,”有效地“ 具有实践和理论上的含义:这意味着我们可以在合理的时间内解决许多实际问题。也意味着从理论上讲,我们可以及时解决问题,并且只需要多项式级别的问题大小。

Convex Sets

如果对于任何 $x,y \in C$ 和 $\theta \in R$ 且 $0\leq \theta \leq 1$,符合下面的式子,那么集合 $C$ 就是凸的:

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

直观地讲,这意味着如果我们在 $C$ 中采用任意两个元素,并在这两个元素之间绘制一条线段,则该线段上的每个点也都属于 $C$。下图展示了一个凸集和非凸集。

点 $\theta x + (1-\theta)y$ 称为点 $x,y$ 的凸组合。

例子

  • 全部的 $R^n$。显然,给定任何 $x,y \in R^n$ ,有 $\theta x + (1-\theta)y \in R^n$。

  • 非负象限 $R^n_{+}$。非负象限包含了所有 $R^n$ 中的向量,并且元素都是非负的:$R^n_{+} = {x: x_i \geq 0,∀i =1,\cdots,n }$。为了表明这是一个凸集,只需注意给定任何 $x,y \in R^n+$ 和 $0\leq \theta \leq 1$,有

    $(\theta x + (1-\theta)y)_i= \theta x_i +(1-\theta)y_i \geq 0 \ ∀_i$

  • 范式球(what?):让 $||\cdot||$ 是关于 $R^n$ 的一些范式(如欧几里得范式,$||x||2 = \sqrt{\sum{i=1}^n x_i^2}$,集合 ${x: ||x||\leq 1}$ 是一个凸集。为了证明这一点,假设 $x,y \in R^n$ 且 $||x|| \leq 1, ||y|| \leq 1,0\leq \theta \leq 1$,然后有:

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

    在这里使用了三角形不等式和范式的正其次性。
  • 仿射子空间和正多面体。给定矩阵 $A \in R^{m \times n}$ 和向量 $b \in R^m$,则仿射子空间是集合 ${x \in R^n: Ax=b }$(如果 $b$ 不在 $A$ 里面,那么值是空)。同样的,多面体是(同样可能为空)集合 ${ x \in R^n: Ax \leq b }$ ,在这里 $\leq$ 表示分量不等式(即,$Ax$ 的所有条目均小于或等于它们在 $b$ 中的对应元素)。为了证明这一点,首先考虑 $x,y \in R^n$ 使得 $Ax=Ay=b$,然后对于 $0 \leq \theta \leq 1$ 有:

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

    类似的,对于 $x,y \in R^n$ 且满足 $Ax \leq b, Ay \leq b, 0\leq \theta \leq 1$,有
$A(\theta x + (1-\theta)y) = \theta Ax + (1-\theta)Ay \leq \theta b + (1 - \theta)b =b$

* 凸集的交集。假设 $C_1, C_2,\cdots,C_k$ 是凸集,然后他们的交集
$\bigcap_{i=1}^k C_i = \{x:x \in C_i, \ ∀_i = 1,\cdots,k \}$

也是个凸集。为了证明这一点,考虑 $x,y \in \bigcap_{i=1}^k C_i$ 和 $0\leq \theta \leq 1$,根据凸集的定义有
$\theta x + (1-\theta)y \in C_i , ∀_i = 1,\cdots,k$

因此
$\theta x + (1-\theta) y \in \bigcap _{i=1}^k C_i$

注意的是,通常凸集的并集不会是凸集。
  • 正半定矩阵。所有对称正半定矩阵的集合(通常称为正半定锥,表示为 $S^n_{+}$)是一个凸集(通常 $S^n \in R^{n \times n }$ 表示 $n$ 阶对称方阵的集合)。回想一下,当且仅当所有 $x \in R^n,x^TAx \geq 0$ 且 $A = A^T$ 矩阵 $A \in R^{n \times n}$ 才是对称半正定矩阵。现在仅考虑两个对称半正定矩阵 $A,B \in S^n_+$ 和 $0 \leq \theta \leq 1$。对于所有 $x \in R^n$ 有

    $x^T(\theta A +(1-\theta)B)x = \theta x^TAx +(1-\theta)x^T Bx \geq 0$

    同样,上述过程适用于所有正定,负定和半负定矩阵,都是凸集。

Convex Functions

凸优化的核心概念是凸函数。

如果函数 $f:R^b \rightarrow 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)$

那么该函数就是凸的。

直观的,直观地,考虑该定义的方式是,如果我们在凸函数的图形上选取任意两个点,然后在它们之间画一条直线,则这两个点之间的函数部分将位于该直线之下。如下图所示:

如果在上述定理中 $x\neq y, 0 < \theta < 1$ 则严格不等式成立,那么我们说函数 $f$ 是严格凸的。如果 $-f$ 是凸的,那么 $f$ 则是凹的,如果 $-f$ 是严格凸的,那么 $f$ 则是严格凹的。

凸的一阶条件

假设函数 $f:R^n \rightarrow R$ 是可微的(在 $f$ 的定义域内,任何点 $x$ 的梯度 $\nabla_x f(x)$ 都存在)。当且仅当 $D(f)$ 是一个凸集,对于所有 $x,y \in D(f)$ ,有如下式子成立,那么函数 $f$ 是凸的。

$f(y) \geq f(x) + \nabla_x f(x)^T (y-x)$

函数 $f(x) + \nabla_x(x)^T(y-x)$ 在点 $x$ 处被称为函数 $f$ 的一阶逼近。直观的讲,可以认为是 $f$ 与 $x$ 点处的切线近似。凸的一阶条件说,当且仅当切线是函数f的整体低估量时,$f$ 才是凸的。换句话说,如果我们采用函数并在任意点绘制切线,则该线上的每个点都将位于 $f$ 上对应点的下方。

类似于凸度的定义,如果 $f$ 包含严格不等式,则 $f$ 将为严格凸;如果不等式被逆,则 $f$ 将为凹;如果反向不等式为严格,则 $f$ 将为严格凹。

凸的二阶条件

假设函数 $f: R^n \rightarrow R$ 是二次可微的(在 $f$ 的定义域内,任何点 $x$ 的 $Hessian \ \nabla_x^2f(x)$ 是存在的)。当且仅当 $D(f)$ 是凸集,且 $Hessian$ 是半正定时,函数 $f$ 才是凸的:即对于所有 $x \in D(f)$

$\nabla_x^2 f(x) \geq 0$

在一维度上,这等效于二阶导 $f^{''}(x)$ 始终是非负的。

再次类似于凸集的定义和一阶条件,如果 $f$ 的 $Hessian$ 为正定,则 $f$ 为严格凸,如果 $Hessian$ 为负半定,则为凹,如果 $Hessian$ 为负,则 $f$ 为严格凹。

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_ix_i) \leq \sum_{i=1}^k \theta_i f(x_i) \ , \ \ for \ \ \sum _{i=1}^k \theta_i = 1, \theta_i \geq 0 \ \ ∀_i $

实际上,这也可以扩展为无限的和或积分。 在后一种情况下,不等式可以写成
$f(\int p(x)xdx) \leq \int p(x)f(x)dx \ , \ \ for \ \ \int p(x)dx = 1, p(x) \leq 0, \ ∀_x$

因为 $p(x)$ 积分为 $1$,所以通常将其视为概率密度,在这种情况下,可以使用期望改写上一个式子
$f(E[x]) \leq E[f(x)]$

这个式子就是 $Jensen$ 不等式。

子集

凸函数产生一个特别重要的凸集类型,称为 $\alpha$ 子集。给定凸函数 $f: R^n \rightarrow R$ 和实数 $\alpha \in R$ ,则 $\alpha$ 子集为

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

换句话说,$\alpha$ 子集是所有满足 $f(x) \leq \alpha$ 的点 $x$ 集合。

为了表明这是一个凸集,对于任何 $x,y \in D(f)$ 使 $f(x) \leq \alpha $ 和 $f(y) \leq \alpha $,有

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

### 例子

下面从一个变量的凸函数的几个例子开始,然后转到多个变量的凸函数。

  • 指数函数:令 $f:R \rightarrow R, \ f(x) = e^{ax}$,为了证明 $f$ 是凸的,只需要证明二次导数 $f^{‘’}(x) = a^2e^{ax}$ 对所有 $x$ 都是正数即可。

  • 负对数函数:令 $f: R \rightarrow R, \ f(x) = -logx $ ,其定义域 $D(f) \in R_{++}$ 表示为严格正数。则 $f^{‘’}(x) = {1\over x^2} > 0$。

  • 仿射函数:令 $f:R^n \rightarrow R, \ f(x) = b^Tx +c$,其中 $b \in R^n, C\in R$。在这里 $Hessian$ 矩阵 $\nabla_x^2 f(x) = 0$。因为零矩阵都是正半定和负半定,所以 $f$ 既是凸的又是凹的。 实际上,这种形式的仿射函数是唯一既凸又凹的函数。

  • 二次函数:令 $f: R^n \rightarrow R, \ f(x) = {1\over 2} x^T Ax + b^Tx +c$ ,其中 $A \in S^n, b \in R^n, c \in R$。 该函数的 $Hessian$ 矩阵为

    $\nabla_x^2 f(x) = A$

    因此,函数 $f$ 的凹凸性由 $A$ 是否是半正定确定。如果 $A$ 为正半定,则函数为凸(类似地,同样适用于严格凸,严格凹);如果A是不确定的,则 $f$ 既不是凸也不是凹。

欧几里得范式 $f(x) = ||x||^2_2 = x^Tx$,是二次函数的特殊形式,其中 $A= I,b=0,c=0$。因此它是严格的凸函数。

  • 范式:令 $f: R^n \rightarrow R$ 是一些范式,通过三角函数和范式的正齐次性,对于所有 $x,y\in R^n, 0 \leq \theta \leq 1$ 有

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

    这是一个特殊的示例,因为通常范式都是不可微的。
  • 凸函数的非负加权和:令 $f_1,\cdots,f_k$ 是凸函数,$w_1,\cdots,w_k$ 是非负实数,则

    $f(x) = \sum_{i=1}^k w_i f_i(x)$

    是凸函数,因为
$\begin{align} f(\theta x + (1-\theta)y) &= \sum_{i=1}^k w_if_i(\theta x +(1-\theta)y) \\ &\leq \sum_{i=1}^k w_i(\theta f_i(x) + (1-\theta)f_i(y)) \\ &= \theta \sum_{i=1}^k w_i f_i(x) + (1-\theta) \sum_{i=1}^k w_if_i(y) \\ &= \theta f(x) + (1-\theta) f(y) \end{align}$

## Convex Optimization Problems

有了凸函数和凸集合的定义,我们现在可以考虑凸优化问题。 形式上的,凸优化问题是如下形式的最优化问题

$\begin {align}minimize \ \ & f(x) \\ subject \ to \ \ & x\in C \end{align}$

其中 $f$ 是凸函数,$C$ 是凸集,$x$ 是优化变量。更具体一点的写法是

$\begin{align} minimize \ \ & f(x) \\ subject \ to \ \ & g_i(x) \leq 0, \ \ i = 1 ,\cdots,m \\ & h_i(x) = 0, \ \ i = 1 , \cdots, p \end{align}$

其中,$f$ 是凸函数,$g(x)$ 是凸函数,$h(x)$ 是仿射函数,$x$ 是优化变量。

注意的是,这些不等式的方向很重要:$g(x)$ 是必须小于 $0$ 的凸函数,这是因为 $g(x)$ 的 $0$ 子级集是凸集,所以可行区域(是许多凸集的交集)也是凸的(回想一下仿射子空间也是凸集)。如果我们对于某个凸 $g_i$ 要求 $g_i≥0$,则可行区域将不再是凸集,并且将不再保证我们解决这些问题的算法找到全局最优值。还要注意,仅仿射函数被允许为等式约束。 直观地,可以认为这是由于等式约束等于两个不等式 $h_i≤0$ 和 $h_i≥0$。但是,当且仅当 $h_i$ 既是凸面又是凹面,即仿射必定是仿射的,这些都是有效约束。

最优化问题的最优值表示为 $p^$(有时为 $f^$),它等于可行区域中目标函数的最小可能值。

$p^* = min\{f(x):g_i(x)\leq 0,i=1,\cdots,m, h_i(x)=0,i=1,\cdots,p \}$

如果问题无解(可行域为空),或者无下界(存在点使 $f(x)\rightarrow -\infty$)时,允许 $p^$ 取 $\infty$ 或者 $-\infty$。如果 $f(x^)=p^$ ,则 $x^$ 是最佳值点。 请注意,即使最佳值为有限,也可以有多个最佳点。

凸问题的全局最优解

在陈述凸问题的全局最优结果之前,让我们正式定义局部最优和全局最优的概念。 直观地,如果没有“较低”目标值的“附近”可行点,则可行点称为局部最优。 类似地,如果根本不存在具有较低目标值的可行点,则将可行点称为全局最优。 为了使它更正式一点,我们给出以下两个定义。

如果一个点 $x$ 是可行的(即满足优化问题的约束),并且存在某个 $R> 0$,使得所有满足 $||x-z||_2 ≤R$ 的可行点 $z$ 都满足 $f(x )≤f(z)$。

如果一个点 $x$ 可行,并且对于所有可行点 $z$,有 $f(x)≤f(z)$。

现在,我们讨论凸优化问题的关键要素,它们将从中得到大部分效用。 关键思想是对于凸优化问题,所有局部最优点都是全局最优的。

让我们通过矛盾来快速证明此属性。 假设 $x$ 不是全局最优的局部最优点,即存在一个可行点 $y$ 有 $f(x) > f(y)$。根据局部最优的定义,不存在可行点 $z$ 使 $||x-z||_2\leq R$ 和 $f(z) < f(x)$ 。但是现在假设有这么一个点,

$z = \theta y + (1-\theta)x , \ with \ \ \theta = {R\over 2 ||x -y||_2}$

然后有

$\begin{align} ||x-z||_2 &= ||x - ({R\over 2||x-y||_2} y + (1- {R\over 2||x-y||_2})x)||_2 \\ &= ||{R\over 2||x-y||_2 }(x-y)||_2 \\ &= {R\over 2} \leq R \end{align}$

另外,通过 $f$ 的凸性,我们有

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

此外,由于可行集是凸集,并且由于 $x$ 和 $y$ 都是可行的,因此,$z = \theta y + (1-\theta)$ 也是可行的。因此,$z$ 是一个可行点,其中 $||x-z||_2 \leq R , f(z) < f(x)$。这与我们的假设相矛盾,表明 $x$ 不可能是局部最优的。

凸问题的特例

由于各种原因,考虑一般凸规划公式的特殊情况通常很方便。 对于这些特殊情况,我们通常可以设计出非常有效的算法来解决非常大的问题,因此,当人们使用凸优化技术时,您可能会看到这些特殊情况。

  • 线性规划:如果目标函数 $f$ 和不等式 $g_i$ 都是仿射函数,并且有如下形式,我们就说这是线性规划问题(LP)

    $\begin{align} minimize \ \ & c^Tx + d \\ subject \ to \ \ & Gx \leq h \\ & Ax = b\end{align}$

    其中,$x \in R^n$ 是优化变量,$c\in R^n,d\in R, G \in R^{m\times n}, h\in R^m , A\in R^{p\times n}, b \in R^p$.

  • 二次规划:如果不等式 $g_i$ 是仿射的,但是目标函数是二次凸函数,那么该凸优化问题称为二次规划问题(OP)

    $\begin{align} minimize \ \ & {1\over 2} x^TPx + c^T x +d \\ subject \ to \ \ & Gx \leq h \\ & Ax = b \end{align}$

  • 二次约束二次规划

  • 半定规

例子

  • SVM

  • 约束最小二乘

  • 最大似然估计的逻辑回归