Convex Set

凸集，是一个在基础数学课程中接触过的概念。凸的背后，往往蕴含着非常好的性质，这也就是我们要去研究凸集的原因。

仿射（Affine）

一个集合 $C$ 是仿射集，如果对任意 $x_1, x_2 \in C$ 和 $\theta \in \mathrm{R}$ 都有： $\theta x_1 + (1-\theta)x_2 \in C$ 需要注意的是这里的 $\theta$ 取值是全体实数（而不是介于0到1之间）。

仿射集可以写成一个线性子空间的仿射，即存在子空间 $V$ 使得： $C=V+x_{0}=\left\{v+x_{0} \mid v \in V\right\}$ 类比非齐次线性方程组的解是一个仿射子集而对应的齐次线性方程组的解是一个线性子空间。

对任意一个集合 $C$ ，我们可以定义它的 affine hull： $\text { aff } C=\left\{\theta_{1} x_{1}+\cdots+\theta_{k} x_{k} \mid x_{1}, \ldots, x_{k} \in C, \theta_{1}+\cdots+\theta_{k}=1\right\}$ 仿射包是包含这个集合的最小仿射集。

相对内点：

relative interior

相对内点与内点是有所不同的，比如考虑一个三维空间中的正方形。这个正方形内部的点，不是内点，但是是相对内点。再考虑三维空间中的一个球面，它的相对内点集是空集。

通过相对内点还可以引出相对边界这一概念。

凸集

一个集合 $C$ 是凸集，如果对任意 $x_1, x_2 \in C$ 和 $\theta \in [0, 1]$ 都有： $\theta x_1 + (1-\theta)x_2 \in C$ 仿射集自然是凸集的一种，类比于仿射集的相关概念，我们可以得到凸包（convex hull）的定义。集合 $\mathrm{C}$ 的凸包是包含集合 $\mathrm{C}$ 的最小凸集。

cones 锥

在优化理论中，锥是一个无限大的集合，与日常所接触的圆锥有所不同。一个集合 $C$ 是锥，如果对任意 $x \in C$ 和 $\theta \geq 0$ 都有： $\theta x \in C$

如果一个锥是凸的，就称它是一个凸锥。比如 $y=|x|$ 的图像就是一个锥，但不是凸锥。但是 $y\ge |x|$ 就是一个凸的锥了。

仔细思考上述概念，任意一个锥 $K$ 是不是都有一个极限点是 $0$ 。如果它是闭的（closed），那么 $0 \in K$ ！

类似的可以得到锥包（conic hull），它是包含某个集合的最小的锥。 $\{\theta_1 x_1 + \cdots +\theta_k x_k \mid x_i \in C, \theta_i \geq 0, i=1, ..., k\}$

重要的例子

下面列举一些重要的凸集的例子

一个点
注意这个是凸集哦~~~
超平面和半平面
球、椭球

正规锥（norm cones）
$C=\{(x, t) |\|x\| \leq t\} \subseteq \mathbf{R}^{n+1}$ 也被叫做二阶锥（second order cones）。
凸多面体

$\mathcal{P}=\left\{x | a_{j}^{T} x \leq b_{j}, j=1, \ldots, m, c_{j}^{T} x=d_{j}, j=1, \ldots, p\right\}$

单纯形 simplex

不同的两个点、不共线的三个点、不共面的四个点，它们生成的凸包，分别构成了一维、二维、三维的单纯形。
特别地，unit simplex：
$x \succeq 0, \quad \mathbf{1}^{T} x \leq 1$ 离散型随机变量的概率分布就是一个典型的 unit simplex。

半定矩阵锥
我们用记号 $\mathrm{S}^n$ 来表示所有的 $n$ 阶实对称矩阵组成的集合， $\mathrm{S}^n_+$ 表示所有的半正定矩阵， $\mathrm{S}^n_{++}$ 表示所有的正定矩阵。其中， $\mathrm{S}_{+}^n$ 是一个闭的 convex cone。所有的 $n$ 阶方阵是一个线性空间， $\mathrm{S}^n_{+}$ 是这个线性空间的一个锥。
半定矩阵锥，让我们对凸集的认识，从欧式空间，飞跃到了抽象的线性空间！这让我们得以在矩阵空间上考虑优化问题。

保持凸性的操作

集合的交、和、差
例：

无穷多个凸集的交，仍然是凸集。

由于我们讨论凸集都是在 $\mathrm{R}^n$ 这个向量空间上讨论，因此所谓的“和”与“差”，都是 elementwise 的。

仿射变换（affine transformation）

比如椭球就可以看作是球的仿射。
例子：

线性分数变换（Linear fractional transformation）
可以看作是仿射变换的推广，涉及到复变函数的知识。

在最简单的情况下， $f(x)=\frac{ax+b}{cx+d}$ （是不是想到了些什么？）
特殊的情况下，是透视函数

一个凸集在透视函数的映射下仍然是凸的。透视函数的作用可以理解为是“针孔摄像头”！（参见：透视函数）

直线上方是一个凸集，下方是透视函数的映射值域

总之，凸集，在线性分数变换下的像/原像，都是凸的。

广义不等式（generalized inequalities）

proper cones

乍一看这个概念很突兀。proper cone 最重要的作用是能定义一个集合上的偏序关系（partial ordering）：

$x \preceq_{K} y \Longleftrightarrow y-x \in K\;\; , \;x \prec_{K} y \Longleftrightarrow y-x \in \mathbf{int}K$

如果取 $K=R_+$ ，那么得到的序关系就是正常的实数比较。
如果取 $K=R^{n}_+$ ，那么向量 $\vec{x}\preceq\vec{y}$ 当且仅当每个分量 $x_i \leq y_i$ 。

$\mathrm{S^{n}_+}$ 是 $\mathrm{S^n}$ 中的一个 $\mathrm{proper\; cone}$ ， $X\preceq_{K} Y$ ，当且仅当 $Y-X$ 是半正定的， $X\prec_{K} Y$ ，意味着 $Y-X$ 是正定的，所以很多时候我们直接简写 $X\succ 0$ 来声明 $X$ 是正定矩阵。

这样的偏序关系有非常良好的性质：

最大和最小元素

有了序关系，自然就会考虑这样一个偏序集的最大/最小的元素（maximum/minimum）。

显然，如果这样的元素存在，那么必然是唯一的。但实际上，并不是所有的元素都是可比较的（comparable），我们可以藉此定义“极小元”、“极大元”（minimal, maximal），意为，没有元素比它们来的更大/更小，容易知道它们不是唯一的。

用 $x-K$ 表示，所有的可以与 $x$ 比较的、并且小于等于 $x$ 的元素全体，此时 $x$ 是 $S$ 中的极小元，当且仅当：
$(x-K) \cap S=\{x\}$

类似地，用 $x+K$ 表示所有与 $x$ 可以比较的、并且大于等于 $x$ 的元素全体。

$K=R^2_+$ 的情况如下图，左图的 $x_1$ 是最小点，而右图的 $x_2$ 是极小点

分割和支撑超平面定理

考虑两个不相交的凸集，是不是能找到一个超平面把它们分割开？？如果其中一个变成凹集，是不是就做不到了？？

对于 $n$ 维空间中的一个超平面，我们习惯用 $\left\{x | a^{T} x=b\right\}$ 来表示。一个超平面将全空间分割成两个半空间。

超平面分割定理，说的就是两个不相交的凸集，一定存在 $a \neq 0$ 的超平面使得在其中一个凸集满足 $a^T x\ge b$ ，而另一个凸集中成立 $a^T x \leq b$ 。这个超平面 $\left\{x | a^{T} x=b\right\}$ 就叫做这两个凸集的分割超平面。

进一步，如果不等关系严格成立，就说这两个凸集被严格分割（strict separation）。

定义两个凸集的欧几里得距离是这两个集合中两个点距离的下确界： $\operatorname{dist}(C, D)=\inf \left\{\|u-v\|_{2} | \;u \in C, v \in D\right\}$

乍一看，好像很多的凸集对都是可以被严格分割的。注意凸集不一定要是闭的。

两个开的不相交的凸集很容易找到例子说明它们可能不能被严格分割。当两个不相交的凸集都是闭的，比如 $A=\{(x, y) | x y \geq 1, x, y>0\}$ 和 $B=\{(x, y) | x \leq 0\}$ ，也可能不能被严格分割。

其实不然，严格分割只在某些特定的情况下。比如一个闭凸集和这个凸集外的一点，这两个凸集是可以被严格分割的。如果这个凸集是开的，并且这个点选为凸集的边界点，那么就不能被严格分割。

点与凸集的分离定理，说的正是闭凸集和集合外一点可以被严格分割；利用它，我们进一步才得到下面的支持超平面定理。

通过上一段的那个结论，我们可以得到，任意一个闭凸集是所有包含这个凸集的半空间的交。

利用凸集分离定理，可以得到一个有趣的结论：

支撑超平面

对凸集 $C$ ，如果有 $x_{0} \in \mathbf{b d} C=\mathbf{cl} C \backslash \mathbf{ int } C$ ，并且 $a^{T} x \leq a^{T} x_{0}\;\;\; \text { for all } x \in C$

那么超平面 $\left\{x | a^{T} x=a^{T} x_{0}\right\}$ 就叫做 $C$ 在 $x_0$ 这点的支撑超平面。凸集的任何个边界点都存在支撑超平面，这就是支撑超平面定理。

support hyperplane

值得一提的是，支撑超平面定理的逆定理也成立。即如果一个内点集非空的闭集，在每一个边界点上都有一个支撑超平面，那么它是凸的。

对偶锥（dual cones）

设 $K$ 是个锥，定义 $K$ 的对偶锥为： $K^{*}=\left\{y | x^{T} y \geq 0 \text { for all } x \in K\right\}$ 。顾名思义， $K^{*}$ 是一个锥，更有意思的是 $K^*$ 总是凸的，不论 $K$ 是不是凸的。

例：

线性空间的子空间 $V$ 的对偶锥是其正交补 $V^\perp$ 。

从几何上看， $K^*$ 中任意一点与 $K$ 中所有点的夹角不超过90°。

非负象限和半正定锥的对偶锥是其本身，称其为自对偶锥（self-dual）。

The dual of the $p$ norm, denoted by $\|\cdot\|^{*},$ is the $q$ norm, where $\frac{1}{p}+\frac{1}{q}=1$

对偶锥有以下性质：

pointed: if $x\in K, -x \in K$ ，then $x=0$

这些性质说明如果 $K$ 是一个 proper cone，那么 $K^*$ 也是一个 proper cone，并且 $K=K^{**}$ 。

对偶广义不等式

之前我们已经知道 proper cone $K$ 能诱导出一个偏序关系。现在 $K^*$ 也是一个 proper cone，是不是通过 $K^*$ 也能定义一个偏序关系了。

此外，通过对偶性可以给出广义不等式的等价命题：

$x \preceq_{K} y \Leftrightarrow \lambda^{T} x \leq \lambda^{T} y ,\; \; \forall \lambda \succeq_{K^{*}} 0$
$x \prec_{K} y \Leftrightarrow \lambda^{T} x<\lambda^{T} y,\;\; \forall \lambda \succeq_{K^{*}} 0, \lambda \neq 0 .$

通过定义很容易验证上图的结论。

上式的含义是，对偶锥中的每个元素（向量）可以看成原来锥的一个合法的投影方向，原来锥上两个点在这些合法的投影方向上序不变！ 在锥形式的对偶中就要用到这条性质。

we have $\lambda \preceq_{K^*} \mu$ if and only if $\lambda^{T} x \leq \mu^{T} x$ for all $x \succeq_K 0$

联系超平面分割定理，我们还能得到下面这个非常重要的结论：

Theorem of alternatives for linear strict generalized inequalities
$A x \prec_{K} b$ is infeasible if and ony if $\lambda \neq 0, \quad \lambda \succeq_{K^*} 0, \quad A^{T} \lambda=0, \quad \lambda^{T} b \leq 0$