优化理论基础（上） · 最优化 02

Created by Hailiang Zhao, 2021年8月26日 440 reads Last modified: 2022年1月7日

数学优化

获取pdf

关键字：最优化理论范数导数泰勒展开梯度 Lipschitz 连续闭函数上方图

摘要 —— 本文主要介绍了向量和矩阵的范数、导数以及闭函数等基本概念。

在本文中，我们首先给出向量和矩阵范数的定义，然后给出了向量导数（梯度）及相关概念的定义。最后，我们给出了凸优化领域中的一个重要概念：闭函数。

向量范数

范数是高维空间中 计量事物自身长度 的一种方式。

向量范数（定义）. 向量范数一个从向量空间 $\mathbb{R}^n$ 到实数域 $\mathbb{R}$ 的非负函数 $\| \cdot \|$，且满足

正定性：$\forall v \in \mathbb{R}^n$，$\| v \| \geq 0$ 且 $\| v \| = 0 \Longleftrightarrow v = 0$；
齐次性：$\forall v \in \mathbb{R}^n, \alpha \in \mathbb{R}$，$\| \alpha v \| = |\alpha| \| v \|$；
三角不等式：$\forall v,w \in \mathbb{R}^n$，$\| v + w \| \leq \| v \| + \| w \|$。

一些常用的范数：

$l_p$ 范数（$p \geq 1$）：$\| v \|_p \triangleq \Big(|v_1|^p + ... + |v_n|^p \Big)^{\frac{1}{p}}$，默认 $p=2$；
由正定阵 $A$ 诱导的范数 ：$\| v \|_A \triangleq \sqrt{v^\mathrm{T} A v}$。

柯西不等式（定理）. $\forall a, b \in \mathbb{R}^n$，$|a^\mathrm{T} b| \leq \| a \| \| b \|$。

矩阵范数

矩阵的 $l_p$ 范数（$p \geq 1$）： $$ \| A \|_p \triangleq \Big(\sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^p \Big)^{\frac{1}{p}} $$ $p=2$ 时，称之为矩阵的 Frobenius 范数，记为 $\|\cdot \|_F$： $$ \| A \|_F \triangleq \sqrt{\sum_{i,j}a_{ij}^2} = \sqrt{\mathrm{Tr} \big(A^\mathrm{T} A\big)} $$ 正交不变性（定理）. 对于任意的正交矩阵 $U \in \mathbb{R}^{m \times m}, V \in \mathbb{R}^{n \times n}$， $$ | UAV |_F^2 = \mathrm{Tr} \Big(UAVV^\mathrm{T}A^\mathrm{T}U^\mathrm{T}\Big) = | A |_F^2 $$ 这里运用了性质 $\mathrm{Tr}(AB) = \mathrm{Tr}(BA)$。

算子范数（由向量范数诱导的矩阵范数）

给定 $m$ 维和 $n$ 维空间的向量范数 $\| \cdot \|_{(m)}$ 和 $\| \cdot \|_{(n)}$， $$ \| A \|_{(m,n)} \triangleq \max_{\forall x \in \mathbb{R}^n, \| x \|_{(n)} = 1} \| Ax \|_{(m)} $$ 显然有结论： \begin{aligned} &\qquad \| Ax \|_{(m)} \leq \| A \|_{(m,n)} \| x \|_{(n)} \\ &\textrm{（矩阵范数和给定的向量范数 “相容”）} \end{aligned} 若 $\| \cdot \|_{(m)}$ 和 $\| \cdot \|_{(n)}$ 均取相应空间的 $l_p$ 范数，如 $p=2$，则可得到 矩阵的 2 范数 ： $$ \| A \|_2 \triangleq \max_{\forall x \in \mathbb{R}^n, \| x \|_2 = 1} \| Ax \|_2 = \max_{r=1, ..., \textrm{rank}(A)} \sigma_r \textrm{(最大奇异值)} $$

严格区分矩阵的 2 范数和矩阵的 $F$ 范数（$l_2$ 范数）！

核范数（非零奇异值之和）

$$ \| A \|_* \triangleq \sum_{r=1}^{\textrm{rank}(A)} \sigma_r $$

内积用来表征两个矩阵（或其张成的空间）之间的夹角。常用的内积是 Frobenius 内积： $$ \langle A, B \rangle \triangleq \mathrm{Tr} (AB^\mathrm{T}) = \sum_{i,j} a_{ij} b_{ij} $$ 显然，$\langle A, A \rangle = \| A \|_F^2$。

矩阵范数的柯西不等式（定理）. $\forall A, B \in \mathbb{R}^{m \times n}$，$|\langle A, B \rangle| \leq \| A \|_F \| B \|_F$。在 $A$ 和 $B$ 线性相关的时候取等。

导数

梯度（定义）. 若函数 $f: \mathbb{R}^n \to \mathbb{R}$ 在点 $x$ 的一个邻域内有意义且存在 $g \in \mathbb{R}^n$ 使得 $$ \lim_{p \to 0} \frac{f(x + p) - f(x) - g^\mathrm{T}p}{\| p \|} = 0, $$ 则称 $f$ 在点 $x$ 处可微。我们称 $g$ 为 $f$ 在点 $x$ 处的梯度，记为 $\nabla f(x)$。若区域 $D$ 上每一个点 $x$ 都有 $\nabla f(x)$ 存在，则称 $f$ 在 $D$ 上可微。

基于该定义，若依次对每一个维度 $i$ 取 $p = \varepsilon e_i$（$e_i$ 为第 $i$ 维的标准基），则可得到 $$ \nabla f(x) = \bigg[ \frac{\partial f(x)}{\partial x_1}, ..., \frac{\partial f(x)}{\partial x_n} \bigg]^\mathrm{T} $$

二阶导数

海瑟矩阵（定义）. 若函数 $f: \mathbb{R}^n \to \mathbb{R}$ 在点 $x$ 的二阶偏导数 $\Big\{\frac{\partial^2 f(x)}{\partial x_i \partial x_j}\Big\}_{i,j=1,...,n}$ 都存在，则 $$ \nabla^2 f(x) \triangleq \Bigg[ \frac{\partial^2 f(x)}{\partial x_i \partial x_j} \Bigg]_{i,j=1,...,n} \in \mathbb{R}^{n \times n} $$ 称为 $f$ 在点 $x$ 处海瑟矩阵。若区域 $D$ 上每一个点 $x$ 都有 $\nabla^2 f(x)$ 存在，则称 $f$ 在 $D$ 上可微。若 $\nabla^2 f(x)$ 在 $D$ 上还连续，则称 $f$ 在 $D$ 上二阶连续可微，此时 $\nabla^2 f(x)$ 是一个对称阵。

雅可比矩阵（定义）. 对于向量值函数 $f: \mathbb{R}^n \to \mathbb{R}^m$，可类比 “梯度” 定义它的雅可比矩阵： $$ J(x) = \Bigg[ \frac{\partial f_i(x)}{\partial x_j} \Bigg]_{ij} \in \mathbb{R}^{n \times m} $$

泰勒展开

若 $f: \mathbb{R}^n \to \mathbb{R}$ 是连续可微的，则 $$ f(x + p) = f(x) + \nabla f(x + tp)^\mathrm{T} p, $$ 其中 $0<t<1$，$p \in \mathbb{R}^n$。

若 $f: \mathbb{R}^n \to \mathbb{R}$ 是二阶连续可微的，则 \begin{aligned} \nabla f(x+p) &= \nabla f(x) + \int_0^1 \nabla^2 f(x + tp) p dt \qquad (\textrm{对上式求导}) \\ f(x + p) &= f(x) + \nabla f(x)^\mathrm{T} p + \frac{1}{2} p^\mathrm{T} \nabla^2 f(x+ tp) p, \end{aligned} 其中 $0<t<1$，$p \in \mathbb{R}^n$。

梯度 Lipschitz 连续

梯度 Lipschitz 连续（定义）. 对于可微函数 $f$，若存在 $L > 0$ 对于任意 $x,y \in \mathbf{dom}f$ 有 \begin{aligned} \| \nabla f(x) - \nabla f(y) \| \leq L \| x - y \|, \end{aligned} 则称 $f$ 是 $L$-Lipschitz 连续的。

$L$-Lipschitz 连续表明 $\nabla f(x)$ 的变化可以被自变量 $x$ 的变化所控制，这在算法的收敛性证明中将发挥重要的作用。

二次上界（定理）. $L$-Lipschitz 连续的函数 $f: \mathbb{R}^n \to \mathbb{R}$ 有二次上界： $$ f(y) \leq f(x) + \nabla f(x)^\mathrm{T} (y - x) + \frac{L}{2} \| y - x \|^2, \forall x,y \in \mathbf{dom}f. $$

证明 . 通过构造辅助函数 $g(t) = f\big(x + t (y - x)\big), t \in [0,1]$ 来推导 $$ f(y) - f(x) - \nabla f(x)^\mathrm{T} (y - x) $$ 的上界。

这说明 $L$-Lipschitz 连续函数被一个二次函数的上界所控制，即 $f(x)$ 的增长速度不超过二次。（$\mathbf{dom}f$ 仅需是凸集即可，不需要是 $\mathbb{R}^n$。）

差距的下界（定理）. 若 $L$-Lipschitz 连续的函数 $f: \mathbb{R}^n \to \mathbb{R}$ 的定义域为 $\mathbb{R}^n$ 且存在一个全局极小点 $x^*$，则 $$ \frac{1}{2L} \| \nabla f(x) \|^2 \leq f(x) - f(x^*), \forall x \in \mathbb{R}^n. $$

证明 . 根据上一定理的结论可得 \begin{aligned} f(x^*) &\leq \inf_{y \in \mathbb{R}^n} \Big\{ f(x) + \nabla f(x)^\mathrm{T} (y - x) + \frac{L}{2} \| y - x \|^2 \Big\} \\ &= f(x) - \frac{1}{2L} \| \nabla f(x) \|^2. \qquad \qquad \triangleright - \frac{b}{2a} \end{aligned}

矩阵变量函数的导数

Frechet 可微（定义）. 对于函数 $f: \mathbb{R}^{m \times n} \to \mathbb{R}$，若存在矩阵 $G \in \mathbb{R}^{m \times n}$ 满足 $$ \lim_{V \to 0} \frac{f(X + V) - f(X) - \langle G, V \rangle}{\| V \|} = 0, $$ 则称 $f$ 在 $X$ 处 Frechet 可微，$G$ 是相应意义下的梯度，记为 $\nabla f(X)$。

同样有： $$ \nabla f(X) = \Bigg[ \frac{\partial f}{\partial x_{ij}} \Bigg]_{ij} $$ Gateaux 可微（定义）. 对于函数 $f: \mathbb{R}^{m \times n} \to \mathbb{R}$，若存在矩阵 $G \in \mathbb{R}^{m \times n}$ 对任意方向 $V \in \mathbb{R}^{m \times n}$ 和任意 $t \in \mathbb{R}$ 满足 $$ \lim_{t \to 0} \frac{f(X + tV) - f(X) - t \langle G, V \rangle}{t} = 0, $$ 则称 $f$ 在 $X$ 处 Gateaux 可微，$G$ 是相应意义下的梯度，仍然记为 $\nabla f(X)$。

Gateaux 可微其实是方向导数的某种推广。此外，若 $f$ 是 Frechet 可微的，则 $f$ 是 Gateaux 可微的，且二者意义下的梯度相等。

我们主要关注 Gateaux 可微。

利用 Gateaux 可微的定义计算梯度

以下案例中梯度的计算综合运用了变换 $\mathrm{Tr}(A + B) = \mathrm{Tr}(A) + \mathrm{Tr}(B)$、$\mathrm{Tr}(AB) = \mathrm{Tr}(BA)$ 以及 $\| \cdot \|_F$ 的定义。

示例 1：

考虑线性函数 $f(X) = \mathrm{Tr}(AX^\mathrm{T}B)$，其中 $A \in \mathbb{R}^{p \times n}$，$B \in \mathbb{R}^{m \times p}$，$X \in \mathbb{R}^{m \times n}$，则 \begin{aligned} \lim_{t \to 0} \frac{f(X + tV)}{t} &= \frac{\mathrm{Tr}\big(A(X + tV)^\mathrm{T}B\big) - \mathrm{Tr}(AX^\mathrm{T}B)}{t} \\ &= \mathrm{Tr}(AV^\mathrm{T} B) = \langle BA, V \rangle. \end{aligned} 所以 $\nabla f(X) = BA$。

示例 2：

考虑二次函数 $f(X, Y) = \frac{1}{2} \| XY - A \|_F^2$，其中 $(X, Y) \in \mathbb{R}^{m \times p} \times \mathbb{R}^{p \times n}$，则 $$ f(X, Y + tV, Y) - f(X, Y) = t \langle V, (XY - A) Y^\mathrm{T} \rangle + \mathcal{O}(t^2), $$ 所以 $\nabla_Y f(X, Y) = X^\mathrm{T} (XY - A)$。同理 $\nabla_X f(X, Y) = (XY - A) Y^\mathrm{T}$。

示例 3：

考虑 In-det 函数 $f(X) =\ln(\mathrm{det}(X))$，其中 $X \in \mathcal{S}_{++}^n$，则给定 $X \succ 0$，对任意方向 $V \in \mathcal{S}^n$ 以及 $t \in \mathbb{R}$，有 \begin{aligned} &\quad f(X + tV) - f(X) \\ &= \ln\Big(\mathrm{det}\big(X^{1/2}(I + tX^{-1/2}VX^{-1/2})X^{1/2}\big)\Big) - \ln\big(\mathrm{det}(X)\big) \\ &= \ln\Big(\mathrm{det}\big(I + tX^{-1/2}VX^{-1/2}\big)\Big). \qquad \quad \triangleright \quad \mathrm{det}(AB) = \mathrm{det}(A) \mathrm{det}(B) \end{aligned}

对于正定阵 $X^{-1/2}VX^{-1/2}$，因为可以正交对角化 ¹，所以不妨设其特征值为 $\lambda_1, ..., \lambda_n$，则 \begin{aligned} &\quad \ln \Big(\mathrm{det}(I + tX^{-1/2}VX^{-1/2})\Big) = \ln \prod_{i=1}^n (1 + t \lambda_i)\\ &= \sum_{i=1}^n t \lambda_i + \mathcal{O}(t^2) \qquad \triangleright x \to 0: \ln (1 + x) = x + \mathcal{O}(x^2) \\ &= t \mathrm{Tr}(X^{-1/2}VX^{-1/2}) + \mathcal{O}(t^2) \qquad \triangleright \textrm{迹是特征值之和} \\ &= t \langle (X^{-1})^\mathrm{T}, V \rangle + \mathcal{O}(t^2) \qquad \triangleright \nabla f(X) = (X^{-1})^\mathrm{T} \end{aligned}

自动微分

依据微积分中的链式法则，沿着从计算图中输出层到输入层的顺序，依次计算并存储目标函数关于计算图中各层的中间变量以及参数的梯度。第 $l$ 层的误差可由第 $l+1$ 层的误差得到 ²。

图 1 正向传播的计算图示例

广义实值函数

广义实值函数（定义）. 令 $\bar{\mathbb{R}} \triangleq \mathbb{R} \cup \{ \pm \infty \}$ 为广义实数空间，则 $f: \mathbb{R}^n \to \bar{\mathbb{R}}$ 被称为广义实值函数。

适当函数（定义）. 给定广义实值函数 $f$ 和非空集合 $\mathcal{X}$，若 \begin{aligned} \left\{ \begin{array}{l} \exists x \in \mathcal{X}, f(x) < +\infty \\ \forall x \in \mathcal{X}, f(x) > -\infty, \end{array} \right. \end{aligned} 则称 $f$ 是关于 $\mathcal{X}$ 的适当函数（ 否则求 minimum 没有意义 ）。

若无特别指示，接下来及后续文档中提及的 $f$ 均为适当函数，且默认 $\mathbb{R} = \bar{\mathbb{R}}$。

闭函数

$\alpha$- 下水平集（定义）. 对于函数 $f: \mathbb{R}^n \to \mathbb{R}$，称 $$ C_\alpha \triangleq \{x \mid f(x) \leq \alpha \} $$ 为 $f$ 的 $\alpha$- 下水平集。$\alpha$- 下水平集是不超过某个阈值的自变量的集合。

上方图（定义）. 对于函数 $f: \mathbb{R}^n \to \mathbb{R}$，称 $$ \mathbf{epi} f \triangleq \{ (x,t) \in \mathbb{R}^{n+1} \mid f(x) \leq t \} $$ 为 $f$ 的上方图。

图 2 上方图

闭函数（定义）. 对于函数 $f: \mathbb{R}^n \to \mathbb{R}$，若 $\mathbf{epi} f$ 为闭集（集合所有的极限点都是这个集合中的点），则称 $f$ 为闭函数。

下半连续函数（定义）. 对于函数 $f: \mathbb{R}^n \to \mathbb{R}$，若 $\forall x \in \mathbb{R}^n$， $$ \liminf_{y \to x} f(y) \geq f(x), $$ 则称 $f$ 为下半连续函数。

图 3 下半连续函数示例

闭函数和下半连续函数的等价性（定理）. 对于函数 $f: \mathbb{R}^n \to \mathbb{R}$，以下命题等价：

(1) $f$ 的任意 $\alpha$- 下水平集都是闭集；
(2) $f$ 是下半连续的；
(3) $f$ 是闭函数。

证明 .

(2) $\rightarrow$ (3)： 设 $(x_k,y_k) \in \mathbf{epi} f$ 且 $\lim_{k \to \infty} (x_k, y_k) = (\bar{x}, \bar{y})$，则 $$ f(\bar{x}) \leq \liminf_{k \to \infty} f(x_k) \leq \lim_{k \to \infty} y_k = \bar{y}, $$ 这说明 $(\bar{x}, \bar{y}) \in \mathbf{epi} f$，所以 $\mathbf{epi} f$ 是闭集。

(3) $\rightarrow$ (1)： 取 $\alpha$- 下水平集的元素 $x_k \to \bar{x}$，有 $(x_k, \alpha) \in \mathbf{epi}f$ 且 $(x_k, \alpha) \to (\bar{x}, \alpha)$，因为 $f$ 是闭函数，所以必然有 $(\bar{x}, \alpha) \in \mathbf{epi}f$，即 $f(\bar{x}) \leq \alpha$。这说明 $f$ 的任意 $\alpha$- 下水平集都是闭集。

(1) $\rightarrow$ (2)： 反证法。假设存在序列 $\{x_k\} \to \bar{x} (k \to \infty)$ 但 $f(\bar{x}) > \liminf_{k \to \infty} f(x_k)$，取 $t$ 使得 \begin{aligned} f(\bar{x}) > t > \liminf_{k \to \infty} f(x_k). \end{aligned} 根据下极限的定义，$\{x_k \mid f(x_k) \leq t\}$ 中必然含有无穷多个 $x_k$，因此 $\{x_k\}$ 中存在子列 $\{x_{k_l}\}$ 使得 $f(x_{x_l}) \leq t$ 且 $\lim_{x_{k_l}} = \bar{x}$，则 $t$- 下水平集不是闭集，这与命题 $1$ 矛盾。

闭函数间的简单运算会保持原有性质 ：

加法：若 $f$ 和 $g$ 均为闭函数，且 $\mathbf{dom} f \cap \mathbf{dom} g \neq \varnothing$，则 $f+g$ 也是闭函数；
仿射映射的复合 ：若 $f$ 为闭函数，则 $f(Ax + b)$ 也为闭函数；
取上确界 ：若每一个 $f_\alpha$ 均为闭函数，则 $\sup_\alpha f_\alpha (x)$ 也为闭函数。

最后

本文所使用的图片来自北京大学开设的凸优化课程的官方教材。

参见需要熟练掌握的算法理论基础。 ↩
参见反向传播的数学原理 · 深度学习 05。 ↩

转载申请

本作品采用知识共享署名 4.0 国际许可协议进行许可，转载时请注明原文链接。您必须给出适当的署名，并标明是否对本文作了修改。

您也可以通过下方按钮直接分享本页面：