凸最佳化 - 凸包

一組點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 )$

因此，凸包是一個凸集。