Chapter 2 凸集

2.1 仿射集和凸集

2.1.1 直线和线段

假设 \(x_1\neq x_2\)\(\mathbb{R}^n\) 上的两个点。那么如下形式的点

\[ y=\theta x_1+(1-\theta)x_2 \]

其中 \(\theta\in\mathbb{R}\),构成了 \(x_1\)\(x_2\) 之间的一条直线。假如 \(\theta=0\),那么 \(y=x_2\);如果 \(\theta=1\),就有 \(y=x_1\)

如果用另外一种方法表示 \(y\)

\[ y=x_2+\theta(x_1-x_2) \]

则有另外一种理解方式:\(y\)基点 \(x_2\)方向向量 \(x_1-x_2\)(从 \(x_2\) 指向 \(x_1\))的 \(\theta\) 倍的加和。因此,\(\theta\) 反映了 \(y\)\(x_1\)\(x_2\) 之间的位置。随着 \(\theta\)\(0\)\(1\) 变化,\(y\)\(x_2\) 逐渐向 \(x_1\) 移动;对于 \(\theta > 1\) 的情况,\(y\) 会在 \(x_1\) 外边的射线上。(如图)

2.1.2 仿射集

如果通过集合 \(C\) 中任意两点的直线都在 \(C\) 中,那么集合 \(C\) 就是仿射集,也就是说,对于任意 \(x_1,x_2\in C\)\(\theta\in\mathbb{R}\),都有 \(y=\theta x_1+(1-\theta)x_2\in C\)。换句话说,\(C\) 包含了 \(C\) 中任意两点的线性组合,且线性系数之和为 \(1\)

这种想法可以推广到多个点上。比如我们有一个点,满足 \(\sum_{i=1}^k \theta_ix_i\),其中 \(\sum_{i=1}^k \theta_i=1\)。这个点就是 \(x_1,\cdots,x_k\) 的仿射组合。从仿射集的定义归纳下来的话(即仿射集包括其中任意两点的仿射组合),一个仿射集包含每个其中点的仿射组合:如果 \(C\) 是一个仿射集,那么对于任意 \(x_1,\cdots,x_k\in C\),都有 \(\sum_{i=1}^k \theta_ix_i\in C\),其中 \(\sum_{i=1}^k \theta_i=1\)

如果 \(C\) 是一个仿射集,且 \(x_0\in C\),则集合

\[ V=C-x_0=\{x-x_0\mid x\in C\} \]

是一个子空间(即加法和数乘封闭)。为了证明这一点,假设 \(v_1,v_2\in V\)\(\alpha,\beta\in\mathbb{R}\)。那么我们有 \(v_1+x_0\in C\)\(v_2+x_0\in C\),因此

\[ \alpha v_1+\beta v_2+x_0=\alpha v_1+\beta v_2+(1-\alpha-\beta)x_0=\alpha(v_1+x_0)+\beta(v_2+x_0)+(1-\alpha-\beta)x_0\in C \]

因为 \(C\) 是仿射集,并且 \(\alpha+\beta+(1-\alpha-\beta)=1\)。因此,我们得到了 \(\alpha v_1+\beta v_2\in V\),因为 \(\alpha v_1+\beta v_2+x_0\in C\)

因此,仿射集 \(C\) 可以表达成

\[ C=V+x_0=\{v+x_0\mid v\in V\} \]

即一个子空间加上一个偏差量的形式。子空间 \(V\) 以不取决于 \(x_0\) 取值的情况与仿射集 \(C\) 产生关联,因此 \(x_0\) 可以选取为 \(C\) 中的任意点。因此,我们可以定义仿射集 \(C\)维度为子空间 \(V=C-x_0\) 的维度,其中 \(x_0\)\(C\) 中的任意元素。

Example 2.1 (线性方程组的解集) 线性方程组的解集 \(C=\{x\mid Ax=b\}\)(其中 \(A \in \mathbb{R}^{m\times n}\)\(b \in \mathbb{R}^m\))是一个仿射集,为了证明,假设 \(x_1,x_2\in C\),那么 \(Ax_1=b\)\(Ax_2=b\)。对于任意 \(\theta\),我们有

\[ \begin{align} A(\theta x_1+(1-\theta)x_2)&=\theta Ax_1+(1-\theta)Ax_2 \\ &=\theta b+(1-\theta)b \\ &=b \end{align} \]

这表明了仿射组合 \(\theta x_1+(1-\theta)x_2\) 也是 \(C\) 的一个元素。和仿射集 \(C\) 相关联的子空间 \(V\)\(A\) 的零空间。

总之我们可以说,每个仿射集都可以表达成线性方程组的解集。

包括一个 \(C \subseteq \mathbb{R}\) 的所有点的仿射组合的集合称为 \(C\)仿射包,记作 \(\operatorname{aff}C\)

\[ \operatorname{aff}C=\{\sum_{i=1}^k \theta_ix_i\mid x_1,\ldots,x_k\in C,\sum_{i=1}^k\theta_i=1\} \]

\(C\) 的仿射包是包含 \(C\) 的最小仿射集。如果 \(S\) 是一个仿射集,且 \(C\subseteq S\),那么 \(\operatorname{aff}C\subseteq S\)

2.1.3 仿射维数和相对内部

我们定义一个集合 \(C\)仿射维数\(\operatorname{aff}C\) 的维数。仿射维数在凸分析和凸优化中比较有用,但是它和其他领域中维数的定义并不一样。例如,考虑一个 \(\mathbb{R}^2\) 上的单位圆,即 \(\{x\in\mathbb{R}^2\mid x_1^2+x_2^2=1\}\)。它的仿射包为 \(\mathbb{R}^2\),因此它的仿射维数为 2。但是在通常意义上,一个 \(\mathbb{R}^2\) 上的圆的维数为 1。

如果一个集合 \(C\subseteq\mathbb{R}^n\) 的仿射维数小于 \(n\),那么这个集合的仿射集 \(\operatorname{aff}C\neq \mathbb{R}^n\)。因此,我们可以定义一个集合 \(C\)相对内部(记作 \(\operatorname{relint}C\),表示相对 \(\operatorname{aff}C\) 的内部)为:

\[ \operatorname{relint}C=\{x\in\mathbb{R}^n\mid B(x,r)\cap\operatorname{aff}C\subseteq C \mathrm{\;for\,some\,} r>0\} \]

其中 \(B(x,r)=\{y\in\mathbb{R}^n\mid \Vert y-x\Vert\leq r\}\) 是在范数 \(\Vert\cdot\Vert\)(这里 \(\Vert\cdot\Vert\) 为任意范数,所有范数都会定义相同的相对内部)下以 \(x\) 为中心半径为 \(r\) 的球体。进而我们定义 \(C\)相对边界\(\operatorname{cl}C \setminus \operatorname{relint}C\),其中 \(\operatorname{cl}C\)\(C\) 的闭包。

Example 2.2 考虑到一个 \(\mathbb{R}^3\)\((x_1, x_2)\) 平面的一个正方形,如下定义:

\[ C=\{x\in\mathbb{R}^3\mid -1\leq x_1\leq 1,-1\leq x_2\leq 1, x_3=0\} \]

其仿射包为整个 \((x_1, x_2)\) 平面,即 \(\operatorname{aff}C=\{x\in\mathbb{R}^3\mid x_3=0\}\)。因此 \(C\) 的相对内部为 \(\operatorname{relint}C=\{x\in\mathbb{R}^3\mid x_3=0\}\),而相对边界为 \(\operatorname{cl}C \setminus \operatorname{relint}C=\{x\in\mathbb{R}^3\mid x_3\neq 0\}\)\(C\) 的内部为空集,但是其相对内部为

\[ \operatorname{relint}C=\{x\in\mathbb{R}^3\mid -1< x_1 < 1, -1 < x_2 < 1, x_3=0\} \]

其在 \(\mathbb{R}^3\) 上的边界为其自身其相对边界为

\[ \{x\in\mathbb{R}^3\mid \max\{|x_1|,|x_2|\}=1, x_3=0\} \]

2.1.4 凸集

如果连接一个集合 \(C\) 中任意两点的线段仍在 \(C\) 中,那么我们称 \(C\)凸集,也就是说,对于任意的 \(x_1, x_2\in C\) 以及任意 \(0\leq\theta\leq 1\),都有

\[ \theta x_1+(1-\theta)x_2\in C \]

通俗地说,如果一个集合中任意一点都能被另外任意一点“看见”(光沿直线传播?),这个集合就是凸集。所有仿射集都是凸集,因为仿射集一定包含了连接其中任意两点的线段。如图。

我们将 \(\sum_{i=1}^k \theta_ix_i, \sum_{i=1}^k\theta_i=1, \theta_i\geq 0\) 称为 \(C\)凸组合。和仿射集一样,一个集合为凸集当且仅当其所有凸组合都在集合中。凸组合其实可以被看作为几个点的混合加权平均

一个集合 \(C\)凸包(记作 \(\operatorname{conv}C\))是集合 \(C\) 的所有点的凸组合组成的集合:

\[ \operatorname{conv}C=\{\sum_{i=1}^k \theta_ix_i\mid \sum_{i=1}^k\theta_i=1, \theta_i\geq 0, x_i\in C\} \]

顾名思义,凸包永远是凸的。它是包含集合 \(C\) 的最小凸集。如果集合 \(B\) 是包含集合 \(C\) 的凸集,那么 \(\operatorname{conv}C\subseteq B\)。如图。

凸组合的概念可以推广到级数、积分或者概率分布等等。假设 \(\theta_1, \theta_2\) 满足:

\[ \theta_i\geq0,\quad i=1,2\cdots,\quad\sum_{i=1}^\infty\theta_i=1 \]

并且 \(x_1, x_2, \cdots \in C\)\(C\subseteq \mathbb{R}^n\) 是凸集,那么(如果级数收敛的话)

\[ \sum_{i=1}^\infty\theta_ix_i\in C \]

更广义地来讲,假设映射 \(p: \mathbb{R}^n\to\mathbb{R}\) 满足对于 \(\forall x\in C\)\(\int_C p(x)\mathrm{d}x=1\),其中 \(C\subseteq\mathbb{R}^n\) 是凸集,那么(如果积分存在的话)

\[ \int_C p(x)x\mathrm{d}x\in C \]

更通常的情况下,假设 \(C\subseteq\mathbb{R}^n\) 是凸集且 \(x\in C\) 是一个随机向量,则有 \(\boldsymbol{E}x\in C\)。当然有一些特殊情况,比如 \(x\) 服从 Bernoulli 分布,即 \(P(x=x_1)=\theta, P(x=x_2)=1-\theta\),我们就回到了最开始的两点问题。

2.1.5

如果一个集合 \(C\) 对于 \(\forall x\in C,\theta\geq 0\) 都有 \(\theta x\in C\),则称 \(C\) 为一个。而如果集合 \(C\) 既是凸集又是一个锥,则称集合 \(C\) 为凸锥,意味着对于 \(\forall x_1, x_2\in C, \theta_1, \theta_2\geq 0\),我们有:

\[ \theta_1x_1+\theta_2x_2\in C \]

通过这种形式表出的点在几何上可以描述为形成顶点为 \(0\),边界穿过 \(x_1, x_2\) 的二维饼片。(如图)

满足形式 \(\sum_{i=1}^k \theta_i x_i, \theta_i\geq 0\) 的点称作 \(x_1, \cdots, x_k\)锥组合(或非负线性组合)。如果一个点 \(x_i\) 在凸集 \(C\) 中,那么 \(x_i\) 的所有锥组合都在 \(C\) 中。相反地,一个集合 \(C\) 为一个凸锥当且仅当其包含其元素所有的锥组合。类似凸组合,锥组合的思想也可以推广到级数和积分上。

集合 \(C\) 的锥包是 \(C\) 所有元素的凸组合,即

\[ \{\sum_{i=1}^k\theta_ix_i\mid x_i\in c,\theta_i\geq0,i=1,\ldots,k\} \]

其也是包含集合 \(C\) 的最小凸锥。(如图)

2.2 一些重要的例子

在这一节中,我们将会讲述本书中我们会遇到的几种重要的凸集。我们先从几个简单容易理解的例子开始。

  • 空集 \(\emptyset\)、任意一个孤立的点 \(\{x_0\}\)、整个 \(\mathbb{R}^n\) 空间都是 \(\mathbb{R}^n\) 的仿射(都仿射了,肯定是凸的)子集。
  • 任意一条直线一定是仿射的。如果它穿过零点,它就是一个子空间,也是一个凸锥。
  • 一条线段一定是凸的,但是除非它缩小到一个点,否则它不仿射。
  • 一条射线,拥有 \(\{x_0+\theta v\mid\theta\geq 0, v\neq 0\}\) 的形式,是凸的,但是不仿射。如果它穿过零点,它就是一个凸锥。
  • 所有子空间既仿射又是凸锥。

2.2.1 超平面和半空间

一个超平面具有如下形式:

\[ \{x\in\mathbb{R}^n\mid a^Tx=b\} \]

其中 \(a\in\mathbb{R}, a\neq 0, b\in\mathbb{R}\)。从代数上来讲,这是非奇异线性方程组 \(a^Tx=b\) 的解集,因此是一个仿射集。从几何上来讲,超平面 \(\{x\mid a^Tx=b\}\) 可以表达成一个常量和给定向量 \(a\) 的内积组成的点集;常量 \(b\in\mathbb{R}\) 表示了和原超平面的偏差。这种几何表达法可以通过这种形式方便理解:

\[ \{x\mid a^T(x-x_0)=0\} \]

其中 \(x_0\) 是超平面上任意一个点(即任意一个满足 \(a^Tx_0=b\) 的点)。这种形式可以写成:

\[ \{x\mid a^T(x-x_0)=0\}=x_0+a^\perp \]

其中 \(a^\perp\)\(a\) 的正交补(即其中所有的向量都与 \(a\) 正交):

\[ a^\perp=\{v\mid a^Tv=0\} \]

这种几何的表达形式(如图所示):

超平面将 \(\mathbb{R}^n\) 空间分成两个半空间。一个(闭)半空间是一种满足如下形式的集合:

\[ \{x\mid a^Tx\leq b\} \]

其中 \(a\neq 0\),即非奇异线性不等式组的解集。半空间是凸的,但是不仿射。(如图)

半空间同样可以表达成这样的形式:

\[ \{x\mid a^T(x-x_0)\leq 0\} \]

其中 \(x_0\) 是相关超平面上任意一个点(即任意一个满足 \(a^Tx_0=b\) 的点)。(?)

半空间(哪个?)的边界为超平面 \(\{x\mid a^Tx=b\}\)。半空间 \(\{x\mid a^Tx\leq b\}\) 的内部 \(\{x\mid a^Tx< b\}\) 被称作开半空间

2.2.2 Euclidean 球和椭球

\(\mathbb{R}^n\) 空间中 Euclidean 球(或者简而言之地称作球)是一种满足如下形式的集合:

\[ B(x_c, r)=\{x\mid \Vert x-x_c\Vert_2\leq r\}=\{x\mid(x-x_c)^T(x-x_c)\leq r^2\}, \]

其中 \(r>0\)\(\Vert\cdot\Vert_2\) 代表 Euclidean 范数,即 \(\Vert x\Vert_2=(x^Tx)^{1/2}\)。向量 \(x_c\) 代表球心,标量 \(r\) 是其半径;\(B(x_c, r)\) 包含了所有距离球心 \(x_c\) 不超过 \(r\) 的点。Euclidean 的另外一种常用表达形式是:

\[ B(x_c, r)=\{x_c+ru\mid \Vert u\Vert_2\leq 1\} \]

Euclidean 球是一个凸集:

如果 \(\Vert x_1-x_c\Vert_2\leq r\)\(\Vert x_2-x_c\Vert_2\leq r\) 以及 \(0\leq\theta\leq 1\),则有:

\[ \begin{align} \Vert\theta x_1+(1-\theta)x_2-x_c\Vert_2&=\Vert\theta(x_1-x_c)+(1-\theta)(x_2-x_c)\Vert_2\\ &\leq\theta\Vert x_1-x_c\Vert_2+(1-\theta)\Vert x_2-x_c\Vert_2\\ &\leq r. \end{align} \]

(这里我们用到了 \(\Vert\cdot\Vert_2\) 的齐次性和三角不等式)

还有一种类似的凸集是椭球,它是一种满足如下形式的集合:

$$