Titik ekstrim dari himpunan cembung

Misalkan S himpunan cembung di $ \ mathbb {R} ^ n $. Vektor $ x \ dalam S $ dikatakan sebagai titik ekstrim dari S jika $ x = \ lambda x_1 + \ left (1- \ lambda \ right) x_2 $ dengan $ x_1, x_2 \ dalam S $ dan $ \ lambda \ di \ kiri (0, 1 \ kanan) \ Panah kanan x = x_1 = x_2 $.

Contoh

Step 1 - $ S = \ kiri \ {\ kiri (x_1, x_2 \ kanan) \ dalam \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} \ leq 1 \ kanan \ } $

Titik ekstrem, $ E = \ kiri \ {\ kiri (x_1, x_2 \ kanan) \ in \ mathbb {R} ^ 2: x_ {1} ^ {2} + x_ {2} ^ {2} = 1 \ kanan \} $

Step 2 - $ S = \ kiri \ {\ kiri (x_1, x_2 \ kanan) \ in \ mathbb {R} ^ 2: x_1 + x_2 <2, -x_1 + 2x_2 \ leq 2, x_1, x_2 \ geq 0 \ right \ } $

Titik ekstrim, $ E = \ kiri \ {\ kiri (0, 0 \ kanan), \ kiri (2, 0 \ kanan), \ kiri (0, 1 \ kanan), \ kiri (\ frac {2} {3 }, \ frac {4} {3} \ kanan) \ kanan \} $

Step 3 - S adalah polytope yang dibuat oleh titik $ \ kiri \ {\ kiri (0,0 \ kanan), \ kiri (1,1 \ kanan), \ kiri (1,3 \ kanan), \ kiri (-2, 4 \ kanan), \ kiri (0,2 \ kanan) \ kanan \} $

Titik ekstrim, $ E = \ kiri \ {\ kiri (0,0 \ kanan), \ kiri (1,1 \ kanan), \ kiri (1,3 \ kanan), \ kiri (-2,4 \ kanan) \ kanan \} $

Catatan

  • Titik mana pun dari himpunan cembung S, dapat direpresentasikan sebagai kombinasi cembung dari titik ekstremnya.

  • Ini hanya benar untuk set tertutup dan berbatas di $ \ mathbb {R} ^ n $.

  • Ini mungkin tidak benar untuk set tak terbatas.

k poin ekstrim

Sebuah titik dalam himpunan cembung disebut k ekstrim jika dan hanya jika titik interior himpunan cembung berdimensi-k di dalam S, dan bukan titik interior himpunan cembung berdimensi a (k + 1) di dalam S. Pada dasarnya, untuk himpunan cembung S, titik ekstrim k membuat sisi terbuka berdimensi-k.