数学优化与凸集2（斯坦福凸优化笔记2）
本文介绍了仿射集合与凸集的基本概念及其性质。仿射集合是指通过集合中任意两点连线上的所有点仍属于该集合的集合；而凸集则是指任意两点连线上的所有点都包含在该集合中的集合。文中还详细讨论了锥的概念（即从原点出发到各个点的辐射直线组成的集合），并进一步探讨了由这些几何对象构成的凸锥及其应用。此外，文章列举了一些常见的凸集类型：超平面与半空间（均为凸且仿射）、欧几里得球和椭球（均为凸）、范数球与范数锥（分别用于度量空间中的距离约束和对偶性）、多面体（作为有限个线性不等式与等式的交集）以及半正定锥（涉及对称矩阵的正定性）。这些几何对象在优化理论中具有重要作用，并广泛应用于工程学、经济学等领域中。
1 仿射和凸集
1 直线和线段
给定两个不同的点x_1, x_2 \in R^n（其中x_1 ≠ x_2），这些点可表示为以下形式：
y = θx₁ + (1 - θ)x₂,\quad θ ∈ R
这条直线穿过这两个关键点。当参数θ取值于区间[0, 1]时，则该集合构成连接这两点的一条有限线段。
2 仿射集合
当且仅当集合C \subseteq R^n中任意两个不同点所连成的直线完全包含于该集合内时，则称该集合为仿射集。
这一概念可推广至多个点的情况：若系数\theta_1, \ldots, \theta_k满足\sum_{i=1}^k\theta_i = 1（其中k \geq 2），则形如\sum_{i=1}^k\theta_ix_i的所有点都被定义为x_1, \ldots, x_k的仿射组合。
基于仿射集的定义可知：若x_1, \ldots, x_k \in C（其中k \geq 2），且其对应的系数满足上述条件，则该组合仍属于该集合。
称该集合为凸集的前提条件是其任取两点连线必完全包含于该集合内。也就是说，在满足以下条件下：
对于属于C中的任意两点x₁,x₂以及介于0到1之间的参数θ，
都有θx₁ + (1-θ)x₂也属于C。
直观而言，
该集合包含了连接任何两个点之间路径的所有点。
而由C中所有点构成的所有可能的凸组合所形成的集合则被称为其凸包，
用符号表示即：
conv C = {θ₁x₁ + ... + θk xk | xi ∈ C, θi ≥ 0, i=1,...,k, θ₁+...+θk=1}
经过计算可知，
这个由C生成的所有点构成的最小闭合凸集就是它的conv C。
即为所求。
此页面上方展示的是一个凸包的图像（该图像源自斯坦福大学 Boyd 的《Convex Optimization》课程材料）。左侧区域呈现的是多个点构成的凸包形态,右侧区域则是呈现出肾形特征的凸包. 4锥.
对于所有x\in C以及\theta\geq 0都满足\theta x\in C，我们定义该集合为锥集或非负齐次集。
同时，
cone can be intuitively understood as the set formed by all rays emanating from the origin to each point in the set.
在图中所示的三条直线可以被视为一个锥。对于该直线上任意取定的三个点x_1, x_2, x_3而言，这些点满足上述锥的基本性质。若集合既是锥又是凸集，则对于该集合中任意两个元素x₁和x₂以及非负标量θ₁和θ₂而言，
θ₁x₁ + θ₂x₂ ∈ C
成立。这样的集合同时具备锥性和凸性，在二维空间中，则对应于一个扇形区域。
（图片来自斯坦福Boyd Convex Optimization）
该集合包含了来自C的所有元素的锥组合。即
\{\theta_1x_1+\cdots+\theta_kx_k\mid x_i \in C, \theta_i \geq 0,i=1,\cdots,k\},
它是包含在所有凸锥中的最小者。
（图片来自斯坦福Boyd Convex Optimization）
2 一些常见的凸集
下面介绍一些常用的凸集，这些凸集将在以后经常用到。
超平面及其相关的半空间区域
超平面是一种具有特定数学表达式的几何体：
\{x\mid a^Tx=b\}
其中向量a属于n维实数空间，并且非零；常数b属于实数域。
其法向量方向由a确定，而常数b则决定了该超平面相对于坐标原点的位置。
这种几何体将整个欧几里得空间划分为两个互不重叠的半空间区域：
\{x\mid a^Tx\leq b\}
而超平面本身既是一个凸集又是仿射子空间。
（图片来自斯坦福Boyd Convex Optimization）
半空间是凸的。
（图片来自斯坦福Boyd Convex Optimization）
2 Euclid 球和椭球
空间中的Euclidean 球（简称球）具体表现为以下两种形式：
B(x_c,r)=\{x \mid ||x - x_c||_2 \leq r\} = \{x | (x - x_c)^T(x - x_c) \leq r^2\}
同样也可以用另一种方式表示为：
B(x_c,r) = \{x_c + ru | ||u||_2 \leq 1\}
另一类重要的凸集是椭球体：
\varepsilon = \{(x - x_c)^T P^{-1}(x - x_c) \leq 1\}
其中\varepsilon代表该椭球体。
此外，椭球还可以采用另一种标准表示方法：
\varepsilon = \{x_c + Au | ||u||_2 \leq 1\}
这里矩阵A是非奇异且对称正定的方阵，在这种情况下（即当A=P^{-1}时），这两种表示方法实际上是等价的）。
3 范数球和范数锥
该种几何体可通过以下方式定义：设\left \|\cdot\right\|代表R^n空间中的一个范数，则对应的范数所限定的空间即被称为范数单位超球面（或简称为单位超椭圆面），其具体形式为集合\{x \mid ||x−xc|| ≤ r\}中的所有点构成的空间区域。
与传统的欧几里得空间中的单位超球不同的是，
这种由特定数学表达式所限定的空间区域同样具有凸性特征。
范数锥的定义如下：
C=\{(x,t)\mid\left\|x\right\|\leq t\} \subseteq R^{n+1}
范数锥是个凸锥。
这个图是二维\{\left\|x\right\|_{max}\leq t\}的图片。
这个图是二维\{\left\|x\right\|_{1}\leq t\}的图片。
4 多面体
多面体定义为有限个线性等式和不等式的解集：
P=\{x \mid x满足线性不等式a_j^Tx \leq b_j（j=1,\cdots,m）与线性等式c_j^Tx=d_j（j=1,\cdots,p）\}
多面体是由有限个半空间与超平面共同构成的集合。该集合为凸集。
多面体还可以表示为：
P=\{x\mid Ax \preceq b, Cx=d\}
其中：
5 半正定锥
我们以符号S^n标记所有n\times n对称矩阵的集合，并将其向量空间维度确定为n(n+1)/2。进一步地，在这一空间中，我们引入子集\mathcal{S}^n_+来表示所有n×n 对称半正定矩阵。具体而言，
\mathcal{S}^n_+=\left\{X \in \mathcal{S}^n \mid X \succeq 0\right\}
其中\mathcal{S}^n_{++}则代表所有n×n 对称正定矩阵构成的子集：
\mathcal{S}^n_{++}=\left\{X \in \mathcal{S}^n \mid X \succ 0\right\}
值得注意的是这些集合均属于凸锥家族。（未完，待续）