凸集的极点



设S是$\mathbb{R}^n$中的一个凸集。如果向量$x \in S$满足:当$x= \lambda x_1+\left ( 1-\lambda \right )x_2$,其中$x_1, x_2 \in S$且$\lambda \in\left ( 0, 1 \right )$时,蕴含$x=x_1=x_2$,则称x是S的极点。

示例

步骤1 − $S=\left \{ \left ( x_1,x_2 \right ) \in \mathbb{R}^2:x_{1}^{2}+x_{2}^{2}\leq 1 \right \}$

极点,$E=\left \{ \left ( x_1, x_2 \right )\in \mathbb{R}^2:x_{1}^{2}+x_{2}^{2}= 1 \right \}$

步骤2 − $S=\left \{ \left ( x_1,x_2 \right )\in \mathbb{R}^2:x_1+x_2< 2, -x_1+2x_2\leq 2, x_1,x_2\geq 0 \right \}$

极点,$E=\left \{ \left ( 0, 0 \right), \left ( 2, 0 \right), \left ( 0, 1 \right), \left ( \frac{2}{3}, \frac{4}{3} \right) \right \}$

步骤3 − S是由点$\left \{ \left ( 0,0 \right ), \left ( 1,1 \right ), \left ( 1,3 \right ), \left ( -2,4 \right ),\left ( 0,2 \right ) \right \}$构成的多胞体

极点,$E=\left \{ \left ( 0,0 \right ), \left ( 1,1 \right ),\left ( 1,3 \right ),\left ( -2,4 \right ) \right \}$

备注

  • 凸集S的任何点都可以表示为其极点的凸组合。

  • 这仅适用于$\mathbb{R}^n$中的闭合有界集。

  • 对于无界集,这可能不成立。

k个极点

凸集中的一个点被称为k极点当且仅当它是S内k维凸集的内点,并且它不是S内(k+1)维凸集的内点。基本上,对于凸集S,k个极点构成k维开面。

广告