凸最適化-極錐

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 ^ {**} $です。