Josh's Note — 凸优化
Part 1.1 凸集—仿射集合和凸集

发表于 2022-03-29 更新于 2024-06-13 分类于 Josh 的学习笔记，凸优化，数学，凸集，凸优化阅读次数：本文字数： 2.7k 阅读时长 ≈ 10 分钟

1. 直线与线段

$ $ 设 $x_1 \ne x_2$ 是 $\mathbf{R}^n$ 空间中的两个点，则具有下列形式的点

\[ y = \theta x_1 + (1-\theta)x_2,\theta \in \mathbf{R} \]

组成一条穿过 $x_1$ 和 $x_2$ 的直线（line）。参数 $\theta = 0$ 和 $\theta = 1$ 分别对应 $y=x_2$ 和 $y = x_1$。参数 $\theta$ 的值在 0 和 1 之间变动，构成了 $x_1$ 和 $x_2$ 之间的（闭）线段（(closed) line segment）。

另一种 $y$ 的表示形式

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

可以解释为：$y$ 是基点（base point）$x_2$（对应 $\theta = 0$）和方向（direction）$x_1 - x_2$（由 $x_2$ 指向 $x_1$）乘以参数 $\theta$ 的和。因此，$\theta$ 给出了 $y$ 在由 $x_2$ 通向 $x_1$ 的路上的位置。当 $\theta$ 由 $0$ 增加到 $1$，点 $y$ 相应地由 $x_2$ 移动到 $x_1$。如果 $\theta > 1$，点 $y$ 在超越了 $x_1$ 的直线上。图 1 给出了直观的解释。

图 1. 通过 x_1 和 x_2 的直线可以参数化描述为 \theta x_1 + (1-\theta)x_2，其中 \theta 在 \mathbf{R} 上变化。x_1 和 x_2 之间的线段由深色所示，对应处于 0 和 1 之间的 \theta。 — 图 1. 通过 $x_1$ 和 $x_2$ 的直线可以参数化描述为 $\theta x_1 + (1-\theta)x_2$，其中 $\theta$ 在 $\mathbf{R}$ 上变化。$x_1$ 和 $x_2$ 之间的线段由深色所示，对应处于 $0$ 和 $1$ 之间的 $\theta$。

2. 仿射集合和凸集

如果通过集合 $C \subseteq \mathbf{R}^n$ 中任意两个不同点的直线仍然在集合 $C$ 中，那么称集合 $C$ 是仿射（affine）的。也就是说，$C \subseteq \mathbf{R}^n$ 是仿射的等价于：对于任意 $x_1, x_2 \in C$ 及 $\theta \in \mathbf{R}$ 有 $\theta x_1 + (1-\theta)x_2 \in C$。换言之，$C$ 包含了 $C$ 中任意两点的系数之和为 $1$ 的线性组合。

这个概念可以扩展到多个点的情况。若 $\theta_1 + \cdots + \theta_k = 1$，则称具有 $\theta_1 x_1 + \cdots + \theta_k x_k$ 形式的点为 $x_1, \cdots, x_k$ 的仿射组合（affine combination）。利用仿射集合的定义（即仿射集合包含其中任意两点的仿射组合），可以归纳出以下结论：一个仿射集合包含其中任意点的仿射组合，即如果 $C$ 是一个仿射集合，$x_1, \cdots, x_k \in C$，并且 $\theta_1 + \cdots + \theta_k = 1$，那么 $\theta_1 x_1 + \cdots + \theta_k x_k$ 仍然在 $C$ 中。

如果 $C$ 是一个仿射集合并且 $x_0 \in C$，则集合

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

是一个子空间，即关于加法和数乘是封闭的。

简单说明 设 $v_1, v_2 \in V$，$\alpha, \beta \in \mathbf{R}$，则有 $v_1 + x_0 \in C$，$v_2 + x_0 \in C$。因为 $C$ 是仿射的，且 $\alpha + \beta + (1 - \alpha - \beta) = 1$，所以
\[ \alpha v_1 + \beta v_2 + x_0 = \alpha (v_1 + x_0) + \beta(v_2 + x_0) + (1 - \alpha - \beta)x_0 \in C \]
由 $\alpha v_1 + \beta v_2 + x_0 \in C$，可知 $\alpha v_1 + \beta v_2 \in V$。

因此，仿射集合 $C$ 可以表示为

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

即一个子空间加上一个偏移。与仿射集合 $C$ 相关联的子空间 $V$ 与 $x_0$ 的选取无关，所以 $x_0$ 可以是 $C$ 中的任意一点。定义仿射集合 $C$ 的维数为子空间 $V = C - x_0$ 的维数，其中 $x_0$ 是 $C$ 中的任意元素。

举例 线性方程组的解集。线性方程组的解集 $C = \{x\mid Ax= b\}$ 是一个仿射集合，其中 $A\in\mathbf{R}^{m\times n}$，$b \in \mathbf{R}^{m}$ 。为说明这点，设 $x_1,x_2\in C$，即 $Ax_1 = b, Ax_2 = b$。则对于任意 $\theta$，有
\[\begin{aligned} A(\theta x_1 + (1-\theta)x_2) &= \theta Ax_1 + (1-\theta)Ax_2 \\ &= \theta b + (1-\theta)b \\ &= b \end{aligned}\]
这表明任意的仿射组合 $\theta x_1 + (1-\theta)x_2$ 也在 $C$ 中，并且与仿射集合 $C$ 相关联的子空间就是 $A$ 的零空间。
反之，任意仿射集合可以表示为一个线性方程组的解集。

由集合 $C \subseteq \mathbf{R}^n$ 中的点的所有仿射组合组成的集合称为 $C$ 的仿射包（affine hull），记为 $\mathop{\bf aff}{C}$：

\[ \mathop{\bf aff}{C} = \left\{ \theta_1 x_1 + \cdots + \theta_k x_k\mid x_1, \cdots, x_k \in C, \theta_1 + \cdots + \theta_k = 1 \right\} \]

仿射包是包含 $C$ 的最小的仿射集合，也就是说：如果 $S$ 是满足 $C \subseteq S$ 的仿射集合，那么 $\mathop{\bf aff}{C} \subseteq S$。

3. 仿射维数与相对内部

集合 $C$ 的仿射维数定义为其仿射包的维数。仿射维数在凸分析及凸优化中十分有用，但它与其他维数的定义常常不相容。

举例考虑 $\mathbf{R}^2$ 上的单位圆环 $\left\{x\in\mathbf{R}^2\mid x_1^2 + x_2^2 = 1 \right\}$。它的仿射包是全空间 $\mathbf{R}^2$，所以其仿射维数为 $2$。但是，在其他大多数维数的定义下，$\mathbf{R}^2$ 上的单位圆环的维数为 $1$。

如果集合 $C \subseteq \mathbf{R}^n$ 的仿射维数小于 $n$，那么这个集合在仿射集合 $\mathop{\bf aff}C \ne \mathbf{R}^n$ 中。定义集合 $C$ 的相对内部（relative interior）为 $\mathop{\bf aff}C$ 的内部，记为 $\mathop{\bf relint}C$，即

\[ \mathop{\bf relint}C = \left\{ x \in C\mid B(x,r) \cap \mathop{\bf aff}C \subseteq C\ 对于某些\ r > 0 \right\} \]

其中 $B(x,r) = \left\{ y\mid \left\| y-x \right\| \leqslant r \right\}$，即半径为 $r$，中心为 $x$ 并由范数 $\| \cdot \|$ 定义的球（这里的 $\| \cdot \|$ 可以是任意范数，并且所有范数定义了相同的相对内部）。于是可以定义集合 $C$ 的相对边界（relative boundary）为 $\mathop{\bf cl}C\ \setminus \mathop{\bf relint}C$，此处 $\mathop{\bf cl}C$ 表示 $C$ 的闭包。

这里的 “$\setminus$” 表示“集合减”，也即集合 $C$ 的相对边界为其闭包 $\mathbf{cl}\ C$ 减去其相对内部 $\mathbf{relint}\ C$。

举例考虑 $\mathbf{R}^3$ 中处于 $(x_1，x_2)$ 平面的一个正方形，定义
\[ C = \{x \in \mathbf{R}\mid -1\leqslant 1, -1\leqslant x_2\leqslant 1, x_3 = 0\} \]
其仿射包为 $(x_1,x_2)$-平面，即 $\mathop{\bf aff}C = \{x\in\mathbf{R}^3\mid x_3 = 0 \}$。$C$ 的内部为空，但其相对内部为
\[ \mathop{\bf relint}C = \{x\in\mathbf{R}^3\mid -1<x_1<1,-1<x_2<1,x_3 = 0\} \]
$C$（在 $\mathbf{R}^3$ 中）的边界是其自身，而相对边界是其边框，
\[ \{x \in \mathbf{R}^3\mid \max\{|x_1|,|x_2|\} = 1,x_3 = 0\} \]

4. 凸集

集合 $C$ 被称为凸集（convex set），如果 $C$ 中任意两点间的线段仍然在 $C$ 中，即对于任意 $x_1, x_2 \in C$ 和满足 $0 \leqslant \theta \leqslant 1$ 的 $\theta$ 都有

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

粗略地看，如果集合中的每一点都可以被其他点沿着它们之间一条无阻碍的路径看见，那么这个集合就是凸集。所谓无阻碍，是指整条路径都在集合中。由于仿射集包含穿过集合中任意不同两点的整条直线，任意不同两点间的线段自然也在集合中。因而仿射集是凸集。图 2 显示了 $\mathbf{R}^2$ 空间中一些简单的凸和非凸集合。

图 2. 一些简单的凸和非凸集合。左：包含其边界的六边形是凸的。中：肾形集合不是凸的，因为图中所示集合中两点间的线段不为集合所包含。右：仅包含部分边界的正方形不是凸的。

集合 $C$ 中所有点的凸组合的集合称为集合 $C$ 的凸包（convex hull），记为 $\mathop{\bf conv}C$：

\[ \mathop{\bf conv}C = \left\{ \theta_1 x_1 + \cdots + \theta_k x_k\mid x_i \in C, \theta_i \geqslant 0, i = 1,\cdots, k, \theta_1 + \cdots + \theta_k = 1 \right\} \]

顾名思义，凸包 $\mathop{\bf conv}C$ 总是凸的。它是包含 $C$ 的最小的凸集。也就是说，如果 $B$ 是包含 $C$ 的凸集，那么 $\mathop{\bf conv}C \subseteq B$。图 3 展示了凸包的定义。

图 3. \mathbf{R}^2 上两个集合的凸包。左：（如图所示的）十五个点的集合的凸包是一个五边形示）。右：图 2 中的肾形集合的凸包是阴影所示的集合。 — 图 3. $\mathbf{R}^2$ 上两个集合的凸包。左：（如图所示的）十五个点的集合的凸包是一个五边形示）。右：图 2 中的肾形集合的凸包是阴影所示的集合。

集合 $C$ 的仿射包 $\mathbf{aff}\ C$ 和凸包 $\mathbf{Conv}\ C$ 的区别是参数 $\theta$ 的定义域。可以看出，仿射包 $\mathbf{aff}\ C$ 包含凸包 $\mathbf{Conv}\ C$，因此集合 $C$ 的仿射包是凸集。

凸组合的概念可以扩展到无穷级数、积分以及大多数形式的概率分布。假设 $\theta_1,\theta_2,\cdots$ 满足

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

并且 $x_1, x_2, \cdots \in C$，其中 $C \subseteq \mathbf{R}^n$ 为凸集。那么，如果下面的级数收敛，则有

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

更一般地，假设 $p:\mathbf{R}^n\to\mathbf{R}$ 对所有 $x \in C$ 满足 $p(x) \geqslant 0$，并且 $\displaystyle \int_C p(x) \mathrm{d}x = 1$，其中 $C \subseteq \mathbf{R}^n$ 是凸集。那么，如果下面的积分存在，则有

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

最一般的情况，设 $C \subseteq \mathbf{R}^n$ 是凸集，$x$ 是随机变量，并且 $x \in C$ 的概率为 $1$，那么 $\mathbb{E}\{x\} \in C$。事实上，这一形式包含了前述的特殊情况。例如，假设随机变量 $x$ 只在 $x_1$ 和 $x_2$ 中取值，其概率分别为 $\mathbf{prob}(x=x_1) = \theta$ 和 $\mathbf{prob}(x=x_2) = 1-\theta$，其中 $0 \leqslant \theta \leqslant 1$。于是，$\mathbb{E}\{x\} = \theta x_1 + (1-\theta)x_2$，即回到了两个点的简单的凸组合。

5. 锥

如果对于任意 $x \in C$ 和 $\theta \geqslant 0$ 都有 $\theta x \in C$，我们称集合 $C$ 是锥（cone）或者非负齐次（nonnegative homogeneous）。如果集合 $C$ 是锥，并且是凸的，则称 $C$ 为凸锥（convex cone），即对于任意 $x_1, x_2 \in C$ 和 $\theta_1, \theta_2 \geqslant 0$，都有

\[ \theta_1 x_1 + \theta_2 x_2 \in C \]

在几何上，具有此类形式的点构成了二维的扇形，这个扇形以 $0$ 为顶点，边通过 $x_1$ 和 $x_2$（如图 4所示）。

图 4. 扇形展示了所有具有形式 \theta_1 x_1 + \theta_2 x_2 的点，其中 \theta_1, \theta_2 \geqslant 0。扇形的顶点 (\theta_1 = \theta_2 = 0) 在 0；其边界（对应于 $\theta_1 = 0 或 \theta_2 = 0) 穿过点 x_1 和 x_2。 — 图 4. 扇形展示了所有具有形式 $\theta_1 x_1 + \theta_2 x_2$ 的点，其中 $\theta_1, \theta_2 \geqslant 0$。扇形的顶点 ($\theta_1 = \theta_2 = 0$) 在 $0$；其边界（对应于 $$\theta_1 = 0$ 或 $\theta_2 = 0$) 穿过点 $x_1$ 和 $x_2$。

具有 $\theta_1 x_1 + \cdots + \theta_k x_k, \theta_1,\cdots,\theta_k \geqslant 0$ 形式的点称为 $x_1,\cdots,x_k$ 的锥组合（conic combination）（或非负线性组合（nonnegative linear combination））。如果 $x_i$ 均属于凸锥 $C$，那么，$x_i$ 的每一个锥组合也在 $C$ 中。反言之，集合 $C$ 是凸锥的充要条件是它包含其元素的所有锥组合。如同凸（或仿射）组合一样，锥组合的概念可以扩展到无穷级数和积分中。

集合 $C$ 的锥包（conic hull）是 $C$ 中元素的所有锥组合的集合，即

\[ \left\{ \theta_1 x_1 + \cdots + \theta_k x_k\mid x_i \in C, \theta_i \geqslant 0, i = 1,\cdots,k \right\} \]

它是包含 $C$ 的最小的凸锥（如图 5 所示）。

类似仿射包，集合 $C$ 的凸包 $\mathbf{Conv}\ C$ 和锥包的区别是参数 $\theta$ 的定义域。可以看出，锥包包含凸包 $\mathbf{Conv}\ C$，因此集合 $C$ 的锥包是凸集。

参考文献

Stephen P. Boyd and Lieven Vandenberghe, Convex optimization. Cambridge, UK: Cambridge University Press, 2004.
Stephen P. Boyd and Lieven Vandenberghe, 凸优化. 北京: 清华大学出版社, 2013.