仿射集&凸集

本文首发于公众号：程序员与机器学习

本文要学习的主要内容是凸优化中的仿射集、凸集和凸锥的概念。

---

例一：给定两个点，如何描述一条直线？

给定两点${x_1} \ne {x_2} \in R{^n},\theta \in R$x1​​=x2​∈Rn,θ∈R，这条直线可以描述为$y = \theta {x_1} + (1 - \theta ){x_2} = {x_2} + \theta ({x_1} - {x_2})$y=θx1​+(1−θ)x2​=x2​+θ(x1​−x2​)。

我们观察上式等式最右端，相当于以$x_2$x2​为基点，沿着$x_1-x_2$x1​−x2​的方向变化$\theta$θ大小。

例二：给定两个点，如何描述一条线段？

与例一不同的是，我们要对$\theta$θ的取值范围加以限制，即$\theta \in [0,1]$θ∈[0,1]。此时，$y$y只能在$x_1$x1​和$x_2$x2​之间变换。

仿射集

仿射集(Affine Sets)：一个集合$c$c是仿射集，对$\forall {x_1},{x_2} \in c$∀x1​,x2​∈c，连接两点的直线仍在$c$c内。

比如：直线是仿射集；线段不是仿射集；二维空间是仿射集；在二维空间中选定取值范围，该范围不是仿射集。

上述定义是针对两个点而言的，我们通过仿射组合的概念将其扩展到多个点。

**仿射组合：**设仿射集$c$c中有$k$k个点，$\forall {x_1}, \ldots ,{x_2} \in c,{\theta _1}, \ldots {\theta _k} \in R,{\theta _1} + \ldots + {\theta _k} = 1$∀x1​,…,x2​∈c,θ1​,…θk​∈R,θ1​+…+θk​=1。此时仿射组合定义为${\theta _1}{x_1} + \ldots + {\theta _k}{x_k} \in c$θ1​x1​+…+θk​xk​∈c。

【分析】

我们分析仿射集的定义，其中最关键的限制即${\theta _1} + \ldots + {\theta _k} = 1$θ1​+…+θk​=1。是否存在一些特殊的仿射集能够摆脱这样的限制呢？

如下图($a$a)，若去掉该限制，那么${\theta _1}{x_1} + \ldots + {\theta _k}{x_k}$θ1​x1​+…+θk​xk​会落到仿射集$c$c(橘色直线)之外，显然不成立。

但若如下图($b$b)，仿射集$c$c经过原点，上述限制则可以忽略。

我们会发现，上图($b$b)中的仿射集相当于对上图($a$a)中的仿射集做了平移。下面我们以数学符号描述上述性质。

定义：
$V = c - {x_0} = \{ x - {x_0}|x \in c\} ,\forall {x_0} \in c$V=c−x0​={x−x0​∣x∈c},∀x0​∈c
这里，我们定义了新的集合$V$V，它表示对仿射集$c$c中的所有点都减去任意一个$c$c中的点$x_0$x0​，即对整个集合做了平移。

我们称，$V$V为与$c$c相关的子空间。

此时，$V$V仍然是仿射集，且摆脱了${\theta _1} + \ldots + {\theta _k} = 1$θ1​+…+θk​=1的限制。因为此时$V$V中的$x_0$x0​点被其自身减掉之后变成了原点，所以$V$V一定经过原点。

---

下面介绍仿射包的概念。

例三：给定任意一个集合$c$c，如何构造尽可能小的仿射集？

我们通过定义仿射包来构建仿射集：
$aff \ \ \ c = \{ {\theta _1}{x_1} + \ldots + {\theta _k}{x_k}|\forall {x_1}, \ldots ,{x_2} \in c,{\theta _1} + \ldots + {\theta _k} = 1\}$aff   c={θ1​x1​+…+θk​xk​∣∀x1​,…,x2​∈c,θ1​+…+θk​=1}
如果集合$c$c本身就是仿射集，那么其仿射包就是$c$c本身。

凸集

定义：一个集合$c$c是凸集，当连接$c$c中任意两点之间的线段仍在$c$c内。数学定义为(同样可扩展到多点情况)：
$\theta {x_1} + (1 - \theta ){x_2},\forall {x_1},{x_2} \in c,\forall \theta \in [0,1],{\theta _1} + \ldots + {\theta _k} = 1$θx1​+(1−θ)x2​,∀x1​,x2​∈c,∀θ∈[0,1],θ1​+…+θk​=1
对应于仿射集的仿射组合和仿射包，凸集也有它的凸组合和凸包。不同的是，均多了${\theta _1}, \ldots {\theta _k} \in [0,1]$θ1​,…θk​∈[0,1]限制。

例四：

• ($a$a)：凸集。根据定义判断，连接集合内任意两点的线段仍位于集合内。
• ($b$b)：非凸集。根据定义判断，图中凹陷处不满足定义。
• ($c$c)：非凸集。空白圆圈表示集合中的空缺点。比如我们在左边任意取两个点画一条线段，因为该边存在空缺点，所以所画的线段并不位于该集合内。
• ($d$d)：凸集。空白圆圈表示集合中的空缺点。但是该空缺点位于集合的顶点，并不能构成($c$c)中的情况。

凸锥

一系列的定义同样对应仿射集、凸集，有凸锥组合、凸锥包。区别于前两者集合，凸锥的限制是：射线。

这里直接给出定义：
${\theta _1}{x_1} + {\theta _2}{x_2} \in c,\forall {x_1},{x_2} \in c,{\theta _1},{\theta _2} \ge 0$θ1​x1​+θ2​x2​∈c,∀x1​,x2​∈c,θ1​,θ2​≥0

总结

集合类型	限制条件	备注
仿射集	${\theta _1}, \ldots {\theta _k} \in R，{\theta _1} + \ldots + {\theta _k} = 1$θ1​,…θk​∈R，θ1​+…+θk​=1	直线
凸集	$\forall \theta \in [0,1],{\theta _1} + \ldots + {\theta _k} = 1$∀θ∈[0,1],θ1​+…+θk​=1	线段
凸锥	${\theta _1}, \ldots {\theta _k} \in R，{\theta _1} , \ldots {\theta _k} \ge 0$θ1​,…θk​∈R，θ1​,…θk​≥0	射线

另：一个点，既是仿射集又是凸集，当该点经过原点时为凸锥。