一、 仿射集合和凸集

1. 基本定义

1. 直线与线段

1. 直线： 一条穿过$x_1$和$x_2$的直线可表示为：

2. 线段： 当$\theta$在$0$和$1$之间变动时，便构成了$x_1$和$x_2$之间的闭线段。

2. 仿射集合

1. 仿射：

   如果通过集合$C \subseteq \R^n$中任意两个不同点的直线仍然在集合$C$中，那么称集合$C$是仿射的。

一条直线、过一个定点的直线束、一个平面都是仿射的。

2. 仿射组合：

   将仿射概念拓宽至多个点，若$\theta_1 +\theta_2 + \dots + \theta_k = 1$，那么具有$\theta_1 x_1 +\theta_2 x_2 + \theta_k x_k$形式的点为$x_1, \dots x_k$的仿射组合。

3. 仿射集合：

   一个仿射集合包含其中任意点的仿射组合。

4. 子空间：

   如果$C$是一个仿射集并且$x_0 \in C$，则我们称以下集合$V$为一个子空间。

$V$是满足加法和数乘的，并且由于$C - x_0$，使得$V$含有了零元素。

由此我们也可将仿射集合$C$定义为一个子空间加上一个偏移：

5. 仿射包：

   我们称由集合$C \subseteq \R^n$中的点的所有仿射集合组成的集合为$C$的仿射包，记为$\mathbf{aff}C$

3. 凸集

1. 凸集：

   如果$C$中任意两点间的线段仍然在$C$中，即：

2. 凸组合：

   我们称点$\theta_1 x_1 + \cdots + \theta_k x_k$为点$x_1, \cdots, x_k$的一个凸组合，其中$\theta_1 +\cdots + \theta_k = 1$并且$\theta_i \geq 0, i = 1, \cdots, k$。

   点的凸组合可以看做它们的混合或加权平均

3. 凸包：

   我们称集合$C$中所有点的凸组合的集合为其凸包，记为$\mathbf{conv}C$:

   $$\mathbf{conv}C = \{\theta_1 x_1 + \cdots + \theta_k x_k| x_i \in C, \theta_1 + \cdots + \theta_k = 1, \theta_i \geq 0, i = 1,\cdots, k\}$$

4. 锥

1. 锥：

   如果对于任意$x \in C$和$\theta \geq 0$都有$\theta x \in C$，我们称集合$C$是锥或者非负其次

2. 凸锥：如果集合$C$是锥，并且是凸的，则称$C$为凸锥

3. 锥组合（非负线性组合）：具有$\theta_1x_1+\cdots+\theta_kx_k, \theta_1,\cdots,\theta_k\geq0$形式的点称为$x_1,\cdots,x_k$的锥组合。
4. 锥包：是$C$中元素的所有锥组合的结合。

二、重要的例子

1. 超平面与半空间

1. 超平面：

   与给定向量$a$的内积为常数的点的集合，或法线方向为$a$的超平面，常数$b \in \R$决定了这个平面从原点的偏移。

   $$\{x | a^Tx =b\}$$

2. 半空间：

   $\R^n$被超平面划分为两个半空间。闭的半空间是具有下列形式的集合：

   $$\{x|a^Tx \leq b\}$$

   半空间是凸的，但不是仿射的。

   其中集合$\{x|a^Tx < b\}$是半空间$\{x|a^Tx\leq b\}$的内部，称为开半空间

2. Euclid球和椭球

1. Euclid球：具有以下形式：

   $$B(x_c, r) = \{x | \Vert x - x_c \Vert_2 \leq r\}$$

   其中 $r > 0, \Vert \cdot \Vert_2$表示 Euclid 范数，即$\Vert u \Vert_2 = (u^Tu)^{\frac{1}{2}}$。向量$x_c$为球心，标量 r 为半径。

2. 椭球：具有以下形式：

   $$\varepsilon = \{x | (x-x_c)^T P^{-1}(x-x_c)\leq 1\}$$

   其中$P$是对称正定矩阵。$\varepsilon$的半轴长度由$\sqrt{\lambda_i}$给出，这里的$\lambda_i$为$P$的特征值。球可以看成$P = r^2I$的椭球。

3. 范数球和范数锥

1. 范数球：$\{x| \Vert x - x_c \Vert \leq r\}$是凸的。
2. 范数锥：$C=\{(x, t) | \Vert x \Vert \leq t\} \subseteq \R^{n+1}$

4. 多面体

多面体被定义为有限个线性等式和不等式的解集。

多面体是有限个半空间和超平面的交集。

可以使用紧凑表达式来表示：

其中$\preceq$ 表示$R^m$上的向量不等式或分量不等式：$u \preceq v$表示$u_i \leq v_i$

5. 半正定锥

我们用$S^n$表示对称$n \times n$矩阵的集合，即

这是一个维数为$\frac{n(n+1)}{2}$的向量空间。我们用$S^n_+$表示对称半正定矩阵的集合，$S_{++}^n$表示对称正定矩阵的集合：

三、做题细节

1. 证明线性空间

需要证明以下性质：

1. 加法封闭性：$\forall x, y \in V \Rightarrow x + y \in V$
2. 标量乘法：$\forall x \in V, \forall \alpha \in F \Rightarrow \alpha x \in V$
3. 加法交换律：$x + y = y + x$
4. 加法结合律：$(x + y) + z = x + (y + z)$
5. 零元存在：$x + 0 = x$
6. 加法逆元存在：$\forall x \in V, \exists -x \in V \Rightarrow x + -x = 0$
7. 数乘单位元：$1x = x$
8. 分配率：$\alpha (x, y) = \alpha x +\alpha y$
9. 分配率：$(\alpha + \beta) x = \alpha x + \beta x$
10. 数乘结合律：$\alpha(\beta x) = (\alpha \beta)x$

其中1、2可以合成一条证明$\forall x, y \in V, \forall \alpha, \beta \in F \Rightarrow \alpha x + \beta y \in V$

2. 证明线性子空间

只需要证明加法和乘法的封闭性即可。

即$\forall x, y \in V, \forall \alpha, \beta \in F \Rightarrow \alpha x + \beta y \in V$