• 参考材料:CS 229 讨论课笔记(原材料为英文), 更新了一些内容
  • 推荐材料:Optimization Model / Convex Optimization / Numerical Optimization

机器学习中的很多情况实际上都是在优化某些函数的值,即给定函数 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$, 我们想要找到使得 $f(x)$ 最小(或最大)的 $x \in \mathbb{R}^{n}$. 在最小二乘、逻辑回归与支持向量机等算法中,可以构造为优化问题的形式去理解。通常情况下,找到某个函数的全局最优点是一项非常困难的任务。然而对于优化问题中的一个特定领域——凸优化问题——在许多情况下可以高效地找到全局最优解。此处的“高效”既指实际应用中,亦包括理论分析角度:这意味着我们可以在合理的时间内解决许多现实世界中的问题,也意味着理论上我们可以及时解决只取决于规模大小的多项式问题。

凸集

我们将从凸集的概念入手进而开始学习凸优化。定义如下:如果对于任意 $x, y \in C$ 与 $\theta \in \mathbb{R} (0 \leq \theta \leq 1)$, 都有 $\theta x+(1-\theta) y \in C$, 则称集合 $C$ 是凸的。直觉上理解,如果我们从 $C$ 中取任意两个元素,并在这两个元素之间画一条线段,线段上的所有点也属于 $C$. 下图展示了凸集和非凸集的一个例子:

凸集举例

  • 所有的 $\mathbb{R}^{n}$. 显然给定任意 $x, y \in \mathbb{R}^{n}$, 有 $\theta x+(1-\theta) y \in \mathbb{R}^{n}$.
  • 非负卦限 $\mathbb{R}_{+}^{n}$. 非负卦限包含 $\mathbb{R}^{n}$ 中满足所有元素非负的所有向量:

    为了显示这是一个凸集,可以简记为给定任意 $x, y \in \mathbb{R}_{+}^{n}$ 与 $\theta \in \mathbb{R}$ ($0 \leq \theta \leq 1$), 有

  • 范数球。令 $\|\cdot\|$ 表示 $\mathbb{R}^{n}$ 上的某范数(例如欧氏范数 $\|x\|_{2}=\sqrt{\sum_{i=1}^{n} x_{i}^{2}}$). 则 $\{x :|x| \leq 1\}$ 是一个凸集。为了证明这一点,设 $x, y \in \mathbb{R}^{n}$, 且有 $\|x\| \leq 1$, $\|y\| \leq 1$ 与 $0 \leq \theta \leq 1$, 则有:

  • 仿射子空间和多面体。给定矩阵 $A \in \mathbb{R}^{m \times n}$ 与向量 $b \in \mathbb{R}^{m}$, 仿射空间为集合 $\left\{x \in \mathbb{R}^{n} : A x=b\right\}$ (注意如果 $b$ 不在 $A$ 的范围内,集合可能为空). 类似地,多面体表示的集合(也可能是空集) 为 $\left\{x \in \mathbb{R}^{n} : A x \preceq b\right\}$, 其中 $\preceq$ 表示分量间不等(即 $Ax$ 中所有的元素小于或等于 $b$ 中对应的元素).为了证明这一点,先考虑 $x, y \in \mathbb{R}^{n}$ 满足 $A x=A y=b$, 则对于 $0 \leq \theta \leq 1$,

    类似地,对于 $x, y \in \mathbb{R}^{n}$ 满足 $A x \leq b$ 与 $A y \leq b$, 则对于 $0 \leq \theta \leq 1$,

    顺便提一下,对于两个向量 $x, y \in \mathbb{R}^{n}$, $x \succeq y$ 表示 $x$ 中的每一个元素都大于或者等于 $y$ 中对应元素。注意有时候会用 $\leq$ 和 $\geq$ 代替 $\preceq$ 和 $\succeq$, 具体含义由上下文决定。

  • 凸集的交。设 $C_{1}, C_{2}, \ldots, C_{k}$ 为凸集,则它们的交集

    也是一个凸集。为了证明这一点,考虑 $x, y \in \bigcap_{i=1}^{k} C_{i}$ 和 $0 \leq \theta \leq 1$, 则有

    根据凸集的定义,因此有

    但是注意,凸集的并通常并不是凸的。

  • 半正定矩阵。所有半正定矩阵的集合,通常被称为半正定锥,记作 $S_{+}^{n}$, 是一个凸集(通常,$\mathbb{S}^{n} \subset \mathbb{R}^{n \times n}$ 表示 $n \times n$ 对称矩阵的集合). 回想一下矩阵 $A \in \mathbb{R}^{n \times n}$ 是对称半正定矩阵,当且仅当 $A=A^{T}$, 且对所有 $x \in \mathbb{R}^{n}$, 有 $x^{T} A x \geq 0$. 现在考虑两个对称半正定矩阵 $A, B \in \mathbb{S}_{+}^{n}$ 与 $0 \leq \theta \leq 1$. 则对任意 $x \in \mathbb{R}^{n}$,

    同样的逻辑也可以被用来证明所有的正定矩阵、负定矩阵和半负定矩阵的集合也分别是凸的。

凸函数

凸优化的一个核心要素是凸函数的概念。如果函数 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 的定义域 $\mathcal{D}(f)$ 是一个凸集,且满足对所有的 $x, y \in \mathcal{D}(f)$ 与 $\theta \in \mathbb{R}, 0 \leq \theta \leq 1$, 有

则称这样的函数为凸函数。直观地理解该定义,我们从一个凸函数图像上取任意两点并作一条直线,两点之间对应的直线部分将位于这条线的下方,如图所示:

如果上述定义中对 $x \neq y$ 和 $0<\theta<$ 严格不等,则称函数是严格凸的。如果 $-f$ 是凸函数,我们则说函数 $f$ 是凹的;类似地,如果 $-f$ 是严格凸函数,则函数 $f$ 是严格凹的。

凸性的一阶条件

假设函数 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 可微(即在 $f$ 定义域的所有点 $x$ 都存在其梯度 $\nabla_{x} f(x)$), 当且仅当满足以下条件时函数 $f$ 是凸的:对所有 $x, y \in \mathcal{D}(f)$,

函数 $f(x)+\nabla_{x} f(x)^{T}(y-x)$ 被称为函数 $f$ 在点 $x$ 处的一阶近似。直觉上可以认为是用点 $x$ 处的切线近似 $f$. 凸性的一阶条件表明当且仅当切线是函数 $f$ 的全局下估计时,函数是凸的。也即是说,我们在函数上任意一点作切线,线上任意一点都位于 $f$ 上对应点的下方,如图所示:

类似于凸性的定义,如果它严格不等,则 $f$ 是严格凸的,如果不等式反转,则 $f$ 是凹的,如果反转后的不等式是严格的,则 $f$ 是严格凹的。

凸性的二阶条件

假设函数 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 二次可微(即在 $f$ 定义域的所有点 $x$ 都存在其 Hessian 矩阵 $\nabla_{x}^{2} f(x)$), 当且仅当 $\mathcal{D}(f)$ 是凸集且 Hessian 为半正定时(即对任意 $x \in \mathcal{D}(f)$ 有 $\nabla_{x}^{2} f(x) \succeq 0$), 此时 $f$ 为凸函数。一维的情况下,等同于二阶导数 $f^{\prime \prime}(x)$ 总是非负的。

这里的符号 $\succeq$ 当与矩阵结合使用时,指的是半正定性,而不是分量间不等。类似地,对于对称矩阵 $X \in \mathbb{S}^{n}$, $X \preceq 0$ 表示 $X$ 是半负定矩阵。尽管它们与向量不等式具有符号相似性,但这些概念却截然不同;通常 $X \succeq 0$ 并不意味着对所有的 $i$ 和 $j$ 都有 $X_{i j} \geq 0$.

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

琴生不等式

假设我们从凸函数的基本定义中的不等式开始

使用归纳法,可以相当容易地推广到到多个点的凸组合,

实际上,这也可以推广到无限求和或积分形式。在后一种情况下,不等式可以写成

因为 $p(x)$ 积分为 $1$, 通常将其考虑为概念密度,在这种情况下前面的式子可以改写为期望的形式,

最后得到的不等式被熟知为琴生不等式(Jensen’s inequality),事实上,所有这四个方程式有时都被称为琴生不等式,因为它们都是等价的。

水平子集

凸函数可以产生一种尤其重要的凸集类型,被称为 $\alpha$-水平子集($\alpha$-sublevel set). 给定凸函数 $f : \mathbb{R}^{n} \rightarrow R$ 与实数 $\alpha \in \mathbb{R}$, $\alpha$-水平子集定义为

换句话说,$\alpha$-水平子集是所有满足 $f(x) \leq \alpha$ 的点 $x$ 的集合。为了证明这是一个凸集,考虑任意 $x, y \in \mathcal{D}(f)$ 满足 $f(x) \leq \alpha$ 与 $f(y) \leq \alpha$. 则有

凸函数举例

我们从单变量凸函数的一些简单示例开始,然后转到多变量函数。

  • 指数函数。令 $f : \mathbb{R} \rightarrow \mathbb{R}$, 对任意 $a \in \mathbb{R}$. 为了证明函数 $f$ 是凸的,我们可以简要地记二阶导数为 $f^{\prime \prime}(x)=a^{2} e^{a x}$, 对所有的 $x$ 都为正。
  • 负对数函数。令 $f : \mathbb{R} \rightarrow \mathbb{R}, f(x)=-\log x$ 且定义域 $\mathcal{D}(f)=\mathbb{R}_{++}$ (此处的 $\mathbb{R}_{++}$ 表示集合中为严格正实数,即 $\{x : x>0\}$). 则对所有 $x$, 有 $f^{\prime \prime}(x)=1 / x^{2} >0$.
  • 仿射函数。令 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}, f(x)=b^{T} x+c$, 对某些 $b \in \mathbb{R}^{n}, c \in \mathbb{R}$. 在这种情况下,对所有的 $x$, 有 Hessian $\nabla_{x}^{2} f(x)=0$. 由于零矩阵既是半正定又是半负定的,此时 $f$ 既是凸的也是凹的。实际上,这种形式的仿射函数是唯一既凸又凹的函数。
  • 二次函数。令 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}, f(x)=\frac{1}{2} x^{T} A x+b^{T} x+c$, 对对称矩阵 $A \in \mathbb{S}^{n}, b \in \mathbb{R}^{n}$ 和 $c \in \mathbb{R}$. 根据线性代数知识可知函数的 Hessian 为 $\nabla_{x}^{2} f(x)=A$. 因此 $f$ 凸或非凸完全取决于 $A$ 是否是半正定的:如果 $A$ 是半正定的则函数为凸(类似地也可以决定严格凸、凹与严格凹);如果 $A$ 是不定的,则 $f$ 既不是凹也不是凸的。注意欧几里得范数的平方 $f(x)=\|x\|_{2}^{2}=x^{T} x$ 是二次函数的一种特例,其中 $A=I, b=0, c=0$, 因此也是一个严格凸函数。
  • 范数。令 $f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 表示在 $\mathbb{R}^{n}$ 上的范数。由范数的三角不等式和正同质性,有对 $x, y \in \mathbb{R}^{n}, 0 \leq \theta \leq 1$,

    这是无法基于二阶或一阶条件去证明凸性的凸函数的例子,因为范数并不是处处可微(例如 $1$ 范数,$\|x\|_{1}=\sum_{i=1}^{n}$ 在任意 $x_i=0$ 点处都不可微).

  • 凸函数的非负加权求和。令 $f_{1}, f_{2}, \dots, f_{k}$ 为凸函数且 $u_{1}, w_{2}, \dots, \dots, w_{k}$ 为非负实数,则有凸函数 $f(x)=\sum_{i=1}^{k} w_{i} f_{i}(x)$. 因为

凸优化问题

有了前面对凸集和凸函数的定义,现在可以考虑凸优化问题了。正式地讲,凸优化问题是优化问题的一种形式

其中 $f$ 是凸函数,$C$ 是凸集,以及 $x$ 是优化的变量。然而由于这种形式比较模糊,我们经常写作

其中 $f$ 是凸函数,$g_{i}(x)$ 是凸函数,$h_{i}(x)$ 是仿射函数,以及 $x$ 是优化的变量。

注意这些不等式的方向很重要:凸函数 $g_{i}(x)$ 必须小于零。这是因为 $g_{i}(x)$ 的 $0$-水平子集是一个凸集,因此得到的可行域是多个凸集的交集,也是凸集(回想一下仿射子空间也是凸集). 如果我们要求某些凸函数 $g_i$ 的不等式为 $g_i \geq 0$, 那么可行域将不再是一个凸集,我们用来求解这些问题的算法也不再保证能找到全局最优解。而且还要注意,只有仿射函数才允许为等式约束。直觉上来说,你可以认为一个等式约束 $h_i= 0$ 等价于两个不等式约束 $h_i \leq 0$ 和 $h_i \geq 0$. 然而,当且仅当 $h_i$ 同时为凸函数和凹函数时(即仿射函数),这两个约束条件才都是有效的。

优化问题的最优值表示成 $p^\ast$ (有时表示为 $f^\ast$), 等于目标函数在可行域内的最小可能值。数学专业的学生可能会注意到,下面出现的最小值更应该用符号$\text{inf}$. 这里我们不需要担心这些技术问题,为了简单起见,我们使用符号$\text{min}$.

当问题不可行(即可行域为空) 或无下界(即存在可行点使得 $f(x)\rightarrow -\infty$) 时,我们允许 $p^\ast$ 取值为 $+\infty$ 和 $-\infty$. 当 $f(x^\ast)=p^\ast$ 时,我们称 $x^\ast$ 是一个最优点。注意,即使最优值是有限的,也可以有多个最优点。

凸问题的全局最优性

在讲解凸问题的全局最优性之前,让我们正式定义局部最优和全局最优的概念。直观地说,如果一个可行点“附近”没有令该函数目标值更低的点,则该可行点被称为局部最优。类似地,如果全局都找不到使目标值更低的可行点,则该可行点称为全局最优。为了更加形式化,我们给出了以下两个定义。

  • 如果在可行域(即满足优化问题的约束条件) 内存在某些 $R > 0$,使满足 $\|x-z\|_{2} \leq R$ 的所有可行点 $z$ 有 $f(x) \leq f(z)$,则我们称点 $x$ 是局部最优的。
  • 如果在可行域所有可行点 $z$, 都满足$ f(x) \leq f(z)$, 则我们称点 $x$ 是全局最优的。

现在我们来讨论凸优化问题的关键元素,它们的大部作用都来自于此。其核心思想是:对于一个凸优化问题,所有局部最优点都是全局最优的。

让我们用反证法来快速证明这个性质。假设 $x$ 是局部最优点而不是全局最优点,即存在这样一个可行点 $y$ 使得 $f(x)>f(y)$. 根据局部最优性的定义,不存在$\|x-z\|_{2} \leq R$ 和 $f(z) < f(x)$ 的可行点 $z$. 现在假设我们选择这个点

则:

另外,通过 $f$ 的凸性,我们可得:

此外,由于可行域的集合是凸集,同时 $x$ 和 $y$ 都是可行的,因此 $z =\theta y +(1-\theta)$ 也会是可行的。因此,$z$ 是一个可行点,满足 $\|x-z\|_{2} \leq R$ 以及 $f(z) < f(x)$. 这与我们的假设相矛盾,表明 $x$ 不可能是局部最优的。

凸问题的特殊情况

由于各种原因,考虑常见凸优化公式的特殊情况通常会比较方便。对于这些特殊情况,我们通常可以设计出非常高效的算法来解决非常大规模的问题,正因为如此,当人们使用凸优化技术时,你可能会看到这些特殊情况。

  • 线性规划(LP). 如果目标函数 $f$ 和不等式约束 $g_i$ 都是仿射函数,那么凸优化问题就是一个线性规划问题。换句话说,这些问题都有如下形式:

    其中,$x \in \mathbb{R}^{n}$ 是优化变量,$c \in \mathbb{R}^{n}$, $ d \in \mathbb{R}$, $ G \in \mathbb{R}^{m \times n}$, $ h \in \mathbb{R}^{m}$, $A \in \mathbb{R}^{p \times n}$, $ b \in \mathbb{R}^{p}$ 这些变量由问题定义,符号 $\preceq$ 代表元素间不相等。

  • 二次规划(QP). 如果不等式约束 $g_i$ (跟线性规划) 一样是仿射的,而目标函数 $f$ 是凸二次函数,则凸优化问题是一个二次规划问题。换句话说,这些问题都有如下形式:

    其中,$x \in \mathbb{R}^{n}$ 是优化变量,$c \in \mathbb{R}^{n}$, $ d \in \mathbb{R}$, $ G \in \mathbb{R}^{m \times n}$, $ h \in \mathbb{R}^{m}$, $A \in \mathbb{R}^{p \times n}$, $ b \in \mathbb{R}^{p}$ 这些变量由问题定义,但我们也有一个对称半正定矩阵 $P \in \mathbb{S}_{+}^{n}$.

  • 二次约束二次规划(QCQP) . 如果目标函数 $f$ 和不等式约束条件 $g_i$ 都是凸二次函数,那么凸优化问题就是一个二次约束二次规划问题,形式如下:

    跟二次规划一样,其中 $x\in R^n$ 是优化变量,$c \in \mathbb{R}^{n}$, $ d \in \mathbb{R}$, $ A \in \mathbb{R}^{p \times n}$, $ b \in \mathbb{R}^{p}$, $P \in \mathbb{S}_{+}^{n}$, 但对 $i=1, \ldots, m$ 同时也有 $Q_{i} \in \mathbb{S}_{+}^{n}$, $ r_{i} \in \mathbb{R}^{n}$, $ s_{i} \in \mathbb{R}$.

  • 半定规划(SDP) . 最后一个举例比前面更复杂,所以如果不太理解也不要担心。但是,半定规划在机器学习许多领域的研究中正变得越来越流行,所以你可能在以后的某个时候会遇到这些问题,所以提前了解半定规划的内容还是比较好的。如果我们说一个凸优化问题是半定规划的,则其形式如下所示:

    其中对称矩阵 $X\in S^n$ 是优化变量,对称矩阵 $C,A_1,\cdots,A_p\in S^n$ 由问题定义,约束 $X\succeq 0$ 意味着 $X$ 是一个半正定矩阵。以上这些看起来和我们之前看到的问题有点不同,因为优化变量现在是一个矩阵而不是向量。如果你好奇为什么这样的公式可能有用,你应该看看更高级的课程或关于凸优化的书。

从定义可以明显看出,二次规划比线性规划更具有一般性(因为线性规划只是 $P = 0$ 时的二次规划的特殊情况). 同样地,二次约束二次规划比二次规划更具有一般性。然而,半定规划实际上比之前的所有类型都更具一般性质,也就是说,任何二次约束二次规划(以及任何二次规划或线性规划) 都可以表示为半定规划。在本文当中,我们不会进一步讨论这种关系,但是这个结论可能会让你对半定规划为何有用有一个小小的概念。

凸优化问题举例

到目前为止,我们已经讨论了凸优化背后大量枯燥的数学以及形式化的定义。接下来,我们终于可以进入有趣的部分:使用这些技术来解决实际问题。我们在课堂上已经遇到过一些这样的优化问题,而且几乎在每个领域,都有很多情况需要人们应用凸优化来解决一些问题。(这一部分需要一些机器学习的前置知识)

  • 支持向量机(SVM). 凸优化方法在机器学习中最普遍的应用之一是支持向量机分类器。支持向量分类器(在松弛变量的情况下) 可以被公式化为优化问题

    优化变量为 $w \in \mathbb{R}^{n}$, $ \xi \in \mathbb{R}^{m}$, $ b \in \mathbb{R}$, 其中 $C \in \mathbb{R}$ 和 $x^{(i)}, y^{(i)}, i=1,\ldots,m$ 由问题定义。这是二次规划的一种例子,将问题置于上一节中描述的形式来展示,特别是如果定义 $k=m+n+1$, 令优化变量为

    并定义矩阵

    其中 $I$ 为单位矩阵,$\mathbf 1$ 是全由 $1$ 组成的向量,$X$ 和 $y$ 定义为

    你可以发现当使用上面定义的这些矩阵时,上述的二次规划形式,等同于 SVM 优化问题。 实际上,很容易看出 SVM 优化问题存在二次目标和线性约束,因此我们通常不需要将其置于标准形式以 “证明” 它是 QP. 如果使用现成的求解器,要求输入为标准形式,我们才会这样做。

  • 约束最小二乘。在讨论最小二乘问题时,对于矩阵 $A \in \mathbb{R}^{m \times n}$ 与 $b \in \mathbb{R}^{m}$ 想要使 $\|A x-b\|_{2}^{2}$ 最小,这个特殊问题可以通过解正规方程搞定。但假设我们还希望将解 $x$ 中的元素限制在某些预定义范围——换句话说,假设我们想要解决优化问题,

    优化变量为 $x$, 问题数据为 $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^{m}$, $ l \in \mathbb{R}^{n}$ 和 $u \in \mathbb{R}^{n}$. 这似乎是一个简单的附加约束,但事实证明不能用老办法获得解析解。 但你应该认为这个优化问题是一个二次规划,矩阵定义为

  • Logistic 回归最大似然。如果要证明逻辑模型中数据的对数似然是凹的,这种模型下的对数似然为

    其中 $g(z)$ 表示 logistic 函数 $g(z)=1 /\left(1+e^{-z}\right)$. 找到最大似然估计即最大化对数似然(或等同于最小化负对数似然 $-\ell(\theta)$, 是一个凸函数). 优化变量为 $\theta \in \mathbb{R}^{n}$, 没有约束条件。

    与前面两个例子不同,要将这个问题转换成优化问题的“标准”形式并不容易。但 $\ell$ 是一个凹函数意味着可以使用类似牛顿法的算法高效地找到全局最优解。

拉格朗日对偶

通常来说,拉格朗日对偶理论是关于凸优化问题最优解的研究。正如我们前面看到的,当最小化一个可微的凸函数 $f(x)$ 满足 $x \in \mathbb{R}^{n}$ 时,使 $x^{\ast} \in \mathbb{R}^{n}$ 全局最优的一个必要且关键的条件是 $\nabla_{x} f\left(x^{\ast}\right)=0$. 然而,对于常见的带约束的凸优化问题,这种简单的最优条件并不成立。对偶理论的一个主要目的是以严谨的数学方式表示凸优化的最优点。在接下来的内容中,我要介绍了拉格朗日对偶及其在常见可微凸优化问题中的应用。

其中 $x \in \mathbb{R}^{n}$ 是优化变量,$f : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 和 $g_i: \mathbb{R}^{n} \rightarrow \mathbb{R}$ 是可微凸函数,以及 $h_{i} : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 是凸函数。

这里回想一下,如果 $S$ 是一个凸集,则 $f : S \rightarrow \mathbb{R}$ 是凸的,以及对任意 $x, y \in S$ 和 $\theta \in[0,1]$, 我们有 $f(\theta x+(1-\theta) y) \leq \theta f(x)+(1-\theta) f(y)$. 如果 $-f$ 是凸函数,则 $f$ 是凹函数。仿射函数是形如 $f(x)=a^{T} x+b$ 的函数,对某些 $a \in \mathbb{R}^{n}, b \in \mathbb{R}$. 由于仿射函数的 Hessian 矩阵等同于零矩阵(既是半正定也是半负定的), 因此仿射函数既是凸的也是凹的。

拉格朗日函数

在本节中,我们介绍一种称为“拉格朗日函数”的人为外形构造,它是拉格朗日对偶理论的基础。给定问题的凸约束最小化形式(OPT), (广义) 拉格朗日函数是 $\mathcal{L} : \mathbb{R}^{n} \times \mathbb{R}^{m} \times \mathbb{R}^{p} \rightarrow \mathbb{R}$ 定义为

上式中,拉格朗日公式中的第一个参数是向量 $x \in \mathbb{R}^{n}$, 其维度与原优化问题中的优化变量对应;按照惯例,我们将 $x$ 称为拉格朗日的原始变量。公式中的第二个参数是向量 $\alpha \in \mathbb{R}^{m}$, 每个变量 $\alpha_{i}$ 分别与原优化问题中 $m$ 个凸不等式约束对应。公式中的第三个参数是向量 $\beta \in \mathbb{R}^{p}$, 每个变量 $\beta_{i}$ 分别与原优化问题中 $p$ 个仿射等式约束对应。这些 $\alpha$ 与 $\beta$ 中的元素统称为对偶变量或拉格朗日乘子。

直观上看,拉格朗日函数可以被认为是原优化问题(OPT) 目标函数的一个修改版本,解释了每个约束。拉格朗日乘子 $\alpha_{i}$ 和 $\beta_{i}$ 可以被认为是与违背不同约束所关联的“代价”。拉格朗日对偶理论的关键直觉如下:

对于任何凸优化问题,总是存在对偶变量,使得拉格朗日函数关于原始变量的无约束最小值(保持对偶变量固定) 与原约束最小化问题的解一致。

在后面描述 KKT 条件时,我们会给出这一直觉理解的形式化描述。

原始与对偶问题

为了体现拉格朗日函数与原凸优化问题(OPT) 之间的关系,我们介绍关于拉格朗日函数的“原始”与“对偶”的概念。

原始问题:考虑优化问题 P,

在上面的式子中,函数 $\theta_{\mathcal{P}} : \mathbb{R}^{n} \rightarrow \mathbb{R}$ 被称为原始目标,右边的无约束最小化问题被称为原始问题。通常我们认为如果 $g_{i}(x) \leq 0, i=1, \ldots, m$ 且 $h_{i}(x)=0, i=1, \dots, p$, 则点 $x \in \mathbb{R}^{n}$ 原始可行。我们通常使用向量 $x^{\ast} \in \mathbb{R}^{n}$ 表示 (P) 的解,并令 $p^{\ast}=\theta_{\mathcal{P}}\left(x^{\ast}\right)$ 表示原始目标的最优值。

对偶问题:通过转换上式中最小化和最大化的顺序,我们得到了一个完全不同的优化问题 D,

这里的函数 $\theta_{\mathcal{D}} : \mathbb{R}^{m} \times \mathbb{R}^{p} \rightarrow \mathbb{R}$ 被称为对偶目标,右边的约束最大化问题被称为对偶问题。通常我们认为如果 $\alpha_{i} \geq 0, i=1, \ldots, m$, 则 $(\alpha, \beta)$ 对偶可行。我们通常使用向量对 $\left(\alpha^{\ast}, \beta^{\ast}\right) \in \mathbb{R}^{m} \times \mathbb{R}^{p}$ 表示 (D) 的解,并令 $d^{\ast}=\theta_{\mathcal{D}}\left(\alpha^{\ast}, \beta^{\ast}\right)$ 表示对偶目标的最优值。

原始问题解释

首先观察原始目标函数 $\theta_{\mathcal{P}}(x)$, 是一个关于 $x$ 的凸函数。这是因为

注意到 $g_{i}(x)$ 中的每一个都是关于 $x$ 的凸函数,且由于 $\alpha_{i}$ 被约束为非负值,则有对每个 $i$ 有 $\alpha_{i} g_{i}(x)$ 是关于 $x$ 的凸函数。类似地,由于 $h_{i}(x)$ 是线性的,每个 $\beta_{i} h_{i}(x)$ 都是关于 $x$ 的凸函数(不用去管 $\beta_{i}$ 的符号). 由于凸函数的求和也是凸函数,我们可以知道括号内的量是关于 $x$ 的凸函数。最终,凸函数集合取最大值也是一个凸函数(请自行证明), 因此我们可以得到结论 $\theta_{\mathcal{P}}(x)$ 是一个关于 $x$ 的凸函数。

为了解释原始问题,注意有

最终发现 $f(x)$ 不取决于 $\alpha$ 与 $\beta$. 仅考虑括号内的项,注意有

  • 如果任意 $g_{i}(x)>0$, 则最大化括号内表达式包括使对应的 $\alpha_{i}$ 成为尽可能大的正数;然而如果 $g_{i}(x) \leq 0$, 则要求 $\alpha_{i}$ 非负意味着 $\alpha_{i}$ 达到最大的最优设置是 $\alpha_{i}=0$, 因此最大值为 $0$.
  • 类似地,如果任意 $h_{i}(x) \neq 0$, 则最大化括号内表达式包括选择对应与 $h_{i}(x)$ 具有相同符号的 $\beta_{i}$ ,且尽可能使之最大化;然而如果 $h_{i}(x) = 0$, 则最大值为 $0$, 与 $\beta_{i}$ 无关。

同时考虑以上两种情况,我们发现如果 $x$ 原始可行(即 $g_{i}(x) \leq 0, i= 1,\ldots ,m$ 且 $h_{i}(x)=0, i=1, \ldots, p$), 则括号中表达式的最大值为 $0$, 但如果任意约束被违背,最大值将为 $\infty$. 据此我们可以写出,

因此,我们可以将原始目标函数 $\theta_{\mathcal{P}}(x)$ 解释为原问题(OPT) 优化目标函数的修改版本,区别在于不可行解(即违背约束的某些 $x$) 具有目标值 $\infty$. 直观地看,

可以将其看为一种“阻碍”函数,阻止我们将不可行点看作是优化问题的候选解。

对偶问题解释

对偶目标函数 $\theta_{\mathcal{D}}(\alpha, \beta)$ 是关于 $\alpha$ 和 $\beta$ 的凹函数,证明与原始目标函数类似,

观察到对任意固定的 $x$ 值,括号内的量是一个关于 $\alpha$ 和 $\beta$ 的仿射函数,因此为凹。由于凹函数集合取最小依旧是凹的,因此可以认为 $\theta_{\mathcal{D}}(\alpha, \beta)$ 是关于 $\alpha$ 和 $\beta$ 的凹函数。

为了解释对偶问题,首先要有以下信息:

引理 1:如果 $(\alpha, \beta)$ 对偶可行,则 $\theta_{\mathcal{D}}(\alpha, \beta) \leq p^{\ast}$

证明如下,

上式第一和第三步的推导直接由对偶目标函数和拉格朗日函数的定义可得。第二步推导表示前一个表达式最小化了 $x$ 可能的值。最后一步表示 $x^\ast$ 原始可行,$(\alpha, \beta)$ 对偶可行,因此根据原始问题解释中最后的公式可知,求和式子中后面两项必须是非正的。

该引理证明了给定任意对偶可行基 $(\alpha, \beta)$, 对偶目标函数 $\theta_{\mathcal{D}}(\alpha, \beta)$ 提供了原始问题中最优值 $p^\ast$ 的下界。由于对偶问题中在所有对偶可行基 $(\alpha, \beta)$ 的空间上最大化对偶变量,由此可认为对偶问题是对 $p^\ast$ 的最严格可能下界的搜索。由此产生的任意原始与对偶优化问题对的属性被称为弱对偶性:

引理 2(弱对偶). 对任意原始与对偶问题对,$d^{\ast} \leq p^{\ast}$.

显然,弱对偶性是引理 1 使用 $\left(\alpha^{\ast}, \beta^{\ast}\right)$ 作为对偶可行基的结果。对一些原始/对偶优化问题,甚至有更强的结论,被称为强对偶性:

引理 3(强对偶). 对于满足约束规范(constraint qualifications) 的任意原始/对偶问题对,$d^{\ast} = p^{\ast}$.

“约束规范”有许多种,最常被使用的被称为 Slater 条件:如果存在一些可行原始解 $x$ 严格满足所有的不等式约束(即 $g_{i}(x)<0, i=1, \ldots, m$), 则这对原始/对偶问题满足 Slater 条件。在实践中,几乎所有凸问题都满足某种约束规范,因此原始问题和对偶问题具有相同的最优值。

互补松弛

凸优化问题的强对偶性的一个特别有趣的性质是互补松弛(或 KKT 互补性) :

引理 4(互补松弛). 如果强对偶性成立,那么对每个 $i=1, \ldots, m$, 有 $\alpha_{i}^{\ast} g\left(x_{i}^{\ast}\right)=0$.

证明如下,假设强对偶性成立,根据上一节中证明有

由于第一个与最后一个表达式相等,可以表明所有中间变形也是相等的,因此可以发现

然而需要注意,每个 $\alpha_{i}^{\ast}$ 是非负的,每个 $g_{i}\left(x^{\ast}\right)$ 是非正的,每个 $h_{i}\left(x^{\ast}\right)$ 为零分别取决于原始与对偶可行基 $\mathcal{X}^{\ast}$ 和 $\left(\alpha^{\ast}, \beta^{\ast}\right)$. 因此上式是所有非正项的综合且结果为 $0$, 据此很容易得出求和公式中每个项必须为 $0$ (如果不是这样,则没有进行补充的正项来保持总和为 $0$).

互补松弛可以用许多等价的方式写出来,特别是这对条件

在这种形式中,我们可以看到,只要任何 $\alpha_{i}^{\ast}$ 严格大于零,则意味着相应的不等式约束必须保持相等。我们将此称为起作用约束(active constraint). 在支持向量机(SVM) 的情况下,起作用约束也称为支持向量。

KKT 条件

最后,根据目前为止所有内容,现在可以表征原始对偶优化对的最佳情况。我们有以下定理:

设 $x^{\ast} \in \mathbb{R}^{n}$, $\alpha^{\ast} \in \mathbb{R}^{m}$, $\beta^{\ast} \in \mathbb{R}^{p}$ 满足以下条件:

  1. (原始可行) $g_{i}\left(x^{\ast}\right) \leq 0, i=1, \ldots, m$ 与 $h_{i}\left(x^{\ast}\right)=0, i=1, \dots, p$
  2. (对偶可行) $\alpha_{i}^{\ast} \geq 0, i=1, \ldots, m$
  3. (互补松弛) $\alpha_{i}^{\ast} g_{i}\left(x^{\ast}\right)=0, i=1, \dots, m$
  4. (拉格朗日平稳) $\nabla_{x} \mathcal{L}\left(x^{\ast}, \alpha^{\ast}, \beta^{\ast}\right)=0$

则 $x^{\ast}$ 为原始最优,$\left(\alpha^{\ast}, \beta^{\ast}\right)$ 为对偶最优。如果强对偶性成立,则任意原始最优 $x^{\ast}$ 和对偶最优 $\left(\alpha^{\ast}, \beta^{\ast}\right)$ 必须满足条件 1 和 4.

这些条件被称为 Karush-Kuhn-Tucker(KKT) 条件。