凸最適化-極錐

Sを$ \ mathbb {R} ^ n $の空でない集合とすると、$ S ^ * $で表されるSの極錐は$ S ^ * = \ left \ {p \ in \ mathbb {Rで与えられます。 } ^ n、p ^ Tx \ leq 0 \:\ forall x \ in S \ right \} $。

リマーク

  • Sが凸でない場合でも、極円錐は常に凸です。

  • Sが空集合の場合、$ S ^ * = \ mathbb {R} ^ n $。

  • 極性は、直交性の一般化と見なすことができます。

$ C \ subseteq \ mathbb {R} ^ n $とすると、Cの直交空間は$ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n:\ left \ langle x、yで表されます。 \ right \ rangle = 0 \ forall x \ in C \ right \} $。

補題

$ S、S_1 $と$ S_2 $を$ \ mathbb {R} ^ n $の空でない集合とすると、次のステートメントが真になります。

  • $ S ^ * $は閉じた凸錐です。

  • $ S \ subseteq S ^ {**} $ここで、$ S ^ {**} $は$ S ^ * $の極錐です。

  • $ S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*} $。

証明

Step 1 − $ S ^ * = \ left \ {p \ in \ mathbb {R} ^ n、p ^ Tx \ leq 0 \:\ forall \:x \ in S \ right \} $

  • $ x_1、x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $および$ x_ {2} ^ {T} x \ leq 0、\ forall x \ in S $

    $ \ lambda \ in \ left(0、1 \ right)、\ left [\ lambda x_1 + \ left(1- \ lambda \ right)x_2 \ right] ^ Tx = \ left [\ left(\ lambda x_1 \ right )^ T + \ left \ {\ left(1- \ lambda \ right)x_ {2} \ right \} ^ {T} \ right] x、\ forall x \ in S $

    $ = \ left [\ lambda x_ {1} ^ {T} + \ left(1- \ lambda \ right)x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left(1- \ lambda \ right)x_ {2} ^ {T} \ leq 0 $

    したがって、$ \ lambda x_1 + \ left(1- \ lambda \ right)x_ {2} \ in S ^ * $

    したがって、$ S ^ * $は凸集合です。

  • $ \ lambda \ geq 0、p ^ {T} x \ leq 0、\ forall \:x \ in S $の場合

    したがって、$ \ lambda p ^ T x \ leq 0、$

    $ \ Rightarrow \ left(\ lambda p \ right)^ T x \ leq 0 $

    $ \ Rightarrow \ lambda p \ in S ^ * $

    したがって、$ S ^ * $は円錐です。

  • $ S ^ * $を表示するには、閉じています。つまり、$ p_n \ rightarrow p $を$ n \ rightarrow \ infty $として表示するには、$ p \ in S ^ * $

    $ \ forall x \ in S、p_ {n} ^ {T} xp ^ T x = \ left(p_n-p \ right)^ T x $

    As $ p_n \ rightarrow p $ as $ n \ rightarrow \ infty \ Rightarrow \ left(p_n \ rightarrow p \ right)\ rightarrow 0 $

    したがって、$ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $。しかし、$ p_ {n} ^ {T} x \ leq 0、\:\ forall x \ in S $

    したがって、$ p ^ Tx \ leq 0、\ forall x \ in S $

    $ \ Rightarrow p \ in S ^ * $

    したがって、$ S ^ * $は閉じられます。

Step 2 − $ S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n:q ^ T p \ leq 0、\ forall p \ in S ^ * \ right \} $

$ x \ in S $、次に$ \ forall p \ in S ^ *、p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

したがって、$ S \ subseteq S ^ {**} $

Step 3 − $ S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n:p ^ Tx \ leq 0、\ forall x \ in S_2 \ right \} $

$ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $以降

したがって、$ \ hat {p} \ in S_2 ^ *の場合、$ then $ \ hat {p} ^ Tx \ leq 0、\ forall x \ in S_2 $

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0、\ forall x \ in S_1 $

$ \ Rightarrow \ hat {p} ^ T \ in S_1 ^ * $

$ \ Rightarrow S_2 ^ * \ subseteq S_1 ^ * $

定理

Cを空でない閉じた凸錐とすると、$ C = C ^ ** $

証明

前の補題による$ C = C ^ {**} $。

証明するには:$ x \ in C ^ {**} \ subseteq C $

$ x \ in C ^ {**} $とし、$ x \ notin C $

次に、基本的な分離定理により、ベクトル$ p \ neq 0 $とスカラー$ \ alpha $が存在し、$ p ^ Ty \ leq \ alpha、\ forall y \ in C $

したがって、$ p ^ Tx> \ alpha $

ただし、$ \ left(y = 0 \ right)\ in C $および$ p ^ Ty \ leq \ alphaであるため、\ forall y \ in C \ Rightarrow \ alpha \ geq 0 $および$ p ^ Tx> 0 $

$ p \ notin C ^ * $の場合、$ p ^ T \ bar {y}> 0 $および$ p ^ T \ left(\ lambda \ bar)のような$ \ bar {y} \ in C $が存在します。 {y} \ right)$は、$ \ lambda $を十分に大きくすることで、任意に大きくすることができます。

これは、$ p ^ Ty \ leq \ alpha、\ forall y \ in C $という事実と矛盾します。

したがって、$ p \ in C ^ * $

$ x \ in C ^ * = \ left \ {q:q ^ Tp \ leq 0なので、\ forall p \ in C ^ * \ right \} $

したがって、$ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

しかし、$ p ^ Tx> \ alpha $

したがって、矛盾です。

したがって、$ x \ in C $

したがって、$ C = C ^ {**} $です。