CMU凸优化笔记--凸集和凸函数
结束了一段时间的学习任务，于是打算做个总结。主要内容都是基于CMU的Ryan Tibshirani开设的Convex Optimization课程做的笔记。这里只摘了部分内容做了笔记，很感谢Ryan Tibshirani在官网中所作的课程内容开源。也很感谢韩龙飞在CMU凸优化课程中的中文笔记，我在其基础上做了大量的内容参考。才疏学浅，忘不吝赐教。
1、凸集合
1.1 基本概念
定义：给定一个集合$C \subseteq \mathbb{R}^n $,满足下列条件则称为凸集
$x,y \in C \Rightarrow tx+(1-t)y \in C $ 对于任意的 $ 0 \leq t \leq 1$
直观上看，可以利用下图帮助理解，假定我们的变量在二维空间中，$x,y$为二维空间变量，黑体线代表的向量为$tx+(1-t)y$，$t$取值范围为$[0,1]$，那么无论t怎么变化，向量$tx+(1-t)y$总会落在$x$和$y$张成的集合空间中。
那么从定义出发，我们也能知道非凸集的情况，下图左侧为凸集，右图为非凸集
一句话来概括凸集就是集合内任意两点间连线依旧在集合内。
1.2 凸集简单例子
凸包(convex hull)：给定集合内的任意$k$个元素$x_1,...,x_k \in \mathbb{R}^n$,任意的线性组合形式：
$\theta_1 x_1+...+\theta_k x_k,\theta_i \leq,i=1,...,k$ 并且$ \sum_{i=1}^{k}\theta_i=1$。称之为集合的convex hull,表示为$conv(C)$。convex hull总是凸的。可以直观认为凸包就是最外围的元素所围成的集合外壳，下图是两个凸包的例子：
空集、点、线都是凸集合
范数球（Norm ball）: 半径为$r$的范数球为：$\left \{x:||x|| \leq r \right \}$
超平面（Hyperplane）: 给定任意$a,b$ ,$\left \{x:a^Tx=b \right \}$
半空间（Half space）: $\left \{x:a^Tx \leq b \right \}$
仿射空间(Affine space):$\left \{x:Ax = b \right \}$
多面体(Polyhedron):$\left \{x:Ax \leq b \right \}$，下图为多面体
Note:集合$\left \{x:Ax \leq b,Cx=d \right\}$也是一个Polyhedron吗？
Answer:是的。因为对于任意的$Cx=d$，都可写成$Cx \leq d$ 与$-Cx \leq -d$,这样就和$Ax \leq b $形式一致。
1.3 锥（Cone）：
定义：给定$C \in \mathbb{R}^n $，满足$x \in C \Rightarrow tx\in C$ 对于任意$ t\geq 0$称之为锥。
凸锥（convex cone）：$x_1,x_2 \in C \Rightarrow t_1 x_1+t_2 x_2 \in C $,对于任意$ t_1,t_2 \geq 0$都成立，那么称集合$C$为凸锥。显然凸锥是锥的一种。
例子：
范数锥(Norm cone):$\left \{(x,t):||x|| \leq t \right \}$，对于一范数和二范数成立。下图取定不同的$t$做出了三维情况下的图：
正规锥(Normal cone):给定任意集合$C$，集合内任意一点$x \in C$,定义：
$\mathbb{N}_c(x)=\left \{g:g^Tx \geq g^Ty ,for \quad any \quad y \in C \right \}$
其含义是指Normal cone中的点与集合$C$内的点的内积永远大于集合内任意点与Normal cone内点的内积。如下图所示：
1.4 凸集的一些特性
可分离超平面理论（Separating hyperplane theorem）：两个不相交的凸集总存在一个超平面能将两者分离，如果$C \bigcap D = \varnothing $,那么总存在着$a,b$使得有:
$C \subseteq \left \{x:a^Tx \leq b \right \}$ ,$D \subseteq \left \{x:x^T \geq b \right \}$。如下图所示：