Convex-optimization-extreme-point-of-convex-set

凸集合の極点

Sを$ \ mathbb \ {R} ^ n $の凸集合とします。 ベクトル$ x \ in S $は、$ x = \ lambda x_1 + \ left（1- \ lambda \ right）x_2 $と$ x_1、x_2 \ in S $、および$ \ lambda \の場合、Sの極点と呼ばれますin \ left（0、1 \ right）\ Rightarrow x = x_1 = x_2 $

例

• ステップ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）、\左（-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極値

凸集合内の点は、S内のk次元凸集合の内部点であり、S内の（k + 1）次元凸集合の内部点ではない場合に限り、k極値と呼ばれます。 基本的に、凸集合Sの場合、k個の極点がk次元の開いた面を作成します。