Skrajny punkt zbioru wypukłego

Niech S będzie wypukłym zbiorem w $ \ mathbb {R} ^ n $. Mówi się, że wektor $ x \ in S $ jest skrajnym punktem S, jeśli $ x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ z $ x_1, x_2 \ in S $ i $ \ lambda \ in \ left (0, 1 \ right) \ Rightarrow x = x_1 = x_2 $.

Przykład

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

Punkt skrajny, $ 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 \ } $

Punkt skrajny, $ 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 jest polytopem utworzonym przez punkty $ \ left \ {\ left (0,0 \ right), \ left (1,1 \ right), \ left (1,3 \ right), \ left (-2, 4 \ right), \ left (0,2 \ right) \ right \} $

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

Uwagi

• Dowolny punkt zbioru wypukłego S można przedstawić jako wypukłą kombinację jego skrajnych punktów.

• Jest to prawdziwe tylko dla zamkniętych i ograniczonych zbiorów w $ \ mathbb {R} ^ n $.

• Może to nie być prawdą w przypadku nieograniczonych zestawów.

k skrajne punkty

Punkt w zbiorze wypukłym nazywa się k ekstremum wtedy i tylko wtedy, gdy jest punktem wewnętrznym k-wymiarowego zbioru wypukłego w S, a nie jest punktem wewnętrznym zbioru (k + 1) - wymiarowego wypukłego w S. Zasadniczo dla zbioru wypukłego S, k skrajne punkty tworzą k-wymiarowe powierzchnie otwarte.