凸优化 - 赫尔

---

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\左 ( 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 ) \右]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 )$

因此，凸包是凸集。