凸集

仿射

仿射集(Affine Sets)

等价定义1: 若对集合C中的任意两点x₁, x₂,都有过x₁, x₂的直线也在C中，则称C为仿射集 即： ∀x₁, x₂ ∈ C, ∀θ ∈ R ⇒ y = θx₁ + (1 − θ)x₂ ∈ C.

等价定义2：设 x₁, …, x_k ∈ C, ∀θ₁, …, θ_k ∈ R,且$\sum_{i=1}^k\theta_i=1$,有$\sum_{i=1}^k\theta_kx_k\in C$,则称C 为 仿射集.

例如：直线是仿射集，全空间是仿射集，线段不是仿射集。线性方程组的解C x|Ax = b是仿射集，且齐次线性方程组的解V {x|Ax = 0}满足更好的性质，即 ∀x, y ∈ V, α, β ∈ R,有 αx + βy ∈ V,而不必要求 α + β = 1 通常称V是C的仿射子空间

仿射组合

仿射组合：设x₁, …, x_k ∈ C, θ₁, …, θ_k ∈ R, θ₁ + ⋯ + θ_k = 1, θ₁x₁ + ⋯ + θ_kx_k称为仿射组合 ⇒若 C 为仿射集，则仿射组合也在 C 内，证明如下 $$\begin{aligned}&\frac{\theta_{1}}{\theta_{1}+\theta_{2}}x_{1}+\frac{\theta_{2}}{\theta_{1}+\theta_{2}}x_{2}\in C\\&(\theta_{1}+\theta_{2})\left(\frac{\theta_{1}}{\theta_{1}+\theta_{2}}x_{1}+\frac{\theta_{2}}{\theta_{1}+\theta_{2}}x_{2}\right)+(1-\theta_{1}-\theta_{2})x_{3}\in C\\&\Leftrightarrow\theta_{1}x_{1}+\theta_{2}x_{2}+\theta_{3}x_{3}\in C,\quad\theta_{1}+\theta_{2}+\theta_{3}=1\end{aligned}$$ 按照此思路可以递归的证明到多个点进行仿射组合的情况

仿射包

对于任意集合C,仿射包aff C是包含C的最小仿射集，
aff C = {θ₁x₁ + … + θ_kx_k|∀x₁, …, x_k ∈ C, θ₁ + … + θ_k = 1}

不管集合C是什么, aff C都一定是仿射集, 且是所有包含C的仿射集中最小的仿射集.也就是说我们可以从任意集合中构造一个特殊的仿射集。 举个例子

{x₁, x₂}的仿射包是连接两点的直线，{x₁, x₂, x₃}的仿射包是R²

凸

凸集

一个集合C为凸集，当且仅当任意连接C内两点的线段也在C内，即 ∀x₁, x₂ ∈ C, ∀θ ∈ [0, 1], θx₁ + (1 − θ)x₂ ∈ C 等价定义为C中任意多个元素的凸组合也在C内

凸组合

x₁, …, x_k ∈ C, θ₁, …, θ_k ∈ [0, 1], θ₁ + ⋯ + θ_k = 1, θ₁x₁ + ⋯ + θ_kx_k
凸集包含其任意元素的凸组合

凸包

对任意集合C,包含C的最小凸集称为C的凸包
Conv(C) = {θ₁x₁ + ⋯ + θ_kx_k|x₁, …, x_k ∈ C, θ₁, …, θ_k ∈ [0, 1], θ₁ + ⋯ + θ_k = 1}

锥

• 椎：∀x ∈ C, θ ≥ 0 ⇒ θx ∈ C

• 凸锥∀x₁, x₂ ∈ C, θ₁, θ₂ ≥ 0 ⇒ θ₁x₁ + θ₂x₂ ∈ C

• 凸锥组合：θ₁x₁ + ⋯ + θ_kx_k, θ₁, …, θ_k ≥ 0

• 凸锥包：{θ₁x₁ + ⋯ + θ_kx_k|x₁, …, x_k ∈ C, θ₁, …, θ_k ≥ 0}

总结

设 x₁, …, x_k ∈ C, ∀θ₁, …, θ_k ∈ C,在下表对应的情况下，

$$\begin{array}{|c|c|c|}\hline\text{仿射集}&\text{凸集}&\text{凸锥}\\\hline\theta_1+\cdots+\theta_k=1&\theta_1+\cdots+\theta_k=1\\\theta_1,\ldots,\theta_k\in R&\theta_1,\ldots,\theta_k\in[0,1]&\theta_1,\ldots,\theta_k\geq0\\\hline\end{array}$$

有$\sum_{i=1}^k\theta_kx_k\in C$，则C为仿射集/凸集/凸锥。

凸集举例

• Rⁿ空间，Rⁿ空间的子空间

• 任意直线(若过原点也为凸锥),任意线段，射线{x₀ + θv|θ ≥ 0, x ∈ Rⁿ, θ ∈ R, v ∈ Rⁿ}

• 超平面与半空间

• 球和椭球

• 多面体(Polyhedron)和单纯形(Simplex)

• 对称矩阵集合，对称半正定矩阵集合，对称正定矩阵集合

超平面

• 超平面(hyperplane){x ∣ a^Tx = b}为平面在高维空间中的扩展 ，它是凸集，是仿射集，若否过原点则是凸锥
• 半空间(halfspace)a^Tx ≥ b或a^Tx ≤ b为由超平面分开的全空间的一半，它是凸集，非仿射集，若过原点则是凸锥

球

$B(x_{c},r)=\{x\mid\|x-x_{c}\|_{2}\leq r\}=\{x\mid\sqrt{(x-x_{c})^{T}(x-x_{c})}\leq r\}$是凸集
证：
$$\begin{aligned}&\forall\theta\in[0,1]\text{,取 }f(x)=\|x-x_c\|_2\\&\|\theta x_1+(1-\theta)x_2-x_c\|_2=\|\theta(x_1-x_c)+(1-\theta)(x_2-x_c)\|_2\\&\leq \theta\|x_{1}-x_{c}\|_{2}+(1-\theta)\|x_{2}-x_{c}\|_{2}\end{aligned}$$

椭球

ε(x_c, P) = {x ∣ (x − x_c)^TP⁻¹(x − x_c) ≤ 1}, x_c ∈ Rⁿ, P ∈ S₊₊ⁿ 其中P为对角矩阵，对角线上为矩阵的奇异值的平方，矩阵的奇异值对应了椭球的半轴长

多面体

多面体(polyhedron)是半空间与超平面的交集，为凸集。 {x ∣ a_j^Tx ≤ b_j, j = 1, …, m, c_j^Tx = d_j, j = 1, …, p} 当然多个条件也可以一起排列写成矩阵的形式，简单来说只有若干个线性不等式和等式的约束代表的凸集即是多面体，注意多面体不一定封闭。

单纯形

在ℝⁿ空间中选择k + 1个仿射无关的点v₀, v₁, …, v_k,（也就是满足v₁ − v₀, v₂ − v₀, …, v_k − v₀线性无关），我们称点v₁, …v_k的凸包为单纯形 C = conv{v₁, …, v_k} = {θ^Tv|θ ≥ 0, ∑_iθ_i = 1} 例如，在ℝⁿ 空间中，由两个点构造的凸包(线段)与三个点组成凸包(三角形)算是单纯形。但是四个点组成的凸包不是单纯形，因为在二维空间ℝⁿ 中，四个点无法仿射独立。如下图

求证：单纯形是多面体的一种

定义

y = [θ₁, …, θ_k], y ≥ 0, 1^Ty ≤ 1(因为y中舍弃了θ₀)

B = [v₁ − v₀, …, v_k − v₀] ∈ R^n × k

则单纯形中的点x = θ₀v₀ + ⋯ + θ_kv_k可以写为 x = θ₀v₀ + ⋯ + θ_kv_k = v₀ + θ₁(v₁ − v₀) + ⋯ + θ_k(v_k − v₀) = v₀ + By  (1) 由于B是列满秩的，也即rank(B) = k,也就是说我们总能通过初等行变换把B变为$B=\left[\begin{array}{c}{ {I_{k} } }\\{0}\end{array}\right]$
用数学的语言描述，我们总能找到可逆矩阵A，使得 $$A=\left[\begin{array}{c}{A_{1} }\\{}\\{A_{2} }\end{array}\right]\in R^{n\times n}, \left[\begin{array}{c}{A_{1} }\\{}\\{A_{2} }\end{array}\right]B=\left[\begin{array}{c}{I_{k} }\\{0}\end{array}\right]$$ 1式两边左乘A $$\left.Ax=Av_0+ABy\Rightarrow\left[\begin{array}{c}A_1\\\\A_2\end{array}\right.\right]x=\left[\begin{array}{c}A_1\\\\A_2\end{array}\right]v_0+\left[\begin{array}{c}I_k\\\\0\end{array}\right]y$$ 利用y ≥ 0, 1^Ty ≤ 1,有A₁x ≥ A₁v₀, 1^TA₁x ≤ 1^TAv₀ + 1
则单纯形中的 x 可以表示为{x ∣ A₁x ≥ A₁v₀, 1^TA₁x ≤ 1^TAv₀ + 1, A₂x = A₂v₀}

一些矩阵

• 对称矩阵集合：Sⁿ = {x ∈ R^n × n ∣ X = X^T}
• 半正定矩阵集合：S₊ⁿ = {x ∈ R^n × n ∣ X = X^T, X ≽ 0}
• 正定矩阵集合:S₊₊ⁿ = {x ∈ R^n × n ∣ X = X^T, X ≻ 0}

保凸运算举例

任意多个凸集的交集

若S₀为凸集，∀a ∈ A,则⋂_a ∈ AS_a为凸集

仿射函数

当f = Ax + b, A ∈ R^m × n, b ∈ R^m 若S ∈ Rⁿ为凸，则f(S) = {f(x) ∣ x ∈ S}为凸，我们称f : Rⁿ → R^m 是仿射的 (线性映射)

缩放和移位

αS = {αx ∣ x ∈ S}  S + a = {x + a ∣ x ∈ S}

透视函数

透视函数(perspective function):P : R^n + 1 → Rⁿ, domP : Rⁿ × R₊₊ $P( z, t) = \frac zt$, z ∈ Rⁿ, t ∈ R₊₊,凸集通过透视变换仍为凸集。

形象的理解P：一个n+1维向量保留前n维，同时除以被扔掉的n+1维得到新的向量

证明任意线段经过透视还是线段:

x = (x̃, x_n + 1), y = (ỹ, y_n + 1), x̃, ỹ ∈ Rⁿ, x_n + 1, y_n + 1 ∈ R₊₊, θ ≥ 0 $$\begin{aligned} \begin{aligned}P(\theta x+(1-\theta)y)\end{aligned}& \begin{aligned}=\frac{\theta\tilde{x}+(1-\theta)\tilde{y}}{\theta x_{n+1}+(1-\theta)y_{n+1}}\end{aligned} \\ &\begin{aligned}&=\frac{\theta x_{n+1}}{\theta x_{n+1}+(1-\theta)y_{n+1}}\frac{\tilde{x}}{x_{n+1}}+\frac{(1-\theta)y_{n+1}}{\theta x_{n+1}+(1-\theta)y_{n+1}}\frac{\tilde{y}}{y_{n+1}}\end{aligned} \\ &=\mu P(x)+(1-\mu)P(y) \end{aligned}$$

线性分数函数

A ∈ R^m × n, b ∈ R^m, C ∈ Rⁿ, d ∈ R，线性分数函数定义为 $$\begin{aligned}f(x)=\frac{Ax+b}{cx+d}, domf=\{x\mid c^Tx+d>0\}\end{aligned}$$ 这可以看成是对x进行两次集合运算得到的结果，先进行仿射变换 $$\delta(x)=\left[\begin{array}{c}{A}\\{c^{T}}\\\end{array}\right]x+\left[\begin{array}{c}{b}\\{d}\\\end{array}\right]$$ 再进行透视变换P : R^m + 1 → R^m，因此两次保凸运算得到的结果依然是凸集

参考文献/blog

• https://www.bilibili.com/video/BV19M411T7S7?p=20&vd_source=84b977d2834d5eca6c0ca78bd619156f，中科大/凌青《凸优化》，chapter1-9
• 知乎专栏，https://www.zhihu.com/column/c_1492543238217478144
• 知乎专栏，https://zhuanlan.zhihu.com/c_1280779583399882752
• 《ConvexOptimizationnotes》，https://github.com/ZxyGed/ConvexOptimization，Convex_Sets pdf笔记