当前位置：首页 > news >正文

动手学深度学习11.2. 凸性-笔记练习（PyTorch）

news 来源：原创 2025/5/24 16:28:38

本节课程地址：72 优化算法【动手学深度学习v2】_哔哩哔哩_bilibili

本节教材地址：11.2. 凸性 — 动手学深度学习 2.0.0 documentation

本节开源代码：...>d2l-zh>pytorch>chapter_multilayer-perceptrons>convexity.ipynb

凸性

凸性（convexity）在优化算法的设计中起到至关重要的作用，这主要是由于在这种情况下对算法进行分析和测试要容易。换言之，如果算法在凸性条件设定下的效果很差，那通常我们很难在其他条件下看到好的结果。此外，即使深度学习中的优化问题通常是非凸的，它们也经常在局部极小值附近表现出一些凸性。这可能会产生一些像 ("https://zh-v2.d2l.ai/chapter_references/zreferences.html#id76">Izmailovet al., 2018)这样比较有意思的新优化变体。

%matplotlib inline
import numpy as np
import torch
from mpl_toolkits import mplot3d
from d2l import torch as d2l

定义

在进行凸分析之前，我们需要定义凸集（convex sets）和凸函数（convex functions）。

凸集

凸集（convex set）是凸性的基础。简单地说，如果对于任何 $a, b \in \mathcal{X}$ ，连接 $a$ 和 $b$ 的线段也位于 $\mathcal{X}$ 中，则向量空间中的一个集合 $\mathcal{X}$ 是凸（convex）的。在数学术语上，这意味着对于所有 $\lambda \in [0, 1]$ ，我们得到

$\lambda a + (1-\lambda) b \in \mathcal{X}$ 当 $a, b \in \mathcal{X}.$ (11.2.1)

这听起来有点抽象，那我们来看一下图11.2.1里的例子。第一组存在不包含在集合内部的线段，所以该集合是非凸的，而另外两组则没有这样的问题。

接下来来看一下交集图11.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}$ 中，从而证明我们的定理。

我们可以毫不费力地进一步得到这样的结果：给定凸集 $\mathcal{X}_i$ ，它们的交集 $\cap_{i} \mathcal{X}_i$ 是凸的。但是反向是不正确的，考虑两个不相交的集合 $\mathcal{X} \cap \mathcal{Y} = \emptyset$ ，取 $a \in \mathcal{X}$ 和 $b \in \mathcal{Y}$ 。因为我们假设 $\mathcal{X} \cap \mathcal{Y} = \emptyset$ ，在图11.2.3 中连接 $a$ 和 $b$ 的线段需要包含一部分既不在 $\mathcal{X}$ 也不在 $\mathcal{Y}$ 中。因此线段也不在 $\mathcal{X} \cup \mathcal{Y}$ 中，因此证明了凸集的并集不一定是凸的，即非凸（nonconvex）的。

通常，深度学习中的问题是在凸集上定义的。例如， $\mathbb{R}^d$ ，即实数的 $d$ -维向量的集合是凸集（毕竟 $\mathbb{R}^d$ 中任意两点之间的线存在 $\mathbb{R}^d$ ）中。在某些情况下，我们使用有界长度的变量，例如球的半径定义为{ $\mathbf{x} | \mathbf{x} \in \mathbb{R}^d$ 且 $| \mathbf{x} | \leq r$ }。

凸函数

现在我们有了凸集，我们可以引入凸函数（convex function） $f$ 。给定一个凸集 $\mathcal{X}$ ，如果对于所有 $x, x' \in \mathcal{X}$ 和所有 $\lambda \in [0, 1]$ ，函数 $f: \mathcal{X} \to \mathbb{R}$ 是凸的，我们可以得到

$\lambda f(x) + (1-\lambda) f(x') \geq f(\lambda x + (1-\lambda) x').$ (11.2.2)

补充：

可以更直观地理解为，在函数 $f$ 的图像上取任意两点 $x$ 和 $x'$ ，连接这两点的线段完全位于函数图像的上方或在图像上。这意味着，对于这两点间的任何点 $\lambda x + (1-\lambda) x'$ ，函数值 $f(\lambda x + (1-\lambda) x')$ 都不会超过这两点函数值的加权平均。

为了说明这一点，让我们绘制一些函数并检查哪些函数满足要求。下面我们定义一些函数，包括凸函数和非凸函数。

f = lambda x: 0.5 * x**2  # 凸函数
g = lambda x: torch.cos(np.pi * x)  # 非凸函数
h = lambda x: torch.exp(0.5 * x)  # 凸函数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)

不出所料，余弦函数为非凸的，而抛物线函数和指数函数为凸的。请注意，为使该条件有意义， $\mathcal{X}$ 是凸集的要求是必要的。否则可能无法很好地界定 $f(\lambda x + (1-\lambda) x')$ 的结果。

詹森不等式

给定一个凸函数 $f$ ，最有用的数学工具之一就是詹森不等式（Jensen's inequality）。它是凸性定义的一种推广：

$\sum_i \alpha_i f(x_i) \geq f\left(\sum_i \alpha_i x_i\right) \text{ and } E_X[f(X)] \geq f\left(E_X[X]\right),$ (11.2.3)

其中 $\alpha_i$ 是满足 $\sum_i \alpha_i = 1$ 的非负实数， $X$ 是随机变量。换句话说，凸函数的期望不小于期望的凸函数，其中后者通常是一个更简单的表达式。为了证明第一个不等式，我们多次将凸性的定义应用于一次求和中的一项。

补充：

可以理解为，对于凸函数，函数在随机变量 $X$ 上的期望值不小于 $X$ 期望值处的函数值。

詹森不等式的一个常见应用：用一个较简单的表达式约束一个较复杂的表达式。例如，它可以应用于部分观察到的随机变量的对数似然。具体地说，由于 $\int P(Y) P(X \mid Y) dY = P(X)$ ，所以

$E_{Y \sim P(Y)}[-\log P(X \mid Y)] \geq -\log P(X),$ (11.2.4)

这里， $Y$ 是典型的未观察到的随机变量， $P(Y)$ 是它可能如何分布的最佳猜测， $P(X)$ 是将 $Y$ 积分后的分布。例如，在聚类中 $Y$ 可能是簇标签，而在应用簇标签时， $P(X \mid Y)$ 是生成模型。

性质

下面我们来看一下凸函数一些有趣的性质。

局部极小值是全局极小值

首先凸函数的局部极小值也是全局极小值。下面我们用反证法给出证明。

假设 $x^{\ast} \in \mathcal{X}$ 是一个局部最小值，则存在一个很小的正值 $p$ ，使得当 $x \in \mathcal{X}$ 满足 $0 < |x - x^{\ast}| \leq p$ 时，有 $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$ 。

然而，根据凸性的性质，有

$\begin{aligned} f(\lambda x^{\ast} + (1-\lambda) x') &\leq \lambda f(x^{\ast}) + (1-\lambda) f(x') \\ &< \lambda f(x^{\ast}) + (1-\lambda) f(x^{\ast}) \\ &= f(x^{\ast}), \\ \end{aligned}$ (11.2.5)

这与 $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(x) = \mathrm{max}(|x|-1, 0)$ 在 $[-1,1]$ 区间上都是最小值。相反，函数 $f(x) = \exp(x)$ 在 $\mathbb{R}$ 上没有取得最小值。对于 $x \to -\infty$ ，它趋近于 0 ，但是没有 $f(x) = 0$ 的 $x$ 。

凸函数的下水平集是凸的

我们可以方便地通过凸函数的下水平集（below sets）定义凸集。具体来说，给定一个定义在凸集 $\mathcal{X}$ 上的凸函数 $f$ ，其任意一个下水平集

$\mathcal{S}_b := \{x | x \in \mathcal{X} \text{ and } f(x) \leq b\}$ (11.2.6)

是凸的。

让我们快速证明一下。对于任何 $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$ ，所以

$f(\lambda x + (1-\lambda) x') \leq \lambda f(x) + (1-\lambda) f(x') \leq b.$ (11.2.7)

凸性和二阶导数

当一个函数的二阶导数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 存在时，我们很容易检查这个函数的凸性。我们需要做的就是检查 $\nabla^2f \succeq 0$ ，即对于所有 $\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}$ ，即其导数是单位矩阵。

更正式地讲， $f$ 为凸函数，当且仅当任意二次可微一维函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是凸的。对于任意二次可微多维函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ ，它是凸的当且仅当它的Hessian $\nabla^2f \succeq 0$ 。

首先，我们来证明一下一维情况。为了证明凸函数的 $f''(x) \geq 0$ ，我们使用：

$\frac{1}{2} f(x + \epsilon) + \frac{1}{2} f(x - \epsilon) \geq f\left(\frac{x + \epsilon}{2} + \frac{x - \epsilon}{2}\right) = f(x).$ (11.2.8)

因为二阶导数是由有限差分的极限给出的，所以遵循

$f''(x) = \lim_{\epsilon \to 0} \frac{f(x+\epsilon) + f(x - \epsilon) - 2f(x)}{\epsilon^2} \geq 0.$ (11.2.9)

为了证明 $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'(\alpha) = \frac{f(x) - f(a)}{x-a}$ 且 $f'(\beta) = \frac{f(b) - f(x)}{b-x}.$ (11.2.10)

通过单调性 $f'(\beta) \geq f'(\alpha)$ ，因此

$\frac{x-a}{b-a}f(b) + \frac{b-x}{b-a}f(a) \geq f(x).$ (11.2.11)

由于 $x = (1-\lambda)a + \lambda b$ ，所以

$\lambda f(b) + (1-\lambda)f(a) \geq f((1-\lambda)a + \lambda b),$ (11.2.12)

从而证明了凸性。

第二，我们需要一个引理证明多维情况： $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是凸的当且仅当对于所有 $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$

$g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y}) \text{ where } z \in [0,1]$ (11.2.13)

是凸的。

为了证明 $f$ 的凸性意味着 $g$ 是凸的，我们可以证明，对于所有的 $a, b, \lambda \in [0,1]$ （这样有 $0 \leq \lambda a + (1-\lambda) b \leq 1$ ），

$\begin{aligned} &g(\lambda a + (1-\lambda) b)\\ =&f\left(\left(\lambda a + (1-\lambda) b\right)\mathbf{x} + \left(1-\lambda a - (1-\lambda) b\right)\mathbf{y} \right)\\ =&f\left(\lambda \left(a \mathbf{x} + (1-a) \mathbf{y}\right) + (1-\lambda) \left(b \mathbf{x} + (1-b) \mathbf{y}\right) \right)\\ \leq& \lambda f\left(a \mathbf{x} + (1-a) \mathbf{y}\right) + (1-\lambda) f\left(b \mathbf{x} + (1-b) \mathbf{y}\right) \\ =& \lambda g(a) + (1-\lambda) g(b). \end{aligned}$ (11.2.14)

为了证明这一点，我们可以证明对 $[0,1]$ 中所有的 $\lambda$ ：

$\begin{aligned} &f(\lambda \mathbf{x} + (1-\lambda) \mathbf{y})\\ =&g(\lambda \cdot 1 + (1-\lambda) \cdot 0)\\ \leq& \lambda g(1) + (1-\lambda) g(0) \\ =& \lambda f(\mathbf{x}) + (1-\lambda) f(\mathbf{y}). \end{aligned}$ (11.2.15)

最后，利用上面的引理和一维情况的结果，我们可以证明多维情况：多维函数 $f: \mathbb{R}^n \rightarrow \mathbb{R}$ 是凸函数，当且仅当 $g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y})$ 是凸的，这里 $z \in [0,1]$ ， $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ 。根据一维情况，此条成立的条件为，当且仅当对于所有 $\mathbf{x}, \mathbf{y} \in \mathbb{R}^n$ ， $g'' = (\mathbf{x} - \mathbf{y})^\top \mathbf{H}(\mathbf{x} - \mathbf{y}) \geq 0$ ( $\mathbf{H} \stackrel{\mathrm{def}}{=} \nabla^2f$ )。这相当于根据半正定矩阵的定义， $\mathbf{H} \succeq 0$ 。

补充：

1. Hessian矩阵：在多维情况下，函数 $f$ 的Hessian矩阵 $\mathbf{H}$ 是一个二阶偏导数构成的方阵，即 $\mathbf{H} \stackrel{\mathrm{def}}{=} \nabla^2f$ 。Hessian矩阵提供了函数在各个方向上的曲率信息。

2. 半正定矩阵：如果对于所有非零向量 $\mathbf{x}$ ，都有 $\mathbf{x}^\top \mathbf{H} \mathbf{x} \geq 0$ ，则称矩阵 $\mathbf{H}$ 是半正定的。这意味着Hessian矩阵在任何方向上的二次型都是非负的。

3. 凸性条件：根据上述定义，如果Hessian矩阵 $\mathbf{H}$ 对所有 $\mathbf{x} \in \mathbb{R}^n$ 都是半正定的，即 $\mathbf{H} \succeq 0$ ，那么函数 $f$ 是凸的。这是因为半正定的Hessian矩阵保证了函数在任何方向上的曲率都是非负的，这与一维情况下二阶导数非负的条件是一致的。

约束

凸优化的一个很好的特性是能够让我们有效地处理约束（constraints）。即它使我们能够解决以下形式的约束优化（constrained optimization）问题：

$\begin{aligned} \mathop{\mathrm{minimize~}}_{\mathbf{x}} & f(\mathbf{x}) \\ \text{ subject to } & c_i(\mathbf{x}) \leq 0 \text{ for all } i \in \{1, \ldots, N\}. \end{aligned}$ (11.2.16)

这里 $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}$ 。同时满足这两个约束等于选择一个球的切片作为约束集。

拉格朗日函数

通常，求解一个有约束的优化问题是困难的，解决这个问题的一种方法来自物理中相当简单的直觉。想象一个球在一个盒子里，球会滚到最低的地方，重力将与盒子两侧对球施加的力平衡。简而言之，目标函数（即重力）的梯度将被约束函数的梯度所抵消（由于墙壁的“推回”作用，需要保持在盒子内）。请注意，任何不起作用的约束（即球不接触壁）都将无法对球施加任何力。

这里我们简略拉格朗日函数 $L$ 的推导，上述推理可以通过以下鞍点优化问题来表示：

$L(\mathbf{x}, \alpha_1, \ldots, \alpha_n) = f(\mathbf{x}) + \sum_{i=1}^n \alpha_i c_i(\mathbf{x}) \text{ where } \alpha_i \geq 0.$ (11.2.17)

这里的变量 $\alpha_i$ （ $i=1,\ldots,n$ ）是所谓的拉格朗日乘数（Lagrange multipliers），它确保约束被正确地执行。选择它们的大小足以确保所有 $i$ 的 $c_i(\mathbf{x}) \leq 0$ 。例如，对于 $c_i(\mathbf{x}) \leq 0$ 中任意 $\mathbf{x}$ ，我们最终会选择 $\alpha_i = 0$ 。此外，这是一个鞍点（saddlepoint）优化问题。在这个问题中，我们想要使 $L$ 相对于 $\alpha_i$ 最大化（maximize），同时使它相对于 $\mathbf{x}$ 最小化（minimize）。有大量的文献解释如何得出函数 $L(\mathbf{x}, \alpha_1, \ldots, \alpha_n)$ 。我们这里只需要知道 $L$ 的鞍点是原始约束优化问题的最优解就足够了。

惩罚

一种至少近似地满足约束优化问题的方法是采用拉格朗日函数 $L$ 。除了满足 $c_i(\mathbf{x}) \leq 0$ 之外，我们只需将 $\alpha_i c_i(\mathbf{x})$ 添加到目标函数 $f(x)$ 。这样可以确保不会严重违反约束。

事实上，我们一直在使用这个技巧。比如权重衰减 4.5节，在目标函数中加入 $\frac{\lambda}{2} |\mathbf{w}|^2$ ，以确保 $\mathbf{w}$ 不会增长太大。使用约束优化的观点，我们可以看到，对于若干半径 $r$ ，这将确保 $|\mathbf{w}|^2 - r^2 \leq 0$ 。通过调整 $\lambda$ 的值，我们可以改变 $\mathbf{w}$ 的大小。

通常，添加惩罚是确保近似满足约束的一种好方法。在实践中，这被证明比精确的满意度更可靠。此外，对于非凸问题，许多使精确方法在凸情况下的性质（例如，可求最优解）不再成立。

投影

满足约束条件的另一种策略是投影（projections）。同样，我们之前也遇到过，例如在 8.5节中处理梯度截断时，我们通过

$\mathbf{g} \leftarrow \mathbf{g} \cdot \mathrm{min}(1, \theta/\|\mathbf{g}\|),$ (11.2.18)

确保梯度的长度以 $\theta$ 为界限。

这就是 $\mathbf{g}$ 在半径为 $\theta$ 的球上的投影（projection）。更泛化地说，在凸集 $\mathcal{X}$ 上的投影被定义为

$\mathrm{Proj}_\mathcal{X}(\mathbf{x}) = \mathop{\mathrm{argmin}}_{\mathbf{x}' \in \mathcal{X}} \|\mathbf{x} - \mathbf{x}'\|.$ (11.2.19)

它是 $\mathcal{X}$ 中离 $\mathbf{X}$ 最近的点。

投影的数学定义听起来可能有点抽象，为了解释得更清楚一些，请看图11.2.4 。图中有两个凸集，一个圆和一个菱形。两个集合内的点（黄色）在投影期间保持不变。两个集合（黑色）之外的点投影到集合中接近原始点（黑色）的点（红色）。虽然对 $L_2$ 的球面来说，方向保持不变，但一般情况下不需要这样。

凸投影的一个用途是计算稀疏权重向量。在本例中，我们将权重向量投影到一个 $L_1$ 的球上，这是图11.2.4 中菱形例子的一个广义版本。

小结

在深度学习的背景下，凸函数的主要目的是帮助我们详细了解优化算法。我们由此得出梯度下降法和随机梯度下降法是如何相应推导出来的。

凸集的交集是凸的，并集不是。
根据詹森不等式，“一个多变量凸函数的总期望值”大于或等于“用每个变量的期望值计算这个函数的总值“。
一个二次可微函数是凸函数，当且仅当其Hessian（二阶导数矩阵）是半正定的。
凸约束可以通过拉格朗日函数来添加。在实践中，只需在目标函数中加上一个惩罚就可以了。
投影映射到凸集中最接近原始点的点。

练习

假设我们想要通过绘制集合内点之间的所有直线并检查这些直线是否包含来验证集合的凸性。i.证明只检查边界上的点是充分的。ii.证明只检查集合的顶点是充分的。
解：
i）设集合 $\mathcal{X}$ 为凸集，则对于任意两点 $x, x' \in \mathcal{X}$ 和所有 $\lambda \in [0,1]$ ，点 $\lambda a +(1-\lambda)b \in \mathcal{X}$ 。
那么考虑 $x$ 和 $x'$ 是两个边界点，则 $\mathcal{X}$ 边界上任意两点之间的点 $\lambda a +(1-\lambda)b$ 都在 $\mathcal{X}$ 内。
由于边界上的点定义了 $\mathcal{X}$ 的“形状”，如果边界上的线段都在集合内，那么集合内部的点之间的线段也必然在集合内，因为它们位于边界点连线的内侧。
因此，只要边界上的点之间的所有线段都包含在集合内，就可以推断出集合X是凸集。即证，只检查边界上的点是充分的。
ii）顶点是集合 $\mathcal{X}$ 的一个特殊边界点，在有限维空间中，凸集的顶点是边界上那些不能被表示为其他边界点凸组合的点。如果一个凸集 $\mathcal{X}$ 的所有顶点之间的线段都包含在 $\mathcal{X}$ 内，那么根据凸集的定义，这些线段上的所有点也都在 $\mathcal{X}$ 内。由于顶点是凸集边界上最“极端”的点，任何集合内的点都可以看作是顶点以及可能的其他点的凸组合。因此，如果顶点之间的线段都是凸的，那么由顶点以及顶点的凸组合形成的线段也将是凸的。即证，只检查集合的顶点是充分的。
用 $p$ -范数表示半径为 $r$ 的球，证明 $\mathcal{B}_p[r] := {\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ and } |\mathbf{x}|_p \leq r}$ ， $\mathcal{B}_p[r]$ 对于所有 $p \geq 1$ 是凸的。
解：
证明 $\mathcal{B}_p[r] := {\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ and } |\mathbf{x}|_p \leq r}$ ， $\mathcal{B}_p[r]$ 对于所有 $p \geq 1$ 是凸的，即是证明对于任意 $\mathbf{a}, \mathbf{b} \in \mathcal{B}_p[r]$ 和 $\lambda \in [0, 1]$ ： $\lambda \mathbf{a} + (1-\lambda) \mathbf{b}\|_p \leq r$
闵可夫斯基不等式表明对于任意向量 $\mathbf{u}, \mathbf{v} \in \mathbb{R}^d$ 和 $p \geq 1$ ，有：
$\|\mathbf{u} + \mathbf{v}\|_p \leq \|\mathbf{u}\|_p + \|\mathbf{v}\|_p$
应用闵可夫斯基不等式可得：
$\|\lambda \mathbf{a} + (1-\lambda) \mathbf{b}\|_p \leq \|\lambda \mathbf{a}\|_p + \|(1-\lambda) \mathbf{b}\|_p$
由于 $p$ -范数是齐次的，则有：
$\|\lambda \mathbf{a}\|_p = \lambda \|\mathbf{a}\|_p \quad$ 和 $\quad \|(1-\lambda) \mathbf{b}\|_p = (1-\lambda) \|\mathbf{b}\|_p$
代入并简化可得：
$\|\lambda \mathbf{a} + (1-\lambda) \mathbf{b}\|_p \leq \lambda \|\mathbf{a}\|_p + (1-\lambda) \|\mathbf{b}\|_p \leq \lambda r + (1-\lambda) r = r$
因此，对于任意 $\mathbf{a}, \mathbf{b} \in \mathcal{B}_p[r]$ 和 $\lambda \in [0, 1]$ ，点 $\lambda \mathbf{a} + (1-\lambda) \mathbf{b} \in \mathcal{B}_p[r]$ 。
即证以 $p$ -范数定义的半径为 $r$ 的球 $\mathcal{B}_p[r]$ 对于所有 $p \geq 1$ 是凸的。
已知凸函数 $f$ 和 $g$ 表明 $\mathrm{max}(f, g)$ 也是凸函数。证明 $\mathrm{min}(f, g)$ 是非凸的。
解：
反例法证明 $\mathrm{min}(f, g)$ 是非凸的，如下：
设凸函数 $f$ 和 $g$ 为：
$f(x) = x^2 \\ g(x) = (x-1)^2$
若 $h(x) = \mathrm{min}(f(x), g(x))$ 为凸函数，则对于所有 $x, y$ 和 $\lambda \in [0, 1]$ ，以下不等式成立：
$h(\lambda x + (1-\lambda) y) \leq \lambda h(x) + (1-\lambda) h(y)$
设 $x = 0$ 和 $y = 1$ ，有：
$h(0) = \mathrm{min}(f(0), g(0)) = \mathrm{min}(0^2, (0-1)^2) = 0$
$h(1) = \mathrm{min}(f(1), g(1)) = \mathrm{min}(1^2, (1-1)^2) = 0$
当 $\lambda = 0.5$ 时：
$h(0.5) = \mathrm{min}(f(0.5), g(0.5)) = \mathrm{min}((0.5)^2, (0.5-1)^2) = \mathrm{min}(0.25, 0.25) = 0.25$
由上可见：
$h(0.5) = 0.25 \not\leq 0 = \lambda h(x) + (1-\lambda) h(y)$
因此 $h(x) = \mathrm{min}(f(x), g(x))$ 不是一个凸函数。
即证，即使 $f$ 和 $g$ 是凸函数， $\mathrm{min}(f, g)$ 也可能是非凸的。
证明Softmax函数的规范化是凸的，即 $f(x) = \log \sum_i \exp(x_i)$ 的凸性。
解：
要证明函数 $f(x) = \log \sum_i \exp(x_i)$ 是凸的，即证明Hessian矩阵是半正定的。
$f(x)$ 对 $x_j$ 的一阶导数是：
$\frac{\partial f}{\partial x_j} = \frac{\partial}{\partial x_j} \log \sum_i \exp(x_i) = \frac{\exp(x_j)}{\sum_i \exp(x_i)}$
$f(x)$ 对 $x_j$ 和 $x_k$ 的二阶导数是：
$\frac{\partial^2 f}{\partial x_j \partial x_k} = \frac{\partial}{\partial x_k} \left( \frac{\exp(x_j)}{\sum_i \exp(x_i)} \right)$
对上式使用商规则，可得：
$\frac{\partial^2 f}{\partial x_j \partial x_k} = \frac{\delta_{jk} \exp(x_j) \sum_i \exp(x_i) - \exp(x_j) \exp(x_k)}{(\sum_i \exp(x_i))^2}$
其中 $\delta_{jk}$ 是克罗内克函数，当 $j = k$ 时为1，否则为0。
Hessian矩阵是二阶偏导数的矩阵，即：
$\mathbf{H} = \left[ \frac{\partial^2 f}{\partial x_j \partial x_k} \right] = \left[ \frac{\delta_{jk} \exp(x_j) \sum_i \exp(x_i) - \exp(x_j) \exp(x_k)}{(\sum_i \exp(x_i))^2} \right]$
证明 $\mathbf{H}$ 是半正定的，即是要证明对于任何向量 $\mathbf{v} \in \mathbb{R}^n$ ， $\mathbf{v}^\top \mathbf{H} \mathbf{v} \geq 0$ 。
$\mathbf{v}^\top \mathbf{H} \mathbf{v} = \sum_{j=1}^n \sum_{k=1}^n v_j v_k \frac{\partial^2 f}{\partial x_j \partial x_k} \\ = \sum_{j=1}^n \sum_{k=1}^n v_j v_k \frac{\delta_{jk} \exp(x_j) \sum_i \exp(x_i) - \exp(x_j) \exp(x_k)}{(\sum_i \exp(x_i))^2} \\ = \sum_{j=1}^n v_j^2 \frac{\exp(x_j)}{\sum_i \exp(x_i)} - \left( \sum_{j=1}^n v_j \frac{\exp(x_j)}{\sum_i \exp(x_i)} \right)^2 \\ = \sum_{j=1}^n \left( \frac{v_j \exp(x_j)}{\sum_i \exp(x_i)} \right)^2 - \left( \sum_{j=1}^n v_j \frac{\exp(x_j)}{\sum_i \exp(x_i)} \right)^2 \\ = \sum_{j=1}^n \left( \frac{v_j \exp(x_j)}{\sum_i \exp(x_i)} - \frac{\left( \sum_{k=1}^n v_k \exp(x_k) \right)}{\sum_i \exp(x_i)} \right)^2$
由于任何实数的平方都是非负的，所以： $\mathbf{v}^\top \mathbf{H} \mathbf{v} \geq 0$
因此，Hessian矩阵是半正定的，即证softmax函数 $f(x) = \log \sum_i \exp(x_i)$ 是凸的。
证明线性子空间 $\mathcal{X} = {\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}}$ 是凸集。
解：
证明线性子空间 $\mathcal{X} = {\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}}$ 是凸集，即是证明对于任意两点 $\mathbf{j}, \mathbf{k} \in \mathcal{X}$ 和任意 $\lambda \in [0, 1]$ ，点 $\lambda \mathbf{j} + (1-\lambda) \mathbf{k}$ 也在 $\mathcal{X}$ 内，即：
$\mathbf{W} (\lambda \mathbf{j} + (1-\lambda) \mathbf{k}) = \lambda \mathbf{W} \mathbf{j} + (1-\lambda) \mathbf{W} \mathbf{k}$
上式代入 $\mathbf{W} \mathbf{j} = \mathbf{b}$ 和 $\mathbf{W} \mathbf{k} = \mathbf{b}$ ，得：
$\mathbf{W} (\lambda \mathbf{j} + (1-\lambda) \mathbf{k}) = \lambda \mathbf{b} + (1-\lambda) \mathbf{b} = \mathbf{b}$
因此， $\lambda \mathbf{j} + (1-\lambda) \mathbf{k} \in \mathcal{X}$ ，
即证线性子空间 $\mathcal{X} = {\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}}$ 是凸集。
证明在线性子空间 $\mathbf{b} = \mathbf{0}$ 的情况下，对于矩阵 $\mathbf{M}$ 的投影 $\mathrm {Proj} \mathcal{X}$ 可以写成 $\mathbf{M} \mathbf{X}$ 。
解：
当 $\mathbf{b} = \mathbf{0}$ 时，意味着 $\mathcal{X}$ 是通过原点的子空间，则投影操作不会涉及到额外的平移。
投影矩阵 $\mathbf{M}$ 可以将任何向量投影到子空间 $\mathcal{X}$ 上，对于列向量 $\mathbf{X}$ ， $\mathbf{M} \mathbf{X}$ 给出了 $\mathbf{X}$ 中每列向量在 $\mathcal{X}$ 上的投影。
具体来说，假设 $\mathbf{X} = [\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n]$ ，其中每个 $\mathbf{x}_i$ 是 $\mathbf{X}$ 的一列，并且 $\mathbf{M}$ 是到 $\mathcal{X}$ 的投影矩阵。则 $\mathbf{M} \mathbf{X}$ 可以写作： $\mathbf{M}\mathbf{X} = \mathbf{M}[\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_n] = [\mathbf{M}\mathbf{x}_1, \mathbf{M}\mathbf{x}_2, \ldots, \mathbf{M}\mathbf{x}_n]$ 上式中的每一项 $\mathbf{M}\mathbf{x}_i$ 就是向量 $\mathbf{x}_i$ 在 $\mathcal{X}$ 上的投影。因此， $\mathbf{M} \mathbf{X}$ 的结果是一个新矩阵，其列向量分别是原矩阵 $\mathbf{X}$ 的列向量在 $\mathcal{X}$ 上的投影。
证明对于凸二次可微函数 $f$ ，对于 $\xi \in [0, \epsilon]$ ，我们可以写成 $f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)$ 。
解：
对于凸二次可微函数f进行二阶泰勒展开：
$f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(c) + o(\epsilon^2)$
其中 $c \in (x, x + \epsilon)$ ， $o(\epsilon^2)$ 表示当 $\epsilon \to 0$ 时比 $\epsilon^2$ 更高阶的小量，可忽略。
根据拉格朗日中值定理，上式中的 $c$ 可以写成 $x + \xi\epsilon$ 的形式，其中 $\xi \in (0, 1)$ 。因此，上式可以改写为：
$f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi\epsilon)$
因为 $\xi \in (0, 1)$ ，所以x+ξϵ落在区间 $[x, x + \epsilon]$ 内。将 $\xi\epsilon$ 重新标记为 $\xi$ ，那么 $\xi$ 就落在 $[0, \epsilon]$ 内，即证对于 $\xi \in [0, \epsilon]$ ，有：
$f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)$
给定一个凸集 $\mathcal{X}$ 和两个向量 $\mathbf{x}$ 和 $\mathbf{y}$ 证明了投影不会增加距离，即 $|\mathbf{x} - \mathbf{y}| \geq |\mathrm{Proj}\mathcal{X}(\mathbf{x}) - \mathrm{Proj}\mathcal{X}(\mathbf{y})|$ 。
解：
根据投影的非扩张性，对于任何点 $\mathbf{z}$ 和 $\mathbf{w}$ 及其在X上的投影 $\mathrm{Proj}\mathcal{X}(\mathbf{z})$ 和 $\mathrm{Proj}\mathcal{X}(\mathbf{w})$ ，有 $\|\mathrm{Proj}_\mathcal{X}(\mathbf{z}) - \mathrm{Proj}_\mathcal{X}(\mathbf{w})\| \leq \|\mathbf{z} - \mathbf{w}\|$
令上式中的 $\mathbf{z} = \mathbf{x}$ 和 $\mathbf{w} = \mathbf{y}$ ，则有：
$\|\mathrm{Proj}_\mathcal{X}(\mathbf{x}) - \mathrm{Proj}_\mathcal{X}(\mathbf{y})\| \leq \|\mathbf{x} - \mathbf{y}\|$
即证对于任意的 $\mathbf{x}$ 和 $\mathbf{y}$ 以及凸集 $\mathcal{X}$ ，投影操作不会增加两点之间的距离。这表明投影是一种非扩张映射，保持或减少了原始空间中点对之间的距离。

凸性

定义

凸集

凸函数

詹森不等式

性质

局部极小值是全局极小值

凸函数的下水平集是凸的

凸性和二阶导数

约束

拉格朗日函数

惩罚

投影

小结

练习

相关文章：