优化理论基础（下） · 最优化 04
关键字： 最优化理论 保凸运算 共轭函数 凸函数
上篇重点介绍了凸函数的定义以及一些凸函数的判定方法。实际上，凸函数还可以从凸函数的 “保凸运算” 中得到，本文将重点描述常用的保凸运算。
1 保凸运算
判定一个函数是否是凸函数的方法：
- 凸函数的定义；
- 凸函数判定定理；
- 对可微函数利用一阶条件和二阶条件；
- 判断 $\mathbf{epi}f$ 是否为凸集；
- 由简单凸函数的保凸运算得到 （非负加权和、与仿射函数复合、逐点取最大值等）。
常见的保凸运算列举如下：
（1）$f$ 凸 $\Longrightarrow \forall \alpha \geq 0, \alpha f$ 凸。
（2）$f_1$ 和 $f_2$ 凸 $\Longrightarrow f_1 + f_2$ 凸。
（3）$f$ 凸 $\Longrightarrow f(Ax + b)$ 凸。
（4）$f_1, f_2, ..., f_m$ 凸 $\Longrightarrow f(x) = \max { f_1(x), f_2(x), ..., f_m(x) }$ 凸。
（5）$\forall y \in \mathcal{A}, f(x,y)$ 关于 $x$ 凸 $\Longrightarrow g(x) \triangleq \sup_{y \in \mathcal{A}} f(x, y)$ 凸。
简要证明 . $\mathbf{epi} g = \bigcap_{y \in \mathcal{A}} \mathbf{epi}f(\cdot, y)$ 作为多个凸集的交集仍然是凸集。
（6）$g: \mathbb{R}^n \to \mathbb{R}$ 凸 & $h: \mathbb{R} \to \mathbb{R}$ 凸且单调不减 $\Longrightarrow f(x) \triangleq h(g(x))$ 凸。
（7）$g: \mathbb{R}^n \to \mathbb{R}$ 凹 & $h: \mathbb{R} \to \mathbb{R}$ 凸且单调不增 $\Longrightarrow f(x) \triangleq h(g(x))$ 凸。
（8）给定 $g: \mathbb{R}^n \to \mathbb{R}^k, h: \mathbb{R}^k \to \mathbb{R}$， \begin{aligned} f(x) = h(g(x)) = h(g_1(x), ..., g_k(x)). \end{aligned}
$g_i$ 凸 & $h$ 凸且关于每个分量单调不减 $\Longrightarrow f$ 凸；
$g_i$ 凹 & $h$ 凸且关于每个分量单调不增 $\Longrightarrow f$ 凸。
简要证明 . 根据 $g$ 的定义可得 \begin{aligned} f(x_i, y_i) \leq g(x_i) + \varepsilon, \forall i = 1, 2. \end{aligned}
因此 \begin{aligned} g(\theta x_1 &+ (1 - \theta) x_2) = \inf_{y \in C} f(\theta x_1 + (1 - \theta) x_2, y) \\ &\leq f(\theta x_1 + (1 - \theta) x_2, \theta y_1 + (1 - \theta) y_2) \quad \triangleright C\textrm{是凸集}\\ &\leq \theta f(x_1, y_1) + (1 - \theta) f(x_2, y_2) \quad \triangleright f\textrm{是凸的}\\ &\leq \theta g(x_1) + (1 - \theta) g(x_2) + \varepsilon. \end{aligned} 最后令 $\varepsilon \to 0$ 即可。
（9）定义函数 $f: \mathbb{R}^n \to \mathbb{R}$ 的透视函数 $g: \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}$， \begin{aligned} g(x, t) = t f\Big(\frac{x}{t}\Big), \quad \mathbf{dom} g = \Big\{ (x, t) \mid \frac{x}{t} \in \mathbf{dom}f, t > 0 \Big \} \end{aligned} 若 $f$ 是凸函数，则 $g$ 是凸函数。
简要证明 . 带入凸函数的定义即可证明。
2 保凸运算示例
2.1 与仿射函数复合保凸
- 线性不等式的 “对数障碍函数”： \begin{aligned} f(x) = - \sum_{i=1}^m \ln \big( b_i - a_i^\mathrm{T} x \big), \quad \mathbf{dom}f = \{ x \mid a_i^\mathrm{T}x < b_i, i = 1, ..., m \} \end{aligned} 是凸函数。
- 仿射函数的 “任意范数”$f(x) = \| Ax + b \|$ 都是凸函数。
2.2 逐点取最大值保凸
- 分段线性函数 $f(x) = \max_{i=1, .., m} \Big( a_i^\mathrm{T} x + b \Big)$ 是凸函数。
- $x \in \mathbb{R}^n$ 的前 $r$ 个 “最大分量之和” \begin{aligned} f(x) = \max \bigg \{ \sum_{i=i_1}^{i_r} x_i \mid 1 \leq i_1 < ... < i_r \leq n \bigg \} \end{aligned} 是凸函数。
2.3 逐点取上确界保凸
- 集合 $C$ 的支撑函数 \begin{aligned} S_C(x) = \sup_{y \in C} y^\mathrm{T}x \end{aligned} 是凸函数。
- 集合 $C$ 的点到给定点 $x$ 的最远距离 \begin{aligned} f(x) = \sup_{y \in C} \| x - y \| \end{aligned} 是凸函数。
- 求对称阵的最大特征值 \begin{aligned} \lambda_{\textrm{max}} (X) = \sup_{\| y \|_2 = 1} y^\mathrm{T} X y, \quad X \in \mathcal{S}^n \end{aligned} 是凸函数。
2.4 凸函数之间的复合保凸
- $g(x)$ 凸 $\Longrightarrow \exp(g(x))$ 凸。
- $g(x)$ 是正值凹函数 $\Longrightarrow \frac{1}{g(x)}$ 是凸函数。
- $g(x)$ 是正值凹函数 $\Longrightarrow \sum_{i=1}^m \ln (g_i(x))$ 是凹函数。
- $g_i(x)$ 凸 $\Longrightarrow \ln \sum_{i=1}^m \exp (g_i (x))$ 凸。
2.5 取下确界保凸
- 对于函数 $f(x, y) = x^\mathrm{T}Ax + 2x^\mathrm{T}By + y^\mathrm{T}Cy$， 其中 $A \in \mathcal{S}^m, C \in \mathcal{S}^n, B \in \mathbb{R}^{m \times n}$（这其实是一个二次型，$(x, y) \to x'$）。其海瑟矩阵若满足 \begin{aligned} \left[ \begin{matrix} A & B \\ B^\mathrm{T} & C \end{matrix} \right] \succeq 0, \quad {\color{red}C \succ 0}, \end{aligned} 则 $f(x, y)$ 为凸函数。对 $y$ 求最小值得（求导得 $y^* = - C^{-1}B^\mathrm{T} x$） \begin{aligned} g(x) = \inf_{y} f(x, y) = x^\mathrm{T} (A - BC^{-1}B^\mathrm{T} )x, \end{aligned} 根据 $f(x,y)$ 的海瑟矩阵满足的条件可以得到 $(A - BC^{-1}B^\mathrm{T}) \succeq 0$，因此 $g$ 是凸函数。
- 点 $x$ 到凸集 $\mathcal{C}$ 的最短距离 $\textrm{dist}(x, \mathcal{C}) = \inf_{y \in \mathcal{C}} \| x - y \|$ 是凸函数。
3 凸函数的性质
连续性（定理）. 设 $f: \mathbb{R}^n \to (-\infty, +\infty]$ 为凸函数。对任意点 $x_0 \in \mathbf{int}\mathbf{dom}f$，有 $f$ 在点 $x_0$ 处连续。 这里 $\mathbf{int dom}f$ 表示定义域 $\mathbf{dom}f$ 的内点一个点是某个集合的内点当且仅当存在以该点为中心的开球 / 邻域被包含于本集合）。
这表明凸函数在定义域的内点处连续，可以认为凸函数 “差不多是连续的”。这一定理可直接得到如下推论：
连续性'（定理）. 设 $f(x)$ 是凸函数，且 $\mathbf{dom}f$ 是开集，则 $f(x)$ 在 $\mathbf{dom}f$ 上是连续的。
凸下水平集（定理）. 设 $f(x)$ 是凸函数，则 $f(x)$ 所有的 $\alpha$- 下水平集 $C_\alpha$ 为凸集。
证明 . 任取 $x_1, x_2 \in C_\alpha$，对任意的 $\theta \in (0,1)$ 有 \begin{aligned} f\big(\theta x_1 + (1 - \theta) x_2\big) &\leq \theta f(x_1) + (1-\theta) f(x_2) \\ &\leq \theta \alpha + (1 - \theta) \alpha = \alpha. \end{aligned}
本命题的逆命题不成立。
二次下界（定理）. 设 $f(x)$ 是参数为 $m$ 的可微强凸函数，则 \begin{aligned} f(y) \geq f(x) + \nabla f(x)^\mathrm{T} (y - x) + \frac{m}{2} \| y - x \|^2, \quad \forall x, y \in \mathbf{dom}f. \end{aligned}
证明 . 结合强凸函数的定义和一阶条件可证。令 $g(x) = f(x) - \frac{m}{2} \|x\|^2$，则对 $g(x)$ 运用一阶条件可得 \begin{aligned} f(y) - \frac{m}{2} \| y \|^2 \geq f(x) - \frac{m}{2} \| x \|^2 + (\nabla f(x) - mx)^\mathrm{T} (y - x). \end{aligned}
下水平集有界（定理）. 设 $f(x)$ 是可微强凸函数，则 $f$ 的所有 $\alpha$- 下水平集都有界。
证明 . 取 $x \in C_\alpha, y \in C_\beta$ 带入上式则 $\beta$ 有下界。
4 共轭函数
共轭函数（定义）. 任意（适当）函数 $f$ 的共轭函数定义为 \begin{aligned} f^*(y) = \sup_{x \in \mathbf{dom}f} \big\{ y^\mathrm{T} x - f(x) \big\}. \end{aligned}
我们关心共轭函数是因为 引入拉格朗日乘子法和对偶问题之后，一定会出现此式 。 $f^*(y)$ 是广义实值函数，可取到正无穷。因此我们规定 $\mathbf{dom}f^*$ 为使得 $f^*(y)$ 有限的 $y$ 的集合。根据 “保凸运算第五条” 可知任意函数的共轭函数都是凸函数。
4.1 常见的共轭函数
Fenchel 不等式（定理）. $f(x) + f^*(y) \geq x^\mathrm{T}y$（定义显然可得）。
常见函数的共轭函数：
-
对于二次函数 $f(x) = \frac{1}{2}x^\mathrm{T} A x + b^\mathrm{T}x + c$，
（1）若 $f$ 强凸（$A \succ 0$）： \begin{aligned} f^*(y) = \frac{1}{2} (y -b)^\mathrm{T} A^{-1} (y - b) - c \end{aligned}
（带入 $x^* = -A^{-1}(y-b)$ 得到）
（2）若 $f$ 一般凸（$A \succeq 0$）： \begin{aligned} f^*(y) = \frac{1}{2} (y - b)^\mathrm{T} A^+ (y - b) - c, \quad \mathbf{dom} f^* = \mathcal{R}(A) + b. \end{aligned} 这里 $A^+$ 是 $A$ 的 Moore-Penrose 逆，$\mathcal{R}(A) = \{ Ax \mid x \in \mathbf{dom}f \}$ 是 $A$ 的像空间。
-
凸集的示性函数 ：给定凸集 $C$，其示性函数为 \begin{aligned} I_C(x) = \left\{ \begin{array}{ll} 0 & x \in C \\ +\infty & x \notin C. \end{array} \right. \end{aligned} 则 \begin{aligned} I_C^*(y) = \sup_{x} \{ y^\mathrm{T}x - I_C(x) \} = \sup_{x \in C} y^\mathrm{T}x. \end{aligned} 又称 $I_C^*(y)$ 为凸集 $C$ 的支撑函数。
-
范数 ：范数的共轭函数为其 “单位对偶范数球” 的示性函数，即若 $f(x) = \| x \|$，则 \begin{aligned} f^*(y) = \left\{ \begin{array}{ll} 0 & \| y \|_* \leq 1 \\ +\infty & \| y \|_* > 1, \end{array} \right. \end{aligned} 其中对偶范数 $\| y \|_* \triangleq \sup_{\| x \| \leq 1} x^\mathrm{T}y$。
分类讨论 ：
- 若 $\| y \|_* \leq 1$，则结合柯西不等式可得 $y^\mathrm{T}x \leq \| x \|$ 对任意 $x$ 成立（在 $x = 0$ 时取等）。 从而 $\sup_{x \in \mathbf{dom}f} { y^\mathrm{T}x =- | x |} = 0$。
- 若 $| y |_* > 1$，则至少存在一个 $x$ 使得 $\| x \| \leq 1$ 且 $x^\mathrm{T}y > 1$。从而对任意 $t>0$ 有 \begin{aligned} f^*(y) \geq y^\mathrm{T} (tx) - \| tx \| = t(y^\mathrm{T}x - \| x \|). \end{aligned} 显然 $t \to \infty$ 时右端 $\to \infty$。
4.2 二次共轭函数
二次共轭函数（定义）. 任意函数 $f$ 的二次共轭函数定义为 \begin{aligned} f^{**}(x) = \sup_{y \in \mathbf{dom}f^*} \{ x^\mathrm{T}y - f^*(y) \}. \end{aligned} 根据闭函数之间简单运算的保闭性以及任意函数的共轭函数的凸性可知 $f^{**}(x)$ 恒为 闭凸函数 。由 Fenchel 不等式可知 $\forall x$， \begin{aligned} f^{**}(x) \leq \sup_{y \in \mathbf{dom}f^*} \{ x^\mathrm{T}y + f(x) - x^\mathrm{T}y \} = f(x). \end{aligned} 等价地，$\mathbf{epi} f \subseteq \mathbf{epi}f^{**}$。
二次共轭函数与原函数的等价性（定理）. 若 $f$ 为闭凸函数，则 \begin{aligned} f^{**}(x) = f(x), \forall x. \end{aligned} 等价地，$\mathbf{epi}f^{**} = \mathbf{epi}f$。
证明 . 因为对任意 $x$ 有 $f^{**}(x) \leq f(x)$，所以只要同时有 $\forall x, f^{**}(x) \geq f(x)$ 即可得证。采用反证法：假设存在 $x$ 使得 $(x, f^{**}(x)) \notin \mathbf{epi}f$， 则必然存在严格分割超平面使得 \begin{aligned} \left[ \begin{matrix} a \\ b \end{matrix} \right]^\mathrm{T} \left[ \begin{matrix} z - x \\ s - f^{**}(x) \end{matrix} \right] \leq c <0, \quad \forall (z, s) \in \mathbf{epi}f， \end{aligned} 且 $a \in \mathbb{R}^n, b, c \in \mathbb{R}, b \leq 0$（$b > 0$ 则 $s \to \infty$ 时矛盾）。 这个式子由 $\left\{ \begin{array}{ll} a^\mathrm{T} x < b & \forall x \in C \triangleq \mathbf{epi}f \\ a^\mathrm{T} x > b & \quad \end{array} \right.$ 相减得到。
接下来对 $b$ 分类讨论。
-
若 $b <0$，取 $s = f(z)$ 并用 $y$ 替换 $-\frac{a}{b}$ 代入上述不等式可得 \begin{aligned} f^*(y) - y^\mathrm{T}x + f^{**}(x) \leq -\frac{c}{b} < 0 \end{aligned} 这与 Fenchel 不等式矛盾。
-
若 $b = 0$，取 $\hat{y} \in \mathbf{dom}f^*$ 并给 $\left[ \begin{matrix} a \\ b \end{matrix} \right]$ 加上一个 $\left[ \begin{matrix} \hat{y} \\ -1 \end{matrix} \right]$ 的 $\varepsilon$ 倍（$\varepsilon > 0$），得 \begin{aligned} \left[ \begin{matrix} a + \varepsilon \hat{y} \\ -\varepsilon \end{matrix} \right]^\mathrm{T} \left[ \begin{matrix} z - x \\ s - f^{**}(x) \end{matrix} \right] \leq c + \varepsilon \big(f^*(\hat{y}) - \hat{y}^\mathrm{T}x + f^{**}(x)\big) < 0, \end{aligned} 这化归成了 $b < 0$ 的情况，遵循相同的步骤，从而得出矛盾。
最后
本文所使用的图片来自北京大学开设的凸优化课程的官方教材。
转载申请
本作品采用 知识共享署名 4.0 国际许可协议 进行许可， 转载时请注明原文链接。您必须给出适当的署名，并标明是否对本文作了修改。
您也可以通过下方按钮直接分享本页面：
还没有评论...