凸优化 - 凸包

S 中一组点的凸包是包含 S 中所有点的最小凸区域的边界，这些点位于凸区域内部或边界上。

或

设 $S\subseteq \mathbb{R}^n$ S 的凸包，记为 $Co\left ( S ight )$，是 S 所有凸组合的集合，即 $x \in Co\left ( S ight )$ 当且仅当 $x \in \displaystyle\sum\limits_{i=1}^n \lambda_ix_i$，其中 $\displaystyle\sum\limits_{1}^n \lambda_i=1$ 且 $\lambda_i \geq 0 \forall x_i \in S$

备注 −平面上 S 中一组点的凸包定义一个凸多边形，S 中位于多边形边界上的点定义该多边形的顶点。

定理$Co\left ( S ight )= \left \{ x:x=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i,x_i \in S, \displaystyle\sum\limits_{i=1}^n \lambda_i=1,\lambda_i \geq 0 ight \}$ 证明凸包是凸集。

证明

设 $x_1,x_2 \in Co\left ( S ight )$，则 $x_1=\displaystyle\sum\limits_{i=1}^n \lambda_ix_i$ 和 $x_2=\displaystyle\sum\limits_{i=1}^n \lambda_\gamma x_i$ 其中 $\displaystyle\sum\limits_{i=1}^n \lambda_i=1, \lambda_i\geq 0$ 和 $\displaystyle\sum\limits_{i=1}^n \gamma_i=1,\gamma_i\geq0$

对于 $ heta \in \left ( 0,1 ight )，heta x_1+\left ( 1- heta ight )x_2= heta \displaystyle\sum\limits_{i=1}^n \lambda_ix_i+\left ( 1- heta ight )\displaystyle\sum\limits_{i=1}^n \gamma_ix_i$

$ heta x_1+\left ( 1- heta ight )x_2=\displaystyle\sum\limits_{i=1}^n \lambda_i heta x_i+\displaystyle\sum\limits_{i=1}^n \gamma_i\left ( 1- heta ight )x_i$

$ heta x_1+\left ( 1- heta ight )x_2=\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i heta +\gamma_i\left ( 1- heta ight ) ight ]x_i$

考虑系数，

$\displaystyle\sum\limits_{i=1}^n\left [ \lambda_i heta +\gamma_i\left ( 1- heta ight ) ight ]= heta \displaystyle\sum\limits_{i=1}^n \lambda_i+\left ( 1- heta ight )\displaystyle\sum\limits_{i=1}^n\gamma_i= heta +\left ( 1- heta ight )=1$

因此，$ heta x_1+\left ( 1- heta ight )x_2 \in Co\left ( S ight )$

因此，凸包是凸集。