Point extrême d'un ensemble convexe

Soit S un ensemble convexe dans $ \ mathbb {R} ^ n $. On dit qu'un vecteur $ x \ dans S $ est un point extrême de S si $ x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ avec $ x_1, x_2 \ in S $ et $ \ lambda \ dans \ left (0, 1 \ right) \ Rightarrow x = x_1 = x_2 $.

Exemple

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

Point extrême, $ E = \ left \ {\ left (x_1, x_2 \ right) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} = 1 \ right \} $

Step 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 \ } $

Point extrême, $ E = \ left \ {\ left (0, 0 \ right), \ left (2, 0 \ right), \ left (0, 1 \ right), \ left (\ frac {2} {3 }, \ frac {4} {3} \ right) \ right \} $

Step 3 - S est le polytope formé par les points $ \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2, 4 \ droite), \ gauche (0,2 \ droite) \ droite \} $

Point extrême, $ E = \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2,4 \ right) \ droite \} $

Remarques

• Tout point de l'ensemble convexe S peut être représenté comme une combinaison convexe de ses points extrêmes.

• Ce n'est vrai que pour les ensembles fermés et bornés dans $ \ mathbb {R} ^ n $.

• Cela peut ne pas être vrai pour les ensembles illimités.

k points extrêmes

Un point dans un ensemble convexe est appelé k extrême si et seulement si c'est le point intérieur d'un ensemble convexe à k dimensions dans S, et ce n'est pas un point intérieur d'un ensemble convexe à (k + 1) dimensions dans S. Fondamentalement, pour un ensemble convexe S, k points extrêmes forment des faces ouvertes de k dimensions.