机器学习笔记之最优化理论与方法(三)凸集的简单认识(下)

引言

继续凸集的简单认识(上)进行介绍，本节将介绍凸集的基本性质以及相关定理。

回顾：基本定义——凸集

关于凸集$(\text{Convex Set})$的定义可简单表述为：可行域$\mathcal{C}$中任意两点间的连线，其连线上的任意一点仍在可行域$\mathcal{C}$范围内。对应数学符号表示如下：
$$\forall x,y\in \mathcal{C};\forall \lambda \in [0,1]\Rightarrow \lambda \cdot x+(1-\lambda )\cdot y\in \mathcal{C}$$
如果记线性规划： min ⁡ { c T x ∣ A x = b , x ≥ 0 } \min \{c^T x \mid \mathcal A x = b,x \geq 0\} min{cTx∣Ax=b,x≥0}的最优解组成的集合为$\mathcal{S}$，那么$\mathcal{S}$是否为凸集$?$

自然是凸集：

• 从最优解集合$\mathcal{S}$中任取两点$x_1,x_2\in \mathcal{S}$，必然有：
  其中这里$v^{\ast }$记作可行域范围内，使$c^{T}x$达到最小的最优解。
  $$c^T{x}_1=c^T{x}_2=v^{\ast }$$
• 根据凸集定义，$\forall \lambda \in [0,1]$，观察$\lambda \cdot x_1+(1-\lambda )\cdot x_2$是否也在最优解集合$\mathcal{S}$内即可。将该点代入有：
  $$\begin{array}{rl}& c^T[\lambda \cdot x_1+(1-\lambda )\cdot x_2]\\ & =\lambda \cdot \underset{v^{\ast }}{\underbrace{c^T{x}_1}}+(1-\lambda )\cdot \underset{v^{\ast }}{\underbrace{c^T{x}_2}}\\ & =v^{\ast }\end{array}$$
  可以看出：$c^T[\lambda \cdot x_1+(1-\lambda )\cdot x_2]$依然是最优解。也就是说：点$\lambda \cdot x_1+(1-\lambda )\cdot x_2\in \mathcal{S}$。$\mathcal{S}$是凸集得证。

关于保持集合凸性的运算

所谓保持集合凸性的运算，即凸集执行一系列运算后，其结果是凸集的性质不发生变化。

设${\mathcal{C}}_1,{\mathcal{C}}_2\in {\mathbb{R}}^n$，并且是凸集。则有：

• 交集 C 1 ∩ C 2 = { x ∣ x ∈ C 1 , x ∈ C 2 } \mathcal C_1 \cap \mathcal C_2 = \{x \mid x \in \mathcal C_1,x \in \mathcal C_2\} C1​∩C2​={x∣x∈C1​,x∈C2​}同样是凸集；
  相反，并集${\mathcal{C}}_1\cup {\mathcal{C}}_2$未必是凸集~
• 关于集合的加减运算： C 1 ± C 2 = { x ± y ∣ x ∈ C 1 , y ∈ C 2 } \mathcal C_1 \pm \mathcal C_2 = \{x \pm y \mid x \in \mathcal C_1,y \in \mathcal C_2\} C1​±C2​={x±y∣x∈C1​,y∈C2​}同样是凸集。

如果存在一个由$n$维向量组成的集合$\mathcal{S}$：
$$\{\begin{array}{l}\begin{array}{rl}& \mathcal{S}=\left\{x\in {\mathbb{R}}^n\mid |\mathcal{P}(t)|\le 1,|t|\le \frac{\pi }{3}\right\}\\ & \mathcal{P}(t)=\sum _{i=1}^n{x}_i\cdot \cos (i\cdot t)\end{array}\end{array}$$
那么集合$\mathcal{S}$是否为凸集$?$

• 首先，由于$\mathcal{S}$是关于$x$的集合，因而$\mathcal{P}(t)$可看作是一个关于$x$的线性表达式。并且有：
  $$-1\le \sum _{i=1}^n{x}_i\cdot \cos (i\cdot t)\le 1$$
• 如果$t$给定，那么可以将上式视作：$\{\begin{array}{l}{\sum }_{i=1}^n{x}_i\cdot \cos (i\cdot t)\le 1\\ {\sum }_{i=1}^n{x}_i\cdot \cos (i\cdot t)\ge -1\end{array}$所描述的一对半空间的交集。
• 由于$\begin{array}{r}-\frac{\pi }{3}\le t\le \frac{\pi }{3}\end{array}$，是一个连续的范围，那么：可以在该范围内取出无穷个$t$，从而得到无穷对半空间的交集。而半空间自身是凸集，那么无穷对半空间的交集同样是凸集。因而$\mathcal{S}$是凸集。
  准确的说，$\mathcal{S}$是一个多面体。

如果$n=2$，此时仅包含两个变量$x_1,x_2$。可以通过$2$维图像的方式观察这个多面体凸集描述的范围。具体代码如下：
在$t$固定的情况下，函数$|\mathcal{P}(t)|=1\Rightarrow \mathcal{P}(t)=\pm 1$可看做是$\varphi (x_1,x_2)$的表示。令$\varphi (x_1,x_2)=\mathcal{P}(t)\mp 1\triangleq 0$,从而得到$x_1,x_2$之间的函数关系：
$$\begin{array}{rl}& x_1\cdot \cos t+x_2\cdot \cos (2\cdot t)=\pm 1\\ & \Rightarrow x_1=\pm \frac{1-x_2\cdot \cos (2\cdot t)}{\cos t}\end{array}$$

import numpy as np
import matplotlib.pyplot as plt
import mathx = np.linspace(-2.5,2,100)
tChoice = np.linspace(-1 * (math.pi / 3),math.pi / 3,30)def phi(x1,t):return (1 - x1 * math.cos(2 * t)) / math.cos(t)def phiTrans(x1,t):return (x1 * math.cos(2 * t) - 1) / math.cos(t)for t in tChoice:y = list()y2 = list()for x1 in x:y.append(phi(x1,t))y2.append(phiTrans(x1,t))plt.plot(x,y,c="tab:red")plt.plot(x,y2,c="tab:red")
plt.show()

对应图像结果表示如下：
中间围成的区域就是$n=2$条件下的多面体凸集$\mathcal{S}$。

仿射变换

仿射变换$(\text{Affine Transformation})$同样是保持集合凸性的一种运算。具体描述如下：
需要注意的是：线性变换是特殊的仿射变换。

假设函数$f(\cdot ):{\mathbb{R}}^n\mapsto {\mathbb{R}}^m$是仿射函数，即$f(x)=\mathcal{A}x+b$。其中$\mathcal{A}\in {\mathbb{R}}^{m\times n},b\in {\mathbb{R}}^m$，则有如下结论：
其中$f^{-1}(\cdot )$表示仿射函数$f(\cdot )$的逆。

• 如果$\mathcal{C}$是凸集 ⇒ f ( C ) = { f ( x ) ∣ x ∈ C } \Rightarrow f(\mathcal C) = \{f(x) \mid x \in \mathcal C\} ⇒f(C)={f(x)∣x∈C}也是凸集；
• 如果$\mathcal{C}$是凸集 ⇒ f − 1 ( C ) = { x ∣ f ( x ) ∈ C } \Rightarrow f^{-1}(\mathcal C) = \{x \mid f(x) \in \mathcal C\} ⇒f−1(C)={x∣f(x)∈C}也是凸集；

以第一项为例：对于$\forall y_1,y_2\in f(\mathcal{C})$，必然有：
$$\{\begin{array}{l}{y}_1=\mathcal{A}{x}_1+b\\ y_2=\mathcal{A}{x}_2+b\end{array}{x}_1,x_2\in \mathcal{C}$$
根据凸集的定义，对$\forall \lambda \in [0,1]$，将$\lambda \cdot y_1+(1-\lambda )\cdot y_2$展开，有：
$$\begin{array}{rl}\lambda \cdot y_1+(1-\lambda )\cdot y_2& =\lambda (\mathcal{A}{x}_1+b)+(1-\lambda )\cdot (\mathcal{A}{x}_2+b)\\ & =\mathcal{A}[\lambda \cdot x_1+(1-\lambda )\cdot x_2]+b\end{array}$$
由于$x_1,x_2\in \mathcal{C}$，且$\mathcal{C}$是凸集，必然有：
$$\forall \lambda \in [0,1]\Rightarrow \lambda \cdot x_1+(1-\lambda )\cdot x_2\in \mathcal{C}$$
从而有：
$$\lambda \cdot y_1+(1-\lambda )\cdot y_2\in f(\mathcal{C})$$
因而$f(\mathcal{C})$也是凸集。

一些特殊的仿射变换有：
其中$\alpha ,\beta$是常数。

• 放缩$(\text{Scaling})$：
  α ⋅ C = { α ⋅ x ∣ x ∈ C } \alpha \cdot \mathcal C = \{\alpha \cdot x \mid x \in \mathcal C\} α⋅C={α⋅x∣x∈C}
• 平移$(\text{Translation})$：
  β + C = { β + x ∣ x ∈ C } \beta+ \mathcal C = \{\beta+ x \mid x \in \mathcal C\} β+C={β+x∣x∈C}
• 投影$(\text{Projection})$
  $$\left\{x^1\mid \left(\begin{array}{c}{x}^1\\ x^2\end{array}\right)\in \mathcal{C}\right\}$$

对应示例图像表示如下：

凸集基本性质：投影定理

投影定理描述如下：
假设$\mathcal{C}\subset {\mathbb{R}}^n$，是一个非空闭凸集；$y\in {\mathbb{R}}^n$但$y\notin \mathcal{C}$，有：

• 存在唯一的点$\bar{x}\in \mathcal{C}$，使得$\bar{x}$是$y$到$\mathcal{C}$的距离最小的点，且有：
  距离最小的点即投影点。
  ∥ x ˉ − y ∥ = inf ⁡ { ∥ x − y ∥ ∣ x ∈ C } > 0 \|\bar {x} - y\| = \inf\{\|x - y\| \mid x \in \mathcal C\} > 0 ∥xˉ−y∥=inf{∥x−y∥∣x∈C}>0
• $\bar{x}$是$y$到$\mathcal{C}$的最小距离点的充要条件是：
  $$(x-\bar{x}{)}^T(\bar{x}-y)\le 0\forall x\in \mathcal{C}$$

证明过程：

• 存在性：
  关于$y$到$\mathcal{C}$的距离，本质上是描述$y$与凸集$\mathcal{C}$中点的距离，假设$x^{\prime }\in \mathcal{C}$，对应目标函数表示如下：
  这里使用二范数表示$x^{\prime }$与$y$之间的距离。
  $$\min f(x)=\Vert y-x^{\prime }{\Vert }_2^2$$
  但我们要找的是距离最小的点，而这个$x^{\prime }$可能并不是那个点。因而我们要找的距离最小点的可行域表示为：
  $$\text{s.t. }x\in \mathcal{C}\cap {\mathcal{N}}_d(y)$$
  其中$d=||y-x^{\prime }|{|}_2^2$；而${\mathcal{N}}_d(y)$表示以$y$为圆心，半径为$d$的圆所描述的范围。也就是说：如果$x^{\prime }$不是距离最小点，并不需要重新从范围$\mathcal{C}$中寻找点，只需要在交集内寻找距离最小点即可。对应图像表示如下：
  
  由于$\mathcal{C}$是非空闭凸集，说明这个交集有界。在连续函数(距离函数)在有界空间内求最小值，那么该值必然可达。

• 唯一性(反证)：
  对应图像表示如下~
  
  不妨设$x^{\prime },\bar{x}(\bar{x}\ne x^{\prime })$均是投影点，从而有：
  $$d=\Vert y-\bar{x}{\Vert }_2^2=\Vert y-x^{\prime }{\Vert }_2^2$$
  由于$\bar{x}\ne x^{\prime }$，连接两点，根据凸集合的定义：两点连线上的点必然也$\in \mathcal{C}$。此时，$x^{\prime },\bar{x},y$三个点构成一个等腰三角形，从而有：线段$\bar{x}{x}^{\prime }$上的点到$y$的距离必然小于$d$。从而得出：$\bar{x},x^{\prime }$不是投影点，这与假设冲突。因而$x^{\prime },\bar{x}$两点重合，投影点具有唯一性。

• 充要条件：观察下面图像：
  
  假设此时已经找到了投影点$\bar{x}$，必然有：

  • 向量$y-\bar{x}$与$\bar{x}$在凸集$\mathcal{C}$的切线垂直；
  • 并且凸集$\mathcal{C}$中除去$\bar{x}$之外的其他点均与$y-\bar{x}$处在由切线划分的不同的半空间。

  从而有：向量$y-\bar{x}$与$x-\bar{x}(\forall x\in \mathcal{C})$之间的夹角总是大于等于$90^{。}$。即：
  等于$90^{。}$即$x,\bar{x}$重合~
  $$(y-\bar{x}{)}^T(x-\bar{x})=\Vert y-\bar{x}\Vert \cdot \Vert x-\bar{x}\Vert \cos \theta \le 0$$
  反之同理。

点与凸集的分离

定理描述如下：
假设${\mathcal{C}}_1,{\mathcal{C}}_2$是两个非空凸集，若存在非零$\alpha \in {\mathbb{R}}^n$和$b\in \mathbb{R}$使得：
或者写作:${\alpha }^{T}z\le {\alpha }^{T}x\forall x\in {\mathcal{C}}_1,\forall z\in {\mathcal{C}}_2$
$$\{\begin{array}{l}{\alpha }^{T}x\ge b\forall x\in {\mathcal{C}}_1\\ {\alpha }^{T}z\le b\forall z\in {\mathcal{C}}_2\end{array}$$
则称超平面 H = { x ∣ α T x = b } \mathcal H = \{x \mid \alpha^T x = b\} H={x∣αTx=b}分离集合${\mathcal{C}}_1,{\mathcal{C}}_2$。

严格分离：
观察上述的分离定义，由于超平面可以取等，使得凸集${\mathcal{C}}_1,{\mathcal{C}}_2$与超平面$\mathcal{H}$之间可能存在交集。而严格分离定义在上述分离定义的基础上，${\mathcal{C}}_1,{\mathcal{C}}_2$均不与超平面$\mathcal{H}$之间存在交集。即：
$$\{\begin{array}{l}{\alpha }^{T}x>b\forall x\in {\mathcal{C}}_1\\ {\alpha }^{T}z<b\forall z\in {\mathcal{C}}_2\end{array}$$
基于上述定义，从而有如下推论：

• 两个不相交的非空凸集，它们一定能分离；
  相反，如果存在集合不是凸集,那就不一定了~
• 假设$\mathcal{C}\subset {\mathbb{R}}^n$是非空闭凸集，点$y\notin \mathcal{C}$，必然存在超平面$\mathcal{H}$将$y$与$\mathcal{C}$分离。
  例如上面描述投影定理充要条件中的红色虚线。实际上:垂直于$y-\bar{x}$并且经过线段$\bar{x}y$上的超平面都是满足要求的。
  $$\{\begin{array}{l}\alpha =y-\bar{x}\\ {\alpha }^T(y-x)\ge 0\Rightarrow {\alpha }^{T}y\ge {\alpha }^{T}x\forall x\in \mathcal{C}\end{array}$$
  上面式子描述的向量$y-x$描述的是从凸集$\mathcal{C}$中的任意一点指向$y$的向量，而该向量和向量$y-\bar{x}$之间的夹角必然是锐角。

支撑超平面定理

定理描述如下：
假设$\mathcal{C}\in {\mathbb{R}}^n$是非空闭凸集，其中$\bar{x}$是$\mathcal{C}$的边界点：$\bar{x}\in \partial \mathcal{C}$，则存在非零向量$\alpha \in {\mathbb{R}}^n$使得：
其中$\partial \mathcal{C}$表示集合$\mathcal{C}$的边界点；$\text{int}\mathcal{C}$表示集合$\mathcal{C}$不包含边界点的所有内点；$cl\mathcal{C}$表示由内点、边界点构成的集合(闭包)$\Rightarrow$非空的闭凸集合。
$${\alpha }^{T}x\le {\alpha }^T\bar{x}\forall x\in clC$$
此时，也称超平面 H = { x ∈ R n ∣ α T x = α T x ˉ } \mathcal H = \{x \in \mathbb R^n \mid \alpha^T x = \alpha^T \bar{x}\} H={x∈Rn∣αTx=αTxˉ}是凸集$\mathcal{C}$在$\bar{x}$处的支撑超平面。对应图像表示如下：

证明过程：
已知$\bar{x}\in \partial \mathcal{C}$，要证：$\exists \alpha \ne 0$使得${\alpha }^{T}x\le {\alpha }^T\bar{x}\forall x\in cl\mathcal{C}$

由于$\bar{x}\in \partial \mathcal{C}$，则必然可以找到收敛于$\bar{x}$的点序列 { x k } ↦ x ˉ \{x_k\} \mapsto \bar{x} {xk​}↦xˉ并且 { x k } ∉ c l C \{x_k\} \notin cl\mathcal C {xk​}∈/clC
也就是说:这个点序列 { x k } \{x_k\} {xk​}并不是从凸集$\mathcal{C}$内找的，而是从集合之外找的。

由于$x_k\notin cl\mathcal{C}$，根据分离定理，存在超平面/非零法向量${\alpha }_k$，有：
也就是说:每一次迭代，总会找到相应的超平面${\alpha }_k$将$\mathcal{C}$与$x_k$做分离。
$${\alpha }_k^{T}x\le {\alpha }_k^T{x}_{k}x\in cl\mathcal{C}$$
由于${\alpha }_k$是法向量，我们更关注它的方向性而不是大小。因而不妨设$\Vert {\alpha }_k\Vert =1$，则有：法向量序列 { α k } \{\alpha_k\} {αk​}随着 { x k } \{x_k\} {xk​}的迭代过程收敛到某位置。当$k\Rightarrow \infty$时，有：
$${\alpha }^T\bar{x}=\underset{k\Rightarrow \infty }{\lim }{\alpha }_k^T\cdot x_k\ge {\alpha }^{T}xx\in cl\mathcal{C}$$
证毕。使用图像表示如下：

相关参考：
最优化理论与方法-第二讲-凸集