最优化方法(3) —

基本线性代数知识

定义 给定函数 $f: \mathbb{R}^n \mapsto \mathbb{R}$, 且 $f$ 在 $x$ 一个邻域内有定义, 若存在 $g \in \mathbb{R}^n$, 使得 $$ \lim_{p \to 0} \frac{f(x+p)-f(x)-g^\top p}{\Vert p \Vert} = 0 $$其中 $\Vert \cdot \Vert$ 是向量范数, 则称 $f$ 在 $x$ 处 可微. 此时, $g$ 称为 $f$ 在 $x$ 处的 梯度, 记为 $\nabla f(x)$.

显然, 如果梯度存在, 令 $p = \varepsilon e_i$, 易得

$$ \nabla f(x) = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n} \right) $$

定义 如果函数 $f(x): \mathbb{R}^n \mapsto \mathbb{R}$ 在点 $x$ 处的二阶偏导数 $\dfrac{\partial^2 f}{\partial x_i \partial x_j}$ 存在, 则称 $f$ 在 $x$ 处 二次可微. 此时, $n \times n$ 矩阵 $$ \nabla^2 f(x) = \begin{pmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1 \partial x_n} \\ \dfrac{\partial^2 f}{\partial x_2 \partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2 \partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \dfrac{\partial^2 f}{\partial x_n \partial x_1} & \dfrac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{pmatrix} $$称为 $f$ 在 $x$ 处的 Hessian 矩阵. 若 $\nabla^2 f(x)$ 在 $D$ 上连续, 则称 $f$ 在 $D$ 上 二次连续可微.

可以证明, 若 $f$ 在 $D$ 上二次连续可微, 则 $\nabla^2 f(x)$ 为对称矩阵.

多元函数的梯度可以推广到变量是矩阵的情形.

定义 给定函数 $f: \mathbb{R}^{m \times n} \mapsto \mathbb{R}$, 且 $f$ 在 $X$ 一个邻域内有定义, 若存在 $G \in \mathbb{R}^{m \times n}$, 使得 $$ \lim_{V \to 0} \frac{f(X+V)-f(X)-\left< G, V \right>}{\Vert V \Vert} = 0 $$其中 $\Vert \cdot \Vert$ 是矩阵范数, 则称 $f$ 在 $X$ 处 (Fréchet)可微. 此时, $G$ 称为 $f$ 在 $X$ 处的 梯度, 记为 $\nabla f(X)$.

矩阵的可微有另一种较为简单常用的定义.

定义 给定函数 $f: \mathbb{R}^{m \times n} \mapsto \mathbb{R}$, 若存在矩阵 $G \in \mathbb{R}^{m \times n}$, 使得 $$ \lim_{t \to 0} \frac{f(X+tV)-f(X)}{t} = \left< G, V \right> $$则称 $f$ 在 $X$ 处 (Gâteaux)可微.

例如:

$f(X) = \mathrm{tr}(AX^\top B)$, 此时 $\nabla f(X) = BA$.
$f(X, Y)=\frac{1}{2} \Vert XY-A \Vert_F^2$. 此时
$$ \begin{aligned} &f(X,Y+tV)-f(X,Y) \\ &= \frac{1}{2} \Vert X(Y+tV)-A \Vert_F^2 - \frac{1}{2} \Vert XY-A \Vert_F^2 \\ &= \frac{1}{2} \Vert XY - A + tVX \Vert_F^2 - \frac{1}{2} \Vert XY - A \Vert_F^2 \\ &= \frac{1}{2} \Vert tVX \Vert_F^2 + \left< XY-A, tVX \right> \\ &= t \left< X^\top (XY-A), V \right> + o(t) \end{aligned} $$
所以 $\frac{\partial f}{\partial Y} = X^\top (XY-A)$, 类似地, $\frac{\partial f}{\partial X} = (XY-A)Y^\top $.
$f(X)=\ln\mathrm{det}(X)$, $X$ 为正定矩阵. 此时
$$ \begin{aligned} &f(X+tV)-f(X) \\ &= \ln\mathrm{det}(X+tV) - \ln\mathrm{det}(X) \\ &= \ln\mathrm{det}(I+tX^{-1/2}VX^{-1/2}) \end{aligned} $$
考虑 $X^{-1/2}VX^{-1/2}$ 的特征值 $\lambda_i$, 则由特征值之和为迹, 有
$$ \begin{aligned} &= \ln\mathrm{det}\prod_{i=1}^n (1+t\lambda_i) \\ &= \sum_{i=1}^n \ln(1+t\lambda_i) \\ &= \sum_{i=1}^n t\lambda_i + o(t) \\ &= t\mathrm{tr}(X^{-1/2}VX^{-1/2}) + o(t) \\ &= t\mathrm{tr}(X^{-1}V) + o(t) \\ &= t\left< X^{-\top}, V \right> + o(t) \end{aligned} $$
所以 $\nabla f(X) = X^{-\top}$.

定义 广义实数 是一种扩充实数域的数, 记为 $\bar{\mathbb{R}} = \mathbb{R} \cup \{ \pm \infty \}$. 映射 $f: \mathbb{R}^n \mapsto \bar{\mathbb{R}}$ 称为 广义实值函数.

定义 给定广义实值函数 $f$ 和非空集合 $X$. 如果存在 $x \in X$ 使得 $f(x) < +\infty$, 并且对任意的 $x \in X$, 都有 $f(x) > -\infty$, 那么称函数 $f$ 关于集合 $X$ 是 适当的．

定义 对于广义实值函数 $f: \mathbb{R}^n \mapsto \bar{\mathbb{R}}$, $C_\alpha = \{x \mid f(x) \le \alpha \}$ 称为 $f$ 的 $\alpha$-下水平集. $\mathrm{epi} f = \{ (x, t) \mid f(x) \le t \}$ 称为 $f$ 的 上方图. 若 $\mathrm{epi} f$ 为闭集, 则称 $f$ 为闭函数. 若对任意的 $x \in \mathbb{R}^n$, 有 $\liminf_{y \to x} f(y) \ge f(x)$, 则称 $f$ 为 下半连续函数.

定理 对于广义实值函数 $f$, 以下命题等价: $f(x)$ 的任意 $\alpha$-下水平集都是闭集; $f(x)$ 是下半连续的; $f(x)$ 是闭函数. 证明 (1) $\Rightarrow$ (2): 反证, 假设 $x_k \to \bar{x}$ 但 $\liminf_{k \to \infty} f(x_k) < f(\bar{x})$. 取 $t$ 介于二者之间. 考虑到 $\liminf_{k \to \infty} f(x_k) < t$, 则有无穷多 $x_k$ 使得 $f(x_k) \le t$, 即这些 $x_k$ 在 $C_t$ 中. 由于 $C_t$ 是闭集, 则 $\bar{x} \in C_t$, 即 $f(\bar{x}) \le t$, 矛盾. (2) $\Rightarrow$ (3): 考虑 $(x_k,y_k) \in \mathrm{epi} f \to (\bar{x},\bar{y})$, 由于 $f$ 下半连续, 则 $$ f(\bar{x}) \le \liminf_{k \to \infty} f(x_k) = \liminf_{k \to \infty} y_k = \bar{y} $$即 $(\bar{x}, \bar{y}) \in \mathrm{epi} f$. (3) $\Rightarrow$ (1): 考虑 $x_k \in C_\alpha \to \bar{x}$, 则 $(x_k, \alpha) \in \mathrm{epi} f \to (\bar{x}, \alpha)$, 所以 $(\bar{x}, \alpha) \in \mathrm{epi} f$, 即 $f(\bar{x}) \le \alpha$, 所以 $\bar{x} \in C_\alpha$.

适当闭函数的和, 复合, 逐点上确界仍然是闭函数.

凸函数

定义 适当函数 $f: \mathbb{R}^n \mapsto \mathbb{R}$ 称为 凸函数, 如果 $\mathrm{dom} f$ 是凸集, 且对任意的 $x, y \in \mathrm{dom} f$ 和 $\theta \in [0,1]$, 有 $$ f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y) $$

易知仿射函数既是凸函数又是凹函数. 所有的范数都是凸函数.

定义 若存在常数 $m > 0$, 使得 $g(x) = f(x) - \frac{m}{2} \Vert x \Vert^2$ 是凸函数, 则称 $f$ 是 强凸函数, $m$ 称为 强凸参数.

定理凸函数判定定理 适当函数 $f: \mathbb{R}^n \mapsto \mathbb{R}$ 是凸函数的充要条件是, 对任意的 $x \in \mathrm{dom} f$, 函数 $g: \mathbb{R} \mapsto \mathbb{R}$ 是凸函数, 其中 $$g(t) = f(x+tv), \quad \mathrm{dom}g = \{ t \mid x + tv \in \mathrm{dom} f \}$$

定理一阶条件 对于定义在凸集上的可微函数 $f$, $f$ 是凸函数当且仅当 $$ f(y) \ge f(x) + \nabla f(x)^\top (y-x), \quad \forall x, y \in \mathrm{dom} f $$证明 必要性: 设 $f$ 凸, 则 $\forall x, y \in \mathrm{dom} f, t \in [0,1]$, 有 $$tf(y)+(1-t)f(x) \ge f(x+t(y-x))$$令 $t \to 0$, 即 $$f(y)-f(x) \ge \frac{f(x+t(y-x))-f(x)}{t} \to \nabla f(x)^\top (y-x)$$充分性: $\forall x, y \in \mathrm{dom}f, t\in (0,1)$, 取 $z = tx+(1-t)y$, 则 $$ \begin{aligned} f(x) &\ge f(z) + \nabla f(z)^\top (x-z) \\ f(y) &\ge f(z) + \nabla f(z)^\top (y-z) \end{aligned} $$一式乘以 $t$, 二式乘以 $1-t$, 相加即得.

定理梯度单调性 设 $f$ 为可微函数, 则 $f$ 为凸函数当且仅当 $\mathrm{dom} f$ 为凸集且 $\nabla f$ 为单调映射. $$(\nabla f(x) - \nabla f(y))^\top (x-y) \ge 0$$证明 必要性: 根据一阶条件, 有 $$ \begin{aligned} f(y) &\ge f(x) + \nabla f(x)^\top (y-x) \\ f(x) &\ge f(y) + \nabla f(y)^\top (x-y) \end{aligned} $$相加即可. 充分性: 考虑 $g(t)=f(x+t(y-x))$, 则 $g^\prime(t)=\nabla f(x+t(y-x))^\top (y-x)$, 从而 $g^\prime (t) \ge g^\prime (0)$. $$ \begin{aligned} f(y) &= g(1) = g(0) + \int_{0}^1 g^\prime(t) dt \\ &\ge g(0) + \int_{0}^1 g^\prime(0) dt = g(0) + g^\prime(0) \\ &= f(x) + \nabla f(x)^\top (y-x) \end{aligned} $$

定理 函数 $f(x)$ 是凸函数当且仅当 $\mathrm{epi}f$ 是凸集.

定理二阶条件 设 $f$ 为定义在凸集上的二阶连续可微函数, $f$ 是凸函数当且仅当 $\nabla^2 f(x) \succeq 0, \forall x \in \mathrm{dom} f$. 若不取等, 则为严格凸函数. 证明 必要性: 反设 $f(x)$ 在 $x$ 处 $\nabla^2 f(x) \prec 0$, 则存在 $v \in \mathbb{R}^n$, 使得 $V^\top \nabla^2 f(x) v < 0$, 考虑 Peano 余项 $$ f(x+tv)=f(x)+t\nabla f(x)^\top v+\frac{t^2}{2}V^\top \nabla^2 f(x+tv)v + o(t^2) $$取 $t$ 充分小, $$ \frac{f(x+tv)-f(x)-t\nabla f(x)^\top v}{t^2}=\frac{1}{2}V^\top \nabla^2 f(x+tv)v + o(1) < 0 $$这和一阶条件矛盾. 充分性: 对于任意的 $x, y \in \mathrm{dom} f$, 有 $$ \begin{aligned} f(y) &= f(x)+\nabla f(x)^\top (y-x)+\frac{1}{2}(y-x)^\top \nabla^2 f(z)(y-x) \\ &\ge f(x)+\nabla f(x)^\top (y-x) \end{aligned} $$由一阶条件, $f$ 为凸函数.

保凸运算

下面举一些重要的例子.

逐点取上界: 若对每个 $y \in A$, $f(x,y)$ 都是关于 $x$ 的凸函数, 则
$$g(x)=\sup_{y \in A} f(x,y)$$
也是凸函数.
- $C$ 的支撑函数 $f(x)=\sup_{y \in C} y^\top x$ 是凸函数.
- $C$ 到 $x$ 的最远距离 $f(x)=\sup_{y \in C} \Vert x-y \Vert$ 是凸函数.
- 对称阵 $X \in \mathbb{S}^n$ 的最大特征值 $\lambda_{\max}(X)=\sup_{\Vert x \Vert=1} x^\top Xx$ 是凸函数.
标量函数的复合: 若 $g: \mathbb{R}^n \mapsto \mathbb{R}$ 是凸函数, $h: \mathbb{R} \mapsto \mathbb{R}$ 是单调不减的凸函数, 则
$$f(x) = h(g(x))$$
也是凸函数. 凹同理.
- 如果 $g$ 凸, 则 $f(x) = \exp(g(x))$ 也是凸函数.
- 如果 $g$ 凹, 则 $f(x) = 1/g(x)$ 也是凸函数.
取下确界: 若 $f(x, y)$ 关于 $(x, y)$ 整体是凸函数, $C$ 是凸集, 则
$$g(x) = \inf_{y \in C} f(x, y)$$
也是凸函数.
- 凸集 $C$ 到 $x$ 的距离 $f(x)=\inf_{y \in C} \Vert x-y \Vert$ 是凸函数.
透视函数: 若 $f: \mathbb{R}^{n} \mapsto \mathbb{R}$ 是凸函数, 则
$$g(x, t) = tf(x/t), \quad \mathrm{dom} g = \{ (x, t) \mid x / t \in \mathrm{dom} f, t > 0 \}$$
也是凸函数.
- 相对熵函数 $g(x,t)=t\log t-t\log x$ 是凸函数.
- 若 $f$ 凸, 则 $g(x)=(c^\top +d)f((Ax+b)/(c^\top +d))$ 也是凸函数.
共轭函数: 任意适当函数 $f$ 的共轭函数
$$f^\ast(y)=\sup_{x \in \mathrm{dom} f} (\left< x, y \right> - f(x))$$
是凸函数.

凸函数的推广

定义 $f: \mathbb{R}^n \mapsto \mathbb{R}$ 称为 拟凸的, 如果 $\mathrm{dom} f$ 是凸集, 且对任意 $\alpha$, 下水平集 $C_\alpha$ 是凸集. 若 $f$ 是拟凸的, 则称 $-f$ 是 拟凹的. 若 $f$ 既是拟凸又是拟凹的, 则称 $f$ 是 拟线性的.

注意: 拟凸函数的和不一定是拟凸函数.

定理 拟凸函数满足类 Jenson 不等式: 对拟凸函数 $f$ 和 $\forall x, y \in \mathrm{dom} f, \theta \in [0,1]$, 有 $$f(\theta x + (1-\theta)y) \le \max\left\{f(x),f(y)\right\}$$ 拟凸函数满足一阶条件: 定义在凸集上的可微函数 $f$ 拟凸当且仅当 $$f(y) \le f(x) \Rightarrow \nabla f(x)^\top (y-x) \le 0$$

定义 如果正值函数 $f$ 满足 $\log f$ 是凸函数, 则 $f$ 称为 对数凸函数; 若为凹函数, 则 $f$ 称为 对数凹函数.

例如, 正态分布

$$f(x) = \frac{1}{\sqrt{(2\pi)^n \mathrm{det} \Sigma}} \exp\left(-\frac{1}{2}(x-\mu)^\top \Sigma^{-1}(x-\mu)\right)$$

是对数凹函数.

对数凹函数的乘积, 积分都是对数凹的, 但加和不一定是对数凹的.

在广义不等式下, 也可以定义凸凹性.

定义 $f: \mathbb{R}^n \mapsto \mathbb{R}^m$ 称为 $K$-凸函数, 如果 $\mathrm{dom} f$ 是凸集, 且 $$f(\theta x+(1-\theta)y \preceq_K \theta f(x)+(1-\theta)f(y))$$ 对任意 $x,y \in \mathrm{dom} f, 0 \le \theta \le 1$ 成立.

例如, $f: \mathbb{S}^m \mapsto \mathbb{S}^m$, $f(X)=X^2$ 是 $\mathbb{S}^m_+$-凸函数. 这点利用 $z^\top X^2z=\Vert Xz \Vert^2$ 是关于 $X$ 的凸函数即可得知.