优化理论基础(中) · 最优化 03

关键字最优化理论仿射集凸集仿射包凸锥超平面半空间多面体保凸运算分离超平面支撑超平面凸函数

摘要 —— 接上篇,本文首先介绍凸优化中的常用概念,包括直线、仿射集、凸集、凸组合、凸函数等,然后重点分析了各种保凸规则和凸性判定规则。

本文将介绍凸优化领域内最重要的数个概念,尤其是凸集和凸函数。我们关心集合和函数的 “凸性” 是因为它让最值的求解有了理论保证。正因如此, 本文将重点阐述了一些判定凸性的规则和方法。

1 直线与仿射集

直线(定义). 对于 $\mathbb{R}^n$ 中的两个点 $x_1$ 和 $x_2$,形如 \begin{aligned} y = \theta x_1 + (1 - \theta) x_2 \end{aligned} 的点组成了过点 $x_1$ 和 $x_2$ 的直线。当 $0 \leq \theta \leq 1$ 时,这样的点形成了连接点 $x_1$ 和 $x_2$ 的 线段

仿射集(定义). 若过集合 $C$ 中任意两点的 直线 都在 $C$ 内,则称 $C$ 为仿射集,即 $$ x_1, x_2 \in C \quad \Longrightarrow \quad \theta x_1 + (1 - \theta) x_2 \in C, \forall \theta \in \mathbb{R}. $$

2 凸集

凸集(定义). 若过集合 $C$ 中任意两点的 线段 都在 $C$ 内,则称 $C$ 为凸集,即 $$ x_1, x_2 \in C \quad \Longrightarrow \quad \theta x_1 + (1 - \theta) x_2 \in C, \forall \theta \in [0, 1]. $$ 显然,仿射集都是凸集。

图 1 (a) 为凸集,(b)、(c) 为非凸集

3 凸组合与凸包

凸组合(定义). 对于给定的点 $x_1, ..., x_k$,$\forall \theta_i \geq 0, \sum_i {\theta_i} = 1$,形如 $$ x = \sum_{i=1}^k \theta_i x_i $$ 的点称为 $x_1, ..., x_k$ 的凸组合。

凸包(定义). 集合 $\mathcal{S}$ 中的点所有可能的凸组合构成的集合称作 $\mathcal{S}$ 的凸包,记为 $\mathbf{conv}\mathcal{S}$。

图 2 离散点集和扇形的凸包

凸组合是凸集定义的扩展——从两个点扩展到多个点。

4 仿射包

去掉凸组合的定义中的 $\forall \theta_i \geq 0$ 的限制,即可得到仿射包的概念。

仿射包(定义). 设 $\mathcal{S}$ 为 $\mathbb{R}^n$ 的子集,则称 $$ \Big\{x \mid x = \sum_{i=1}^k \theta_i x_i, \quad x_1, ..., x_k \in \mathcal{S}, \sum_{\theta_i} = 1 \Big\} $$ 为集合 $\mathcal{S}$ 的仿射包,记为 $\mathbf{affine \mathcal{S}}$。

图 3 $\mathbb{R}^n$ 中的圆盘 $\mathcal{S}$ 的仿射包是一个平面

$\mathbf{affine}\mathcal{S}$ 是包含 $\mathcal{S}$ 的最小的仿射集。

5 锥组合与凸锥

锥组合(定义). 形如 $x = \theta_1 x_1 + \theta_2 x_2, \theta_1 > 0, \theta_2 > 0$ 的点称为点 $x_1,x_2$ 的锥组合。

凸锥(定义). 若集合 $\mathcal{S}$ 中任意点的锥组合都在 $\mathcal{S}$ 中,则称 $\mathcal{S}$ 为凸锥。

图 4 凸锥

6 重要的凸集

6.1 超平面与半空间

其中 $a$ 是对应超平面和半空间的法向量。一个超平面将 $\mathbb{R}^n$ 分为两个半空间。 显然,超平面是仿射集和凸集,半空间是凸集但不是仿射集(因为一端封闭)。

图 5 超平面和半空间

6.2 球、椭球和锥

以上定义中使用的是 $l_2$ 范数,因此得到的都是欧几里得空间的距离。如果不限制范数的类型,即 $\| \cdot \|$ 是任意一个范数,则称 $\{x \mid \| x - x_c \| \leq r \}$ 是中心为 $x_c$,半径为 $r$ 的 范数球 ,称 $\{(x,t) \mid \|x\| \leq t\}$ 为范数锥。 欧几里得范数锥也称为 二次锥

6.3 多面体和半正定锥

图 6 二维半正定锥 $\mathcal{S}_+^2$

7 凸集的保凸运算

证明一个集合是凸集的方法:(1)定义;(2)简单凸集的保凸运算。 常用的保凸元算是 “取交集” 和“仿射变换”(缩放、平移、投影)。

取交集保凸(定理). 任意多个凸集的交为凸集。即,若 $C_i, i \in \mathcal{I}$ 是凸集,则 $$ \bigcap_{i \in \mathcal{I}} C_i $$ 为凸集。这里不要求指标集 $\mathcal{I}$ 可列。

仿射变换保凸(定理). 设 $f: \mathbb{R}^n \to \mathbb{R}$ 是仿射变换 $f(x) = Ax + b$,则

8 分离超平面

超平面可以分离不相交的凸集。

分离超平面定理(定理). 如果 $C$ 和 $D$ 是两个不相交的凸集,则存在非零向量 $a$ 和常数 $b$,使得 \begin{aligned} \left\{ \begin{array}{ll} a^\mathrm{T} x \leq b & \forall x \in C \\ a^\mathrm{T} x \geq b & \forall x \in D. \end{array} \right. \end{aligned} 即超平面 $\{x \mid a^\mathrm{T} x = b\}$ 分离了 $C$ 和 $D$。

图 7 分离超平面

9 支撑超平面

当 $C$ 是闭凸集,$D$ 是单点集时,我们有严格分离定理。

严格分离定理(定理). 设 $C$ 是闭凸集,点 $x_0 \notin C$,则存在非零向量 $a$ 和常数 $b$,使得 \begin{aligned} \left\{ \begin{array}{ll} a^\mathrm{T} x < b & \forall x \in C \\ a^\mathrm{T} x_0 > b. & \quad \end{array} \right. \end{aligned} 当点 $x_0$ 恰好在凸集 $C$ 的边界上时,即可构造 “支撑超平面”。

支撑超平面(定义). 给定集合 $C$ 及其边界上的一点 $x_0$,如果 $a \neq 0$ 满足 $\forall x \in C, a^\mathrm{T} x \leq a^\mathrm{T} x_0$,那么集合 $$ \big\{x \mid a^\mathrm{T} x = a^\mathrm{T} x_0 \big\} $$ 为 $C$ 在边界点 $x_0$ 处的支撑超平面。

几何上,$\{x \mid a^\mathrm{T} x = a^\mathrm{T} x_0 \}$ 与 $C$ 在点 $x_0$ 处相切且半空间 $a^\mathrm{T} x \leq a^\mathrm{T} x_0$ 包含 $C$。

支撑超平面定理(定理). 如果 $C$ 是凸集,则在 $C$ 的 任意边界点处 都存在支撑超平面。

支撑超平面的几何直观 :给定一个平面后,可把 凸集边界上的任意一点 当成支撑点将凸集放置在该平面上。从几何直观来理解凸优化的性质是非常重要的。


10 凸函数

凸函数(定义). 若函数 $f$ 的定义域 $\mathbf{dom}f$ 是凸集,且 $$ f\big(\theta x + (1-\theta) y)\big) \leq \theta f(x) + (1 - \theta) f(y) $$ 对所有 $x,y \in \mathbf{dom}f, 0 \leq 1$ 都成立,则称 $f$ 是凸函数。如果对所有 $x,y \in \mathbf{dom}f, 0 \leq 1$ 都有上式严格成立(处处小于), 则称 $f$ 是严格凸函数。

图 8 凸函数

相应地,若 $-f$ 凸函数,则称 $f$ 为凹函数。很多凸函数的性质都可以应用在凹函数上,因此我们主要讨论凸函数。

11 强凸函数

强凸函数(定义). 若存在常数 $m > 0$ 使得 $$ g(x) = f(x) - \frac{m}{2} \| x \|^2 $$ 为凸函数,则称 $f$ 是强凸函数。其中 $m$ 为强凸参数,也称 $f$ 为 $m$- 强凸函数(曲线弯曲的更加厉害了,减去一个正定二次函数之后仍然是凸的)。

强凸函数的等价定义(定义). 若存在常数 $m > 0$ 使得对于任意 $x,y \in \mathbf{dom}f$ 以及 $\theta \in (0,1)$,有 $$ f\big(\theta x + (1 - \theta) y\big) \leq \theta f(x) + (1 - \theta) f(y) - \frac{m}{2}\theta (1 - \theta) \| x - y \|^2, $$ 则称 $f$ 是强凸函数(可以看到 $f$ 一定是严格凸函数)。

显然,强凸函数比一般凸函数具有更快的收敛速度。

强凸函数解的唯一性(定理). 若 $f$ 为强凸函数且存在最小值,则 $f$ 的最小值点唯一。

证明 . 反证法。设 $x \neq y$ 均为 $f$ 的最小值点,取 $\theta \in (0,1)$,则 \begin{aligned} f\big(\theta x + (1 - \theta) y\big) &\leq \theta f(x) + (1 - \theta) f(y) - \frac{m}{2}\theta (1 - \theta) \| x - y \|^2 \\ &= f(x) - \frac{m}{2} \theta (1 - \theta) \| x - y \|^2 \qquad \quad \triangleright f(x) = f(y) \\ &<f(x), \end{aligned} 其中严格不等号成立是因为 $x \neq y$。这与 $f(x)$ 是最小值矛盾。


12 凸函数的判定

12.1 凸函数判定定理

凸函数判定定理(定理). $f(x)$ 是凸函数当且仅当对任意的 $x \in \mathbf{dom}f, v \in \mathbb{R}^n, g: \mathbb{R} \to \mathbb{R}$, \begin{aligned} g(t) = f(x + tv ), \quad \mathbf{dom} g = \{ t \mid x + tv \in \mathbf{dom}f \} \end{aligned} 是凸函数(将其限制在直线上,然后判定对应的一维函数是否是凸的)。

证明 .

必要性 。任取 $t_1, t_2 \in \mathbf{dom} g$ 以及 $\theta \in (0, 1)$,则 \begin{aligned} x + t_1 v \in \mathbf{dom}f, x + t_2 v \in \mathbf{dom}f, \end{aligned} 由 $\mathbf{dom}f$ 是凸集可以得到 \begin{aligned} x + \big(\theta t_1 + (1-\theta) t_2 \big) v \in \mathbf{dom}f, \end{aligned} 这说明 $\theta t_1 + (1-\theta) t_2 \in \mathbf{dom}g$,因此 $\mathbf{dom}g$ 是凸集。同样地,带入 $g$ 的定义可以证得 $g$ 是凸函数。

充分性 。对任意的 $x,y \in \mathbf{dom}f$ 以及 $\theta \in (0, 1)$,取 $v = y - x, t_1 = 0, t_2 = 1$, 则 $\theta \cdot 0 + (1 - \theta) \cdot 1 \in \mathbf{dom}g$,所以 $x + (1 - \theta) (y - x) = \theta x + (1 - \theta) y \in \mathbf{dom}f$,这说明 $\mathbf{dom}f$ 是凸集。

根据 $g(t)$ 的凸性,进一步有 \begin{aligned} g(1 - \theta) &= g(\theta t_1 + (1 - \theta) t_2) \\ &\leq \theta g (t_1) + (1 - \theta) g(t_2) \\ &= \theta f(x) + (1 - \theta) f(y). \end{aligned} 而等式左边有 \begin{aligned} g(1 - \theta) = f(x + (1 - \theta) (y - x)) = f(\theta x + (1 - \theta) y), \end{aligned} 因此 $f(x)$ 是凸函数。

有了凸函数判定定理,我们就可以结合定义和该定理来证明一个一般函数是否为凸函数。

12.2 常见的凸函数

12.3 更多凸性判定方法

1)利用导数判定凸性

一阶条件(定理). 对于定义在凸集上的可微函数 $f$,$f$ 是凸函数当且仅当 $$ f(y) \geq f(x) + \nabla f(x)^\mathrm{T} (y - x), \quad \forall x, y \in \mathbf{dom} f. $$

图 9 可微函数的任意一点处的一阶近似可以得到 $f$ 的一个全局下界


2)利用梯度单调性判定凸性

梯度单调性(定理). 设 $f$ 是可微函数,则 $f$ 为凸函数当且仅当 $\mathbf{dom} f$ 为凸集且 $\nabla f$ 为单调映射,即 $$ \big(\nabla f(x) - \nabla f(y) \big)^\mathrm{T} (x - y) \geq 0, \quad \forall x, y \in \mathbf{dom} f. $$

证明 .

必要性 。若 $f$ 可微且为凸函数,则根据一阶条件有 \begin{aligned} f(y) &\geq f(x) + \nabla f(x)^\mathrm{T} (y - x) \\ f(x) &\geq f(y) + \nabla f(y)^\mathrm{T} (x - y), \end{aligned} 相加即可。

充分性 。构造一元辅助函数 $g(t) = f(x + t (y - x))$,则 $g'(t) = \nabla f\big(x + t (y-x)\big)^\mathrm{T} (y - x)$。 根据 $\nabla f$ 的单调性可得 $g'(t) \geq g'(0), \forall t \geq 0$。因此 \begin{aligned} f(y) &= g(1) = g(0) + \int_0^1 g'(t)dt \\ &\geq g(0) + g'(0) = f(x) + \nabla f(x)^\mathrm{T} (y - x). \end{aligned}

严格凸函数和强凸函数的梯度单调性(定理). 设 $f$ 是可微函数,$\mathbf{dom} f$ 为凸集,则


3)利用二阶导数判定凸性

二阶条件(定理). 设 $f$ 是定义在凸集上的二阶连续可微函数,则 $f$ 是凸函数当且仅当 $$ \nabla^2 f(x) \succeq 0, \quad \forall x \in \mathbf{dom}f. $$ 若正定,则 $f$ 是严格凸函数。

证明 .

必要性 。假设存在点 $x$ 使得 $\nabla^2 f(x) \nsucceq 0$,即存在非零向量 $v \in \mathbb{R}^n$ 使得 $v^\mathrm{T} \nabla^2 f(x) v < 0$。 在 $x + tv$ 处泰勒展开得 \begin{aligned} \frac{f (x + tv) - f(x) - t \nabla f(x)^\mathrm{T} v}{t^2} = \frac{1}{2} v^\mathrm{T} \nabla^2 f(x) v + o(1). \end{aligned} 所以当 $t$ 充分小的时候 $o(1) \to 0$,即 $f (x + tv) - f(x) - t \nabla f(x)^\mathrm{T} v < 0$。这与一阶条件的结论相矛盾。

充分性 。对任意的 $x, y \in \mathbf{dom}f$,根据泰勒展开可得 \begin{aligned} f(y) = f(x) + \nabla f(x)^\mathrm{T} (y - x) + \frac{1}{2}\underbrace{(y - x)^\mathrm{T} \nabla^2 f\big(x + t (y - x)\big) (y - x)}_{\textrm{半正定性可得本项}\geq 0}, \end{aligned} 其中 $t \in (0,1)$。这正是凸函数判定的一阶条件。

本证明稍加改造,即可得到严格凸函数的二阶条件的证明。


利用二阶条件判定凸性示例


4)利用上方图判定凸性

上方图和凸函数的关系(定理). 函数 $f(x)$ 是凸函数当且仅当其上方图 $\mathbf{epi}f$ 是凸集。

证明 .

必要性 。取 $x_1, x_2, t_1, t_2$ 使得 $f(x_1) \leq t_1, f(x_2) \leq t_2$,则 $$ f(\theta x_1 + (1 - \theta) x_2) \leq \theta t_1 + (1 - \theta) t_2. $$ 这说明 \begin{aligned} \big(\theta x_1 + (1 - \theta) x_2, \theta t_1 + (1 - \theta) t_2\big) \in \mathbf{epi}f, \theta \in (0,1). \end{aligned} 所以 $\mathbf{epi}f$ 为凸集。

充分性 。显然 $(x_1, f(x_1)) \in \mathbf{epi}f, (x_2, f(x_2)) \in \mathbf{epi}f$,因为 $\mathbf{epi}f$ 是凸集,所以 \begin{aligned} \big(\theta x_1 + (1 - \theta) x_2, \theta f(x_1) + (1 - \theta) f(x_2) \big) \in \mathbf{epi}f, \theta \in (0,1). \end{aligned} 所以 $f\big(\theta x_1 + (1 - \theta) x_2 \big) \leq \theta f(x_1) + (1 - \theta) f(x_2)$。即 $f$ 是凸函数。

最后

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

转载申请

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

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


发表评论

登录以发表评论

最新评论


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