支撑超平面理论(Supporting hyperplane theorem):凸集边界上的一点必然存在一个支撑超平面穿过该点，即如果$C$都是非空凸集，$ x_0 \in $ bd$(C) $，那么必然存在一个超平面$a$，使得, $C \subseteq \left \{x:a^Tx \leq a^T x_0 \right \}$。如下图：
1.5 保凸操作
集合交（Intersection）：任何凸集之交产生的集合依旧是凸集。
缩放和平移（Scaling and translation）：假设$C$为凸集，那么$aC+b=\left \{ax+b:x \in C \right \}$对于任意$a,b$也是凸的。
仿射映射与预映射(Affine images and preimages)：如果$f(x)=Ax+b$是凸集，那么$f(C)=\left \{f(c):x \in C \right\}$也是凸集，如果$D$为凸集，那么$f^(-1)(D)=\left \{x:f(x) \in D \right \}$也是凸的。
1.6 凸集与保凸操作相关例子
条件概率集合(conditional probability set)：$U,V$分别为$\left \{1,...,n\right \}$与$\left \{1,...,m\right \}$上的两个随机变量集合。$ C \subseteq \mathbb{R}^{nm} $为$U,V$的联合分布集合。对于每个$p \in C$，定义联合概率分布 $p_{ij} = \mathbb{P}(U=i,V=j)$。D为对应的条件概率分布，对于每个$q \in D$定义 $q_{ij}=\mathbb{P}(U=i|V=j)$。假定$C$为凸集，那么D一定为凸集。简单证明可用保凸操作中的Affine images and preimages，$D=\{q\in\mathbb{R}^{nm}:q_{ij}={\textstyle\frac{p_{ij}}{\textstyle\overset n{\underset{k=1}{\sum p_{kj}}}}}\}$
2 、凸函数
2.1 基本概念
定义：给定映射$f:\mathbb{R}^n \rightarrow \mathbb{R}$ 并且 dom$(f) \subseteq \mathbb{R}^n$为凸集，那么
$f(tx+(1-t)y) \leq tf(x)+(1-t)f(y)$ 对于任意 $0 \leq t \leq 1$，且 任意$x,y \in dom(f)$。如下图：
从上图可以看出，$f$的函数值总是位于连接$f(x)$和$f(y)$之间的直线下方。
Note:
严格凸(Strictly convex):对于任意$x \neq y$,且$0<t<1$,有$f(tx+(1-t)y)<tf(x)+(1-t)f(y)$。简而言之，就是$f$比线性函数要更弯曲
强凸(Strongly convex):对于参数$m>0$:$f-\frac{m}{2}||x||^2_2$依旧是一个凸函数。简而言之就是$f$要比一般的二次函数要弯曲。
强凸 $\Rightarrow$ 严格凸 $\Rightarrow$ 凸
2.2 凸函数例子
单变量函数：
例如指数函数$e^{ax} $对于任意a都是凸的，幂函数$x^a$在$a\geq 1 或 a \leq 0$的时候为凸，当$0 \leq a \leq 1$的时候非凸，对数函数$log x$是非凸函数
仿射函数(Affine function):
$a^Tx+b$既是凸函数又是非凸函数
二次函数(Quadratic function)：
$\frac{1}{2}x^TQx+b^Tx+c$当$Q \succeq 0$（半正定）的时候为凸
最小平方损失函数（Least squares loss）:
$||y-Ax||_2^2$总是凸的，因为展开后的$A^TA$总是半正定的
范数(Norm)：
$||x||$的任何范数总是凸的，$\ell_p$范数定义为：$\parallel x\parallel_p=(\overset n{\underset{i=1}{\sum x_i^p}})^{1/p}$，对于任意$p\geq1$,$\parallel x\parallel _{\infty} =max|x_i|$。
谱(spectral)范数：$\parallel X \parallel _{op}=\sigma_1(X)$,
核范数（nuclear）:$||X||_{tr}=\sum_{i=1}^{r}\sigma_r(X)$。其中$\sigma_1(X)\geq...\geq\sigma(X)\geq0$为矩阵$X$的从大到小排序的奇异值。
指示函数(Indicator function):
如果$C$为凸，那么其指示函数为：$I_C(x)=\left\{\begin{array}{lc}0&x\in C\\\infty&x\not\in C\end{array}\right.$为凸函数。
最大值函数（Max function）:
$f(x)=max\left\{x_1,...,x_n\right\}$为凸函数
2.3 凸函数的一些特性
上镜特性(Epigraph characterization):函数$f$为凸函数当且仅当其上镜图$epi(f)=\left \{(x,t)\in dom(f)\times \mathbb{R}:f(x)\leq t\right\}$为凸集，如下图：
一阶特性(First-order characterization):假设$f$处处可微，那么$f$为凸函数当且仅当$dom(f)$为凸，并且有：$f(y)\geq f(x)+\nabla f(x)^T(y-x)$对于所有$x,y\in dom(f)$。
Note:如何证明凸函数的一阶特性？
Answer:从凸函数定义出发，$f(ty+(1-t)x) \leq tf(y)+(1-t)f(x) \quad \Rightarrow \quad \\ f(t(y-x)+x)+f(x))\leq t(f(y)-f(x))+f(x) \quad \Rightarrow \quad \\ \frac{f(t(y-x)+x)-f(x)}{t(y-x)}\leq frac{f(y)-f(x)}{y-x} \quad \Rightarrow \quad \\ \lim_{t\rightarrow0} \frac{f(t(y-x)+x)-f(x)}{t(y-x)}=\nabla f(x) \quad \Rightarrow \quad \\ \nabla f(x)(y-x) \leq f(y)-f(x) \quad \Rightarrow \quad \\ f(y) \geq f(x)+\nabla f(x)(y-x)$
二阶特性：如果函数二阶可微分，则$f$为凸函数当且仅当$dom(f)$为凸，且对于所有$x \in dom(f)$ 都有$\nabla^2f(x)\succeq0$
Jensen不等式：假若$f$为凸，并且$X$由$dom(f)$所支持的随机变量，则有$f(\mathbb{E}[x])\leq\mathbb{E}[f(x)]$
2.4保凸操作
非负线性组合
$f_1,...,f_m$均为凸函数，那么对任意$a_1,...a_m\geq0$均有$a_1f_1+...+a_mf_m$为凸。
逐点最大化
如果$f_s$对于任意$s\in S$均为凸，那么$f(x)=max_{s\in S}f_s(x)$是凸函数。
部分最小化
如果$g(x,y)$在任意$x,y$处为凸函数，并且$C$是凸的，那么$f(x)=min_{y\in C}g(x,y)$为凸函数。
2.5 证明凸函数例子