北京大数据研究院

BEIJING INSTITUTE OF BIG DATA RESEARCH

研院简介

科研中心

墨奇博客 | 凸优化简介：极值何时存在？

文章来源于微信公众号：墨奇科技

引言

同学们可能能回忆起来，对于二次函数 $f(x)=(x-a)^2+b$ 来说最小值出现于 $x=a$ 为 $f(a)=b$ 。这个当然是一个非常简单的例子。在这里我们先热热身，我们把 $x=a$ 叫做 $f$ 在实数集 $\mathbb{R}$ 的最小解，最小值为 $b$ 。如果对于函数 $f(x)=-(x-a)^2+b$ 则存在最大值 $b$ 。所以像这些有最值的函数都可以有最优解，那么求解这些最值和最值位置的问题就是我们常说的最优化问题（Optimization）。

在求解这个问题之前，我们应该先判断问题本身是不是可解的。一些同学可能能想起有个东西叫极值存在定理。它是这样描述的：在一个有界区间中，如果一个函数是连续的，那么在这个区间内它一定存在极大值和极小值。然而对于最优化问题来讲，我们在当前区间内更关心这个极大值唯一吗？或者这个极小值唯一吗？读到这里的同学们可以先思考一下，能有什么样的性质能帮助我们判断这种唯一性吗？

当然聪慧的你们肯定能察觉到一些蛛丝马迹。正如标题中提到的凸优化中的 “凸”，我们看重的是问题的 “凸” 性。在深入到各种数学符号之前，我觉得大家应该更加感性的理解这个问题。

举个例子，想象有一块橡皮泥，我们希望这块橡皮泥印在平板上的印记只有一个。那么这个橡皮泥应该是什么样子的呢？如果是个正方体，那么印记会是一条线段或者一个长方形或者一个点。若是一个球形的，那么印记会是一个点。这两个例子都满足前文“印记只有一个”的前提要求。但如果是马鞍形，印记则可能是两个点。是不是感觉有点理解这个感性认识了？

如果你能找到点感觉，那就带着这个感觉先赶快看一下经典 Weierstrass 级值定理吧。这部分内容能够帮助你理解一个更广义的极值存在定理，并将连续这个概念拓展到更广泛的场景中。

经典 Weierstrass 极值定理

基本定义与定理

本节我们会介绍一些基本概念，包括什么是有界、闭合、紧致等定义。同时我们还会回顾一些连续性的相关定义，以方便我们去证明后续的一些定理。

1.有界 (bounded) ：有界集合有穷的集合半径；有界集合内部的任两个点的距离都是有穷的。

2.闭合 (closed) ：闭合集合是有界的且边界在集合中的。

3.紧致 (compact) ：紧致集合是有界的且闭合的。

4.真性 (proper)：真度量空间内所有的闭合球 (closed ball) 都是紧致的。换言之，真度量空间都是完备的(complete)。真函数 (proper functions) 在自身非空的定义域中每个值都大于 $-\infty$ 且存在一个值小于 $\infty$ 。

5.下半连续 (lower semi-continuous) ：闭合函数都是下半连续的，反之亦然。（上半连续 + 下半连续 = 连续）

$f(x)\le\lim_{k\to\infty}\inf{f(x_k)} \qquad \forall x_k\to x \text{ and } {x_k}\subset X$

6.强制性 (coercive) ：可以理解为是函数在轴两侧都是奔向无穷的。

7.Bolzano-Weierstrass 定理：任意有界的序列都有一个收敛的子序列。

极值存在定理

在证明经典 Weierstrass 极值定理之前，我们先推出一个初始版本的极值定理：

(定理 1) 对于一个闭合，强制性的真函数 (coercive, closed and proper function)

$f:X\to(-\infty,+\infty]$ $(\exists x\in X) \text{ } f(\bar{x}):=\min f(x) = \inf f(x)$ ： $\bar{x}$ 是函数 $f$ 的极小值点。

证明：

先定义一个序列 $(x_n)$ 让 $f(x_n)\to\inf f(x)$ 。

声明：

(x_n)

有一个有界的子序列。

~~（为了证明上面的声明是正确的，我们需要使用反证法来证明。这部分可能会有点绕）~~

假设

上面的的声明不正确，也就是说

(x_n)

没有一个有界的子序列，则

(x_n)

不是有界的。根据强制性（coercive），对于

\|x_n\|\to\infty

，我们有

f(x_n)\to\infty

；

又根据我们对于序列

(x_n)

的定义，

f(x_n)\to\inf f(x) = \infty

；这与真函数的定义相悖。因此假设不成立，原命题“

(x_n)

有一个有界的子序列”为真。

由上面的推导，我们可以声明 $(x_n)$ 有界。根据 Bolzano-Weierstrass 定理， $(x_n)$ 有一个收敛的子序列。我们在这里把这个有界且收敛的序列记作 $(x_n)'$ 。

因此我们有，

$\inf_n f(x_n) \le f(\bar{x}) \le \underline{\lim} f(x_n)=\inf f(x_n) \qquad \forall x_n \in (x_n)'$

其中， $\inf_n f(x_n) \le f(\bar{x}) \le \underline{\lim} f(x_n)$ 是根据 $(x_n)'$ 的收敛性和闭合性（由序列定义可知）

且因为 $\inf_n f(x_n)=\inf f(x_n)$ ，所以整个不等式就转换成了等式：

$\inf_n f(x_n) = f(\bar{x}) = \underline{\lim} f(x_n)=\inf f(x_n) \ne -\infty\qquad \blacksquare$

经典 Weierstrass 极值定理的证明

上面的一些定理能够帮助我们去定义一个函数是否有一个极小值。在引出经典 Weierstrass 极值定理之前，我们还需要补充指示函数的一些定义和性质

1.指示函数（indicator function）：指示函数

\delta_C := \begin{cases} 0 & x\in C \\ \infty & x\notin C\\ \end{cases} \qquad \operatorname{dom} \delta_C = C

在面对指定定义域的问题时，可以结合指示函数来定义目标函数，比如 $f|_C$ 可以记作 $f+\delta_C$ 。同时我们可以注意到， $\delta_C$ 是一个闭合函数，

那么现在我们终于来到了本节的大 boss：

(经典 Weierstrass 极值定理) 对于一个下半连续（lower semi-continuous）的函数 $f:X\to(-\infty,\infty]$ 在一个紧致的集合 $C$ 上， $\operatorname{dom}f \cap C \ne \phi$ ，那么 $f|_C$ 有一个极小值。

证明：

首先我们面对由定义域的函数

f|_C

，将其转化为

f+\delta_C

。目标就是证明

f+\delta_C

是闭合强制的真函数，以利用之前证明的极值存在定理来证明这个定理。

（闭合性）

因为

f

和

\delta_C

都是闭合函数，我们先记

f(x)+\delta_C(x) := (f+\delta_C)(x)

，那么有

所以我们可知 (f+δC) 是下半连续的，也就是闭合的。

（强制性）

当

|x|\to\infty

，

(f+\delta_C)(x)\to\infty

。因为集合

C

是闭合且有界的，所以超出闭合定义域的值会被指示函数顶到

\infty

。

（真性）

$\operatorname{dom}(f+\delta_C) = \operatorname{dom}f \cap \operatorname{dom}\delta_C = \operatorname{dom}f + C \ne \phi$ ，所以真性得到了保证。

因此函数

f+\delta_C

是闭合强制的真函数，根据极值存在定理，我们可以得到该函数至少存在一个极小值。■

小结一下

现在成功的将极值存在定理从连续函数拓展到了半连续 (semi-continuous) 函数上。同学们可能会问了，这有什么用呢？这个很有用，因为实际场景中连续性是比较少见的。熟悉神经网络的同学们可能会知道 ReLU 这个东西，是一个分段函数 (piece-wise) ，虽然不是连续的但是却是半连续的。所以本节当中推导的经典 Weierstrass 极值定理能够确保我们即使遇到半连续的函数，也能确保我们还能用极值存在作为已知前提。

凸函数与 Hilbert 投影定理

感谢能看到这里的同学，接下来就是比较让人激动的内容了。本节我们会介绍凸函数和可分离定理。这是对于凸优化非常重要的基本概念。这为最优化算法可行性的判定提供了有效的依据。我个人也是觉得这部分算是容易理解并且很优雅的一节内容。

什么是凸函数

重点来了！敲黑板！！

1.凸函数的定义有两种形式：

a. 定义：（类似地，我们可以来思考一下凸集合的定义是什么？）

b. Jensen 不等式形式：

我们可以简单消化一下：如果在函数围成的区域内随意取两个点，并将两点连成线段，那么如果这个线段上任意点都还在这个区域里，那么这个函数就是凸的。这个被函数围成的区域也是有学名的，它叫上镜图 Epigraph（如果把函数围成的区域替换成集合，那么凸集合的定义就呼之欲出了）

2.凸函数的一些性质：

a.（仿射不变性）

对于一个线性映射 $A:X\to Y$ 和向量 $b\in Y$ ，对于一个凸函数 $g:Y\to(-\infty,\infty]$ ，则 $f:X\to (-\infty,\infty]:x\mapsto g(Ax+b)$ 也为凸函数。

证明：

$\begin{aligned}f\Big(\lambda x_1+(1-\lambda)x_2\Big)&=g\Big(A\big(\lambda x_1 + (1-\lambda) x_2\big) + b\Big)\\&=g\Big(\lambda Ax_1+(1-\lambda) Ax_2+b\Big)\\&\le\lambda g(Ax_1+b) + (1-\lambda)g(Ax_2+b)\\&=\lambda f(x_1)+(1-\lambda)f(x_2)\end{aligned}$

所以根据定义，可以证明凸性有仿射不变性。■

b.（非负权和下不变）

对于非负的 $\alpha_1,\alpha_2,\alpha_3,...,\alpha_m$ 和扩充实值凸函数 (extended real valued function) $f_1,f_2,f_3,...,f_m$ ，那么 $\sum_i^m \alpha_i f_i$ 也是凸函数。

证明：这个证明很简单，推导一下就可以得到这个结果

\begin{aligned}\sum_i^m \alpha_if_i\big(\lambda x_a+(1-\lambda x_b)\big)&=\alpha_1f_1\big(\lambda x_a + (1-\lambda)x_b\big) + \\&\qquad... + \alpha_mf_m\big(\lambda x_a + (1-\lambda)x_b\big) \\ &\le \lambda\alpha_1f_1(x_a)+ (1-\lambda)\alpha_1f_1(x_b)+ \\ &\qquad ... +\lambda\alpha_mf_m(x_a)+ (1-\lambda)\alpha_mf_m(x_b)\\ &=\lambda\sum_i^m\alpha_if_i(x_b) + (1-\lambda)\sum_i^m\alpha_if_i(x_b)\end{aligned}

因此可得凸函数在非负的权重求和下，凸性不变。■

c.（凸函数集合的上确界为凸）

对于一个凸函数集合 $(f_i)_{i\in I}$ ，凸函数集合的上确界也是凸的。

证明：

\begin{aligned}&\sup_i f_i\big(\lambda x_a + (1-\lambda)x_b\big)\\\le &\sup_i \big\{ \lambda f_i(x_a)+(1-\lambda)f_i(x_b)\big\} \\\le &\lambda\sup_i f_i(x_a)+(1-\lambda)\sup_i f_i(x_b)\qquad \blacksquare \end{aligned}

点到集合的投影

1.支撑函数（Support function）：支持函数

$\sigma_C(y):=sup_{x\in C}\langle y,x\rangle$

经过推导我们可以知支持函数是闭合且凸的。支持函数可以理解为绕着集合的一个函数，描绘了集合的边界。

2.支持函数的性质：（这里我们定义 $rA:=\{ra|a\in A\}$ ， $A+B:=\{a+b|a\in A, b\in B\}$ ）

a. $\sigma_C(\alpha y) = \alpha\sigma_C(y)=\sigma_{\alpha C}(y)$

b. $\sigma_C(\alpha y) = \alpha\sigma_C(y)=\sigma_{\alpha C}(y)$

c. $\sigma_C(y+z)\le\sigma_C(y)+\sigma_C(z)$

d. $\sigma_{A+B}(y) = \sigma_A(y)+\sigma_B(y)$

3. 集合的投影（Projection of a set）：对于一个非空且闭合的集合 $C\subseteq X$ ，对于一个任意点 $z\in X$ ，存在一个集合内的点 $x\in C$ 满足 $\|z-x\|=d_C(z)=\inf_{c\in C}\|z-c\|$ 。我们把满足这一条件的点 $x$ 定义为集合 $C$ 的投影，记作 $P_C(z)$ 。

4. 对于欧几里得范数 $\|\cdot\|$ 而言，我们有

5. 如果 $\|\cdot\|$ 是欧几里得范数，且 $C$ 为凸集合，那么 $P_C(z)$ 则是一个单点（singleton）。

证明：

不妨假设集合投影

P_C(z)

有两个点

x_0,x_1

，则有

\|z-x_i\|=d_C(z) \qquad i\in\{0,1\}

我们先由凸性定义

x_\lambda := (1-\lambda)x_0+\lambda x_1 \in C

，其中

\lambda\in(0,1)

。因此有

\begin{aligned}d_C(z)&\le \|z-x_\lambda\|^2\\&=\|z-(1-\lambda)x_0-\lambda x_1\|^2\\&=\|(1-\lambda)(z-x_0)+\lambda (z-x_1)\|^2\end{aligned}

根据上文提到的 CUTE 性质和上文两个点的定义，不难得到：

但是这里我们需要注意，

-\lambda(1-\lambda)\|x_1-x_0\|^2

是非正的。为了满足不等式

d_C(z)\le d_C(z)-\lambda(1-\lambda)\|x_1-x_0\|^2

只能让

-\lambda(1-\lambda)\|x_1-x_0\|^2=0

。因此证明了

x_0,x_1

实际上是一个点，也就证明了若集合为凸，那么集合外一点到集合的投影唯一。■

有了上面的凸集投影唯一的性质，我们就可以很方便地得到本节的主题：Hilbert 投影定理

Hilbert 投影定理

（Hilbert 投影定理）对于一个闭合的凸集合 $C\subseteq X,C\ne\phi$ ，任意不在集合内的点 $z\in X$ ，存在一个唯一的投影 $P_C(z)\in C$ 。同时，对于投影 $P_C(z)$ ，有 $p=P_C(z)\Leftrightarrow \langle c-p, z - p\rangle\le0$ 。

证明：因为集合为凸且闭合， $p$ 为集合的投影，因此我们有：

为了方便表示，我们定义

a:=z-p,b:=c-p

，因此我们有：

\begin{aligned} \|a\|^2&\le\|a-\lambda b\|^2\\ \|a\|^2&\le\|a\|^2-2\langle a,\lambda b\rangle+\lambda^2\|b\|^2\\ 0&\le\lambda^2\|b\|^2-2\lambda\langle a,b\rangle\\ 2\langle a,b\rangle&\le\lambda\|b\|^2\qquad\forall\lambda\in[0,1]\\ \langle a,b\rangle&\le 0 \end{aligned}

我们重新带回两个定义，即可得到

\langle z-p,c-p\rangle\le0

。■

我们做了一个图示以方便大家理解。请大家看下图， $p$ 为点 $z$ 在集合 $C$ 的上的投影，对于在集合内的点 c ，可以明显观察到 $\langle c-p, z - p\rangle\le0$ 。但是集合外的点 $c'$ 就不能满足上述条件。这样能让我们更感性地理解 Hilbert 投影定理。

有了这样优美的理论，我们总感觉还差点什么。就让我们引申一下，看分离定理是怎么推导的：

（分离定理）对于 $X\supseteq C \ne 0$ ， $C$ 是闭合的凸集合，点 $z\notin C$ 。那么， $\exists a\in X \backslash{\{0\}}$ ， $\exists\alpha\in\mathbb{R}$ ，满足 $\langle a,z\rangle>\alpha\ge\sup_{c\in C}\langle a,c\rangle$ 。

证明：

定义

a:=z-P_C(z)\ne0

（因为

z

不在

C

中）和

\alpha:=\langle z-P_C(z), P_C(z)\rangle\in\mathbb{R}

。

\forall c\in C

，根据 Hilbert 投影定理，我们有

\begin{aligned}\langle c-P_C(z),z-P_C(z)\rangle&\le 0\\ \langle c,z-P_C(z)\rangle&\le\langle P_C(z),z-P_C(z)\rangle=\alpha\end{aligned}

此外，

\begin{aligned} \langle a,z\rangle&=\langle z-P_C(z), z\rangle=\langle z-P_C(z),\big(z-P_C(z)\big)+z\rangle\\ &=\|z-P_C(z)\|^2+\langle z-P_C(z),z\rangle\\ &>\langle z-P_C(z),z\rangle=\alpha \end{aligned}

我们可以看到上面的没有不等式没有等号，是因为我们定义存在集合外的一点

a

。■

换言之，我们总能找到一个非零超平面 $\langle a,z\rangle>\alpha$ 将空间中含有集合 $C$ 的部分和不含 $C$ 的部分一分为二，只要集合 $C$ 是一个凸集合。

这个是不是很酷？上面的一些推导向我们展示了，“凸性“ (convexity) 能作为我们处理最优化问题的一个有力证据。本次由于篇幅问题我们还有很多精彩的内容没有覆盖，比如 KKT 条件。我们将求解凸问题的最优化问题统称 “凸优化”。由于我们仅仅限制了凸性这个更加宽泛的性质，对于连续性和可微性的限制很小，所以接下来我们还需要拓展微分的概念。比如次微分 (subdifferential)，次梯度 (subgradient)等等。

如果感兴趣的话，要记得时刻关注了解更多凸优化知识哦！

—END—

上一篇快马加鞭！深势科技 Uni-Fold 融合最新加速技术，训练速度再增18%！

下一篇新一代工业软件内核发布

文章分类：对外活动