凸优化

凸集

对于点集\(C\)，如果\(\forall x,y \in C\)满足以\(x,y\)为端点的线段都落在\(C\)内，就称\(C\)为凸集。以\(x,y\)为端点的线段写成方程的形式是\(u=x+\theta(y-x)\)，\(\theta \in [0,1]\)。因此“线段落在\(C\)内”这一条件可以写作“\(\theta x+(1-\theta)y \in C\)，\(\theta \in (0,1)\)”。通常把\(1-\theta\)记作\(\bar{\theta}\)，把\(\theta x+\bar{\theta}y\)称为\(x,y\)的凸组合。于是验证凸集只要验证两两点的凸组合都落在凸集内。

一般地，\(n\)个点的凸组合定义为\(\theta_1x_1+\cdots+\theta_nx_n\)，其中\(\theta_i \geq 0\)，\(\sum\limits_{i=1}^{n}\theta_i=1\)。如果\(x_1,\cdots,x_n\)都在凸集\(C\)内，那么它们的凸组合也在\(C\)内（对\(n\)归纳，证明很容易）。

常见的凸集有：空集，\(\R^n\)，超平面， 多面体，1-范数球，半正定矩阵集合等。证明它们是凸集只需验证它们两两的凸组合落在集合内。

保凸运算

凸集的交集依然是凸集：\(C=\bigcap\limits_{i \in I}C_i\)，因为显然交集内任意两点的凸组合依然在凸集中，可见“交”是保凸运算。

对于向量\(x\)，\(x \to Ax\)的变换称为线性变换，\(x \to Ax+b\)的变换称为仿射变换。仿射变换是保凸运算。设仿射映射\(Ax+b\)为\(f(x)\)，凸集\(C\)的像\(f(C)\)依然是凸集。反过来，如果某个仿射变换的像是凸集，其原像也是凸集：\(C'\)是凸集\(\Rightarrow f^{-1}(C')\)是凸集。

凸包

对于点集\(S\)，定义\(S\)的凸包\(\text{conv}(S)\)为包含\(S\)的最小凸集（最小指任何\(\text{conv}(S)\)的真子集都不是包含\(S\)的凸集，或任何包含\(S\)的凸集都包含\(\text{conv}(S)\)）。下面证明，\(\text{conv}(S)\)恰好是\(S\)中所有任取\(m\)个点做凸组合得到的所有点集合，即\(\text{conv}(S)=\{\sum\limits_{i=1}^{m}\theta_ix_i \mid x_i \in S, \theta_i \geq 0,\sum\limits_{i=1}^{m}\theta_i=1\}\)。“包含\(S\)”与“凸集”是显然的，而任何一个满足“包含\(S\)的凸集”的集合\(C\)一定包含上式的右式，因此\(S\)就是最小的。

我们定义过线性独立是指若干向量的线性组合为0向量时所有的系数都为0。下面定义仿射独立的概念，\(n+1\)个点仿射独立当且仅当从中选取一个点并让剩余点与它做差后的\(n\)个向量线性独立。对于给定的\(m+1\)个仿射独立的点\(x_0,\cdots,x_m\)，称它们构成的凸包\(\text{conv}\{x_0,\cdots,x_m\}\)为这\(m+1\)个点的单纯形。