12.2. 凸性¶ 在 SageMaker Studio Lab 中打开 Notebook
凸性（Convexity）在优化算法的设计中扮演着重要的角色。这在很大程度上是由于在这种情况下对算法进行分析和测试要容易得多。换言之，如果算法在凸性情况下的效果很差，那通常我们很难期望它在其他情况下会有很好的效果。此外，尽管深度学习中的优化问题通常是非凸的，但它们在局部极小值附近时表现出一些凸函数的性质。这催生了优化算法的令人兴奋的新变体，例如 (Izmailov et al., 2018)。
%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l
%matplotlib inline
from mpl_toolkits import mplot3d
from mxnet import np, npx
from d2l import mxnet as d2l
npx.set_np()
%matplotlib inline
import numpy as np
import tensorflow as tf
from mpl_toolkits import mplot3d
from d2l import tensorflow as d2l
12.2.1. 定义¶
在进行凸分析之前，我们需要定义凸集（convex sets）和凸函数（convex functions）。它们引出了常用于机器学习的数学工具。
12.2.1.1. 凸集¶
集合是凸性的基础。简而言之，如果对于向量空间中的任意 \(a, b \in \mathcal{X}\)，连接 \(a\) 和 \(b\) 的线段也位于 \(\mathcal{X}\) 中，则该集合 \(\mathcal{X}\) 是凸（convex）的。在数学术语中，这意味着对于所有 \(\lambda \in [0, 1]\)，我们有
这听起来有点抽象。请看 图 12.2.1。第一个集合不是凸的，因为它存在不包含在集合内部的线段。另外两个集合则没有这样的问题。
图 12.2.1 第一个集合是非凸的，另外两个是凸的。¶
除非我们能对定义做一些有用的事情，否则定义本身并没有什么用。在这种情况下，我们可以看看 图 12.2.2 所示的交集。假设 \(\mathcal{X}\) 和 \(\mathcal{Y}\) 是凸集，那么 \(\mathcal{X} \cap \mathcal{Y}\) 也是凸的。为了证明这一点，考虑任意 \(a, b \in \mathcal{X} \cap \mathcal{Y}\)。因为 \(\mathcal{X}\) 和 \(\mathcal{Y}\) 是凸的，所以连接 \(a\) 和 \(b\) 的线段同时包含在 \(\mathcal{X}\) 和 \(\mathcal{Y}\) 中。因此，它们也需要被包含在 \(\mathcal{X} \cap \mathcal{Y}\) 中，从而证明了我们的定理。
图 12.2.2 两个凸集的交集是凸的。¶
我们可以毫不费力地加强这个结果：给定凸集 \(\mathcal{X}_i\)，它们的交集 \(\cap_{i} \mathcal{X}_i\) 是凸的。要看到逆命题是不成立的，考虑两个不相交的集合 \(\mathcal{X} \cap \mathcal{Y} = \emptyset\)。现在选择 \(a \in \mathcal{X}\) 和 \(b \in \mathcal{Y}\)。在 图 12.2.3 中连接 \(a\) 和 \(b\) 的线段需要包含既不在 \(\mathcal{X}\) 中也不在 \(\mathcal{Y}\) 中的部分，因为我们假设 \(\mathcal{X} \cap \mathcal{Y} = \emptyset\)。因此该线段也不在 \(\mathcal{X} \cup \mathcal{Y}\) 中，从而证明了凸集的并集通常不一定是凸的。
图 12.2.3 两个凸集的并集不一定是凸的。¶
深度学习中的问题通常是在凸集上定义的。例如，\(\mathbb{R}^d\)，即实数的 \(d\) 维向量的集合，是一个凸集（毕竟，\(\mathbb{R}^d\) 中任意两点之间的线段仍然在 \(\mathbb{R}^d\) 中）。在某些情况下，我们使用有界长度的变量，例如半径为 \(r\) 的球，其定义为 \(\{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \textrm{ and } \|\mathbf{x}\| \leq r\}\)。
12.2.1.2. 凸函数¶
既然我们有了凸集，我们就可以引入凸函数 \(f\)。给定一个凸集 \(\mathcal{X}\)，函数 \(f: \mathcal{X} \to \mathbb{R}\) 是凸的，如果对于所有的 \(x, x' \in \mathcal{X}\) 和所有的 \(\lambda \in [0, 1]\)，我们有
为了说明这一点，让我们绘制一些函数并检查哪些函数满足要求。下面我们定义了一些函数，包括凸函数和非凸函数。
f = lambda x: 0.5 * x**2 # Convex
g = lambda x: torch.cos(np.pi * x) # Nonconvex
h = lambda x: torch.exp(0.5 * x) # Convex
x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
d2l.plot([x, segment], [func(x), func(segment)], axes=ax)
f = lambda x: 0.5 * x**2 # Convex
g = lambda x: np.cos(np.pi * x) # Nonconvex
h = lambda x: np.exp(0.5 * x) # Convex
x, segment = np.arange(-2, 2, 0.01), np.array([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
d2l.plot([x, segment], [func(x), func(segment)], axes=ax)
[21:56:20] ../src/storage/storage.cc:196: Using Pooled (Naive) StorageManager for CPU
f = lambda x: 0.5 * x**2 # Convex
g = lambda x: tf.cos(np.pi * x) # Nonconvex
h = lambda x: tf.exp(0.5 * x) # Convex
x, segment = tf.range(-2, 2, 0.01), tf.constant([-1.5, 1])
d2l.use_svg_display()
_, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
for ax, func in zip(axes, [f, g, h]):
d2l.plot([x, segment], [func(x), func(segment)], axes=ax)
不出所料，余弦函数是非凸的，而抛物线和指数函数是凸的。请注意，\(\mathcal{X}\) 是一个凸集的要求对于使条件有意义是必要的。否则 \(f(\lambda x + (1-\lambda) x')\) 的结果可能没有很好的定义。
12.2.1.3. 詹森不等式¶
给定一个凸函数 \(f\)，最有用的数学工具之一是詹森不等式（Jensen's inequality）。它相当于凸性定义的一般化：
其中 \(\alpha_i\) 是非负实数，使得 \(\sum_i \alpha_i = 1\)，\(X\) 是一个随机变量。换句话说，凸函数的期望不小于期望的凸函数，其中后者通常是一个更简单的表达式。为了证明第一个不等式，我们一次对总和中的一项重复应用凸性的定义。
詹森不等式的一个常见应用是用一个更简单的表达式来约束一个更复杂的表达式。例如，它可以应用于部分观测到的随机变量的对数似然。也就是说，我们使用
因为 \(\int P(Y) P(X \mid Y) dY = P(X)\)。这可以用在变分方法中。这里 \(Y\) 通常是未观测到的随机变量，\(P(Y)\) 是它可能如何分布的最佳猜测，\(P(X)\) 是将 \(Y\) 积分掉的分布。例如，在聚类中，\(Y\) 可能是簇标签，而 \(P(X \mid Y)\) 是应用簇标签时的生成模型。
12.2.2. 性质¶
凸函数有许多有用的性质。下面我们描述一些常用的性质。
12.2.2.1. 局部极小值是全局极小值¶
首先，凸函数的局部极小值也是全局极小值。我们可以用反证法来证明它，如下所示。
考虑一个定义在凸集 \(\mathcal{X}\) 上的凸函数 \(f\)。假设 \(x^{\ast} \in \mathcal{X}\) 是一个局部极小值：存在一个小的正值 \(p\)，使得对于满足 \(0 < |x - x^{\ast}| \leq p\) 的 \(x \in \mathcal{X}\)，我们有 \(f(x^{\ast}) < f(x)\)。
假设局部极小值 \(x^{\ast}\) 不是 \(f\) 的全局极小值：存在一个 \(x' \in \mathcal{X}\)，使得 \(f(x') < f(x^{\ast})\)。还存在 \(\lambda \in [0, 1)\)，例如 \(\lambda = 1 - \frac{p}{|x^{\ast} - x'|}\)，使得 \(0 < |\lambda x^{\ast} + (1-\lambda) x' - x^{\ast}| \leq p\)。
然而，根据凸函数的定义，我们有
这与我们关于 \(x^{\ast}\) 是一个局部极小值的说法相矛盾。因此，不存在 \(x' \in \mathcal{X}\) 使得 \(f(x') < f(x^{\ast})\)。局部极小值 \(x^{\ast}\) 也是全局极小值。
例如，凸函数 \(f(x) = (x-1)^2\) 在 \(x=1\) 处有一个局部极小值，这也是全局极小值。
f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')
f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')
f = lambda x: (x - 1) ** 2
d2l.set_figsize()
d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')
凸函数的局部极小值也是全局极小值，这个事实非常方便。这意味着如果我们最小化函数，我们不会“卡住”。但请注意，这并不意味着不可能有多个全局极小值，或者甚至可能不存在全局极小值。例如，函数 \(f(x) = \mathrm{max}(|x|-1, 0)\) 在区间 \([-1, 1]\) 上达到其最小值。相反，函数 \(f(x) = \exp(x)\) 在 \(\mathbb{R}\) 上没有达到最小值：当 \(x \to -\infty\) 时，它渐近于 \(0\)，但不存在 \(x\) 使得 \(f(x) = 0\)。
12.2.2.2. 凸函数的下方集是凸的¶
我们可以方便地通过凸函数的下方集来定义凸集。具体来说，给定一个定义在凸集 \(\mathcal{X}\) 上的凸函数 \(f\)，任何下方集
都是凸的。
让我们快速证明这一点。回想一下，对于任何 \(x, x' \in \mathcal{S}_b\)，只要 \(\lambda \in [0, 1]\)，我们就需要证明 \(\lambda x + (1-\lambda) x' \in \mathcal{S}_b\)。由于 \(f(x) \leq b\) 和 \(f(x') \leq b\)，根据凸性的定义，我们有
12.2.2.3. 凸性与二阶导数¶
只要函数 \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) 的二阶导数存在，就很容易检验 \(f\) 是否是凸的。我们只需要检查 \(f\) 的Hessian矩阵是否是半正定的：\(\nabla^2f \succeq 0\)，即，将Hessian矩阵 \(\nabla^2f\) 表示为 \(\mathbf{H}\)，对于所有 \(\mathbf{x} \in \mathbb{R}^n\)，\(\mathbf{x}^\top \mathbf{H} \mathbf{x} \geq 0\)。例如，函数 \(f(\mathbf{x}) = \frac{1}{2} \|\mathbf{x}\|^2\) 是凸的，因为 \(\nabla^2 f = \mathbf{1}\)，即它的Hessian矩阵是一个单位矩阵。
形式上，一个二次可微的一维函数 \(f: \mathbb{R} \rightarrow \mathbb{R}\) 是凸的，当且仅当它的二阶导数 \(f'' \geq 0\)。对于任何二次可微的多维函数 \(f: \mathbb{R}^{n} \rightarrow \mathbb{R}\)，它是凸的，当且仅当它的Hessian矩阵 \(\nabla^2f \succeq 0\)。
首先，我们需要证明一维的情况。为了证明 \(f\) 的凸性意味着 \(f'' \geq 0\)，我们使用以下事实：
因为二阶导数是由有限差分的极限给出的，所以可以得出
为了证明 \(f'' \geq 0\) 意味着 \(f\) 是凸的，我们使用 \(f'' \geq 0\) 意味着 \(f'\) 是一个单调不减函数这一事实。设 \(a < x < b\) 是 \(\mathbb{R}\) 中的三个点，其中 \(x = (1-\lambda)a + \lambda b\) 且 \(\lambda \in (0, 1)\)。根据中值定理，存在 \(\alpha \in [a, x]\) 和 \(\beta \in [x, b]\) 使得
根据单调性 \(f'(\beta) \geq f'(\alpha)\)，因此
因为 \(x = (1-\lambda)a + \lambda b\)，我们有
从而证明了凸性。
其次，在证明多维情况之前，我们需要一个引理：\(f: \mathbb{R}^n \rightarrow \mathbb{R}\) 是凸的，当且仅当对于所有 \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\)
都是凸的。
为了证明 \(f\) 的凸性意味着 \(g\) 是凸的，我们可以证明对于所有 \(a, b, \lambda \in [0, 1]\) (因此 \(0 \leq \lambda a + (1-\lambda) b \leq 1\))
为了证明逆命题，我们可以证明对于所有 \(\lambda \in [0, 1]\)
最后，利用上面的引理和一维情况的结果，可以证明多维情况如下。一个多维函数 \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) 是凸的，当且仅当对于所有 \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\)，\(g(z) \stackrel{\textrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y})\)（其中 \(z \in [0,1]\)）是凸的。根据一维情况，这成立当且仅当 \(g'' = (\mathbf{x} - \mathbf{y})^\top \mathbf{H}(\mathbf{x} - \mathbf{y}) \geq 0\)（其中 \(\mathbf{H} \stackrel{\textrm{def}}{=} \nabla^2f\)）对于所有 \(\mathbf{x}, \mathbf{y} \in \mathbb{R}^n\)，根据半正定矩阵的定义，这等价于 \(\mathbf{H} \succeq 0\)。
12.2.3. 约束¶
凸优化的一个很好的特性是它允许我们有效地处理约束。也就是说，它允许我们解决以下形式的约束优化问题
其中 \(f\) 是目标函数，函数 \(c_i\) 是约束函数。为了了解这是做什么的，考虑 \(c_1(\mathbf{x}) = \|\mathbf{x}\|_2 - 1\) 的情况。在这种情况下，参数 \(\mathbf{x}\) 被限制在单位球内。如果第二个约束是 \(c_2(\mathbf{x}) = \mathbf{v}^\top \mathbf{x} + b\)，那么这对应于所有位于半空间上的 \(\mathbf{x}\)。同时满足这两个约束相当于选择一个球的切片。
12.2.3.1. 拉格朗日¶
一般来说，解决一个约束优化问题是困难的。有一种解决方法源于物理学，其直觉相当简单。想象一个盒子里的球。球会滚到最低的地方，重力会被盒子侧壁施加给球的力所抵消。简而言之，目标函数（即重力）的梯度将被约束函数（球需要凭借墙壁的“推回”力而留在盒子内）的梯度所抵消。请注意，某些约束可能不活跃：未被球触及的墙壁将无法对球施加任何力。
跳过拉格朗日函数 \(L\) 的推导，上述推理可以通过以下鞍点优化问题来表达
这里的变量 \(\alpha_i\) (\(i=1,\ldots,n\)) 是所谓的拉格朗日乘子，它们确保约束被正确地执行。它们被选择得足够大，以确保对所有 \(i\) 都有 \(c_i(\mathbf{x}) \leq 0\)。例如，对于任何 \(\mathbf{x}\)，如果自然有 \(c_i(\mathbf{x}) < 0\)，我们最终会选择 \(\alpha_i = 0\)。此外，这是一个鞍点优化问题，其中我们希望相对于所有 \(\alpha_i\) *最大化* \(L\)，同时相对于 \(\mathbf{x}\) *最小化*它。有大量的文献解释了如何得到函数 \(L(\mathbf{x}, \alpha_1, \ldots, \alpha_n)\)。对我们来说，只要知道 \(L\) 的鞍点是原始约束优化问题得到最优解的地方就足够了。
12.2.3.2. 惩罚¶
至少*近似地*满足约束优化问题的一种方法是调整拉格朗日函数 \(L\)。我们不是满足 \(c_i(\mathbf{x}) \leq 0\)，而是简单地将 \(\alpha_i c_i(\mathbf{x})\) 添加到目标函数 \(f(x)\) 中。这确保了约束不会被严重违反。
实际上，我们一直在使用这个技巧。考虑 3.7节 中的权重衰减。在其中，我们将 \(\frac{\lambda}{2} \|\mathbf{w}\|^2\) 添加到目标函数中，以确保 \(\mathbf{w}\) 不会增长得太大。从约束优化的角度来看，我们可以看到这将确保对于某个半径 \(r\)，\(\|\mathbf{w}\|^2 - r^2 \leq 0\)。调整 \(\lambda\) 的值允许我们改变 \(\mathbf{w}\) 的大小。
总的来说，添加惩罚是确保近似满足约束的好方法。在实践中，这比精确满足约束要鲁棒得多。此外，对于非凸问题，许多在凸情况下使精确方法如此吸引人的性质（例如，最优性）不再成立。
12.2.3.3. 投影¶
满足约束的另一种策略是投影。同样，我们之前也遇到过，例如在 9.5节 中处理梯度裁剪时。在那里，我们通过以下方式确保了梯度的长度以 \(\theta\) 为界：
这实际上是 \(\mathbf{g}\) 在半径为 \(\theta\) 的球上的一个*投影*。更一般地，在凸集 \(\mathcal{X}\) 上的投影定义为
这是 \(\mathcal{X}\) 中离 \(\mathbf{x}\) 最近的点。
图 12.2.4 凸投影。¶
投影的数学定义可能听起来有点抽象。图 12.2.4 更清楚地解释了它。图中我们有两个凸集，一个圆形和一个菱形。两个集合内部的点（黄色）在投影期间保持不变。两个集合外部的点（黑色）被投影到集合内部离原始点（黑色）最近的点（红色）。虽然对于 \(\ell_2\) 球，这不改变方向，但这通常不一定成立，正如在菱形的情况下可以看到的那样。
凸投影的用途之一是计算稀疏权重向量。在这种情况下，我们将权重向量投影到 \(\ell_1\) 球上，这是 图 12.2.4 中菱形情况的一个推广版本。
12.2.4. 小结¶
在深度学习的背景下，凸函数的主要目的是激发优化算法并帮助我们详细理解它们。在下文中，我们将看到如何相应地推导出梯度下降和随机梯度下降。
凸集的交集是凸的。并集则不是。
凸函数的期望不小于期望的凸函数（詹森不等式）。
一个二次可微函数是凸的，当且仅当它的Hessian矩阵（二阶导数矩阵）是半正定的。
凸约束可以通过拉格朗日函数添加。在实践中，我们可以简单地在目标函数中添加一个惩罚项。
投影将点映射到凸集中离原始点最近的点。
12.2.5. 练习¶
假设我们想通过绘制集合内点之间的所有连线并检查这些线是否被包含在内来验证集合的凸性。
证明只检查边界上的点就足够了。
证明只检查集合的顶点就足够了。
用 \(\mathcal{B}_p[r] \stackrel{\textrm{def}}{=} \{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \textrm{ and } \|\mathbf{x}\|_p \leq r\}\) 表示使用 \(p\)-范数的半径为 \(r\) 的球。证明对于所有 \(p \geq 1\)，\(\mathcal{B}_p[r]\) 是凸的。
给定凸函数 \(f\) 和 \(g\)，证明 \(\mathrm{max}(f, g)\) 也是凸的。证明 \(\mathrm{min}(f, g)\) 不是凸的。
证明 softmax 函数的归一化是凸的。更具体地说，证明 \(f(x) = \log \sum_i \exp(x_i)\) 的凸性。
证明线性子空间，即 \(\mathcal{X} = \{\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}\}\)，是凸集。
证明在线性子空间且 \(\mathbf{b} = \mathbf{0}\) 的情况下，投影 \(\textrm{Proj}_\mathcal{X}\) 可以写成 \(\mathbf{M} \mathbf{x}\)，其中 \(\mathbf{M}\) 是某个矩阵。
证明对于二次可微的凸函数 \(f\)，我们可以写出 \(f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)\)，其中 \(\xi \in [0, \epsilon]\)。
给定一个凸集 \(\mathcal{X}\) 和两个向量 \(\mathbf{x}\) 和 \(\mathbf{y}\)，证明投影从不增加距离，即 \(\|\mathbf{x} - \mathbf{y}\| \geq \|\textrm{Proj}_\mathcal{X}(\mathbf{x}) - \textrm{Proj}_\mathcal{X}(\mathbf{y})\|\)。