优化理论基础(下) · 最优化 04

关键字最优化理论保凸运算共轭函数凸函数

摘要 —— 本文重点介绍了常用的保凸运算。借助保凸运算,我们可以轻易地判定一个函数是否为凸函数,这直接决定了一个问题是否是“容易求解的”。

上篇重点介绍了凸函数的定义以及一些凸函数的判定方法。实际上,凸函数还可以从凸函数的 “保凸运算” 中得到,本文将重点描述常用的保凸运算。

1 保凸运算

判定一个函数是否是凸函数的方法:

常见的保凸运算列举如下:

(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 与仿射函数复合保凸

2.2 逐点取最大值保凸

2.3 逐点取上确界保凸

2.4 凸函数之间的复合保凸

2.5 取下确界保凸


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$ 的集合。根据 “保凸运算第五条” 可知任意函数的共轭函数都是凸函数。

图 1 对固定的 $y$,$f^*(y)$ 的几何意义

4.1 常见的共轭函数

Fenchel 不等式(定理). $f(x) + f^*(y) \geq x^\mathrm{T}y$(定义显然可得)。

常见函数的共轭函数:

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$ 分类讨论。

最后

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

转载申请

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

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


发表评论

登录以发表评论

最新评论


Designed & written by Hailiang Zhao.
hliangzhao.cn. Copyright © 2021 - 2022 | 浙ICP备2021026965号-1
Manage