凸集合与凸函数

1. convex sets

1.1 Line segmentation 直线分割

$y=\theta x_1+(1-\theta)x_2$ $y=x_2+\theta(x_1-x_2)$

$\theta$=1时$y=x_1$,=0时反之，所以称为直线分割

根据式2也可以看做是以x_2为基准。向x_1-x_2延伸的一条线

1.2 affine sets

仿射集C上的任意两点连成的直线属于C
即

${\theta x_{1}+(1-\theta) x_{2} \in C, \quad \forall x_{1}, x_{2} \in C, \text { and } \theta \in \mathbb{R}}$

扩展到多点上为

$x_1, x_2 ... x_k \in C$ $\bf{AND} {\theta}_1+{\theta}_2+...+{\theta}_k=1$ $\bf{THEN} \theta x_{1}+...+\theta_k x_{k} \in C$

其中，对于属于C的子空间是
$V=C-x_0=\{x-x_0|x\in C\}$

意味着标量乘积之和是闭合的

子空间维数=仿射集维数

1.3 affine hull 仿射包

aff$C=\{\theta x_{1}+…+\theta_k x_{k}|x_{1}, x_{2}…x_k\in C, \theta_1+\theta_2+…+\theta_k=1\}$

C中的所有点的仿射组合组成的集合
仿射集维数=仿射集子空间的维数
是包含C的最小仿射集合

1.4 相对内部 relative interior

如果集合C的仿射维数小于n,那么aff$C\ne R ^n$
相对内部relint C定义为
$\text { relint } C =\{x \in C \mid B(x, r) \cap \operatorname{aff} C \subseteq C \text { for some } r>0\}$
其中$B(x,y)=\{y| |y-x|\le r\}$(任意范数均可)

（呃呃呃开始不说人话了是吧）

1.5 convex sets 凸集

任意两点的线段都在C中
$\theta x_{1}+(1-\theta) x_{2} \in C$

所有点的凸组合为凸包（convex hull）
conv$C=\{\theta x_{1}+…+\theta_k x_{k}|x_{1}, x_{2}…x_k\in C, \theta_1+\theta_2+…+\theta_k=1, \theta_i\ge 0\}$
凸包是包含C的最小凸集

2. cone 锥

对与任何x属于C以及$\theta$大于等于0，都有
$\theta x\in C$

2.1 凸锥

锥且凸，即
$\theta_1 x_1 + \theta_2 x_2\in C$

2.2 锥包

所有锥组合形成的集合

3. 重要例子

3.1 一些概念

空集、任意一个点（即单点集）、全空间R”都是Rn的仿射（自然也是凸的)子集。
任意直线是仿射的。如果直线通过零点，则是子空间，因此，也是凸锥。
一条线段是凸的，但不是仿射的（除非退化为一个点）。
一条射线，即具有形式$\{x_0+\theta v|\theta≥0\}$，v≠0的集合，是凸的，但不是仿射的。如果射线的基点$x_0$是0，则它是凸锥。
任意子空间是仿射的、凸锥（自然是凸的）。

3.2 超平面

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

$a\in R^n且不为0, b\in R$
超平面是关于x的线性方程的解空间（因此是仿射集合）

3.3 半空间

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

线性不等式的解空间
凸但不仿射
由超平面切割而成2个半空间

3.4 Euclid球

$\begin{aligned}
B\left(x_{c}, r\right) &=\left\{x \mid\left|x-x_{c}\right|_{2} \leq r\right\} \\
&=\left\{x \mid\left(x-x_{c}\right)^{\top}\left(x-x_{c}\right) \leq r^{2}\right\}
\end{aligned}$

$x_c$为球心
r是半径

3.5 多面体

$\begin{array}{r}
\mathcal{P}=\left\{x \mid a_{j}^{\top} x-b_{j} \leq 0, j=1, \ldots, m\right. \\
\left.c_{j}^{\top} x-d_{j}=0, j=1, \ldots, p\right\}
\end{array}$