凸优化 - 凸包

一组点S的凸包是包含S中所有点在其内部或边界上的最小凸区域的边界。

或

设$S\subseteq \mathbb{R}^n$，S的凸包，记为$Co\left ( S \right )$，是S的所有凸组合的集合，即$x \in Co\left ( S \right )$当且仅当$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 \right )= \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 \right \}$ 证明凸包是一个凸集。

证明

设$x_1,x_2 \in Co\left ( S \right )$，则$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$

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

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

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

考虑系数，

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

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

因此，凸包是一个凸集。