Convex-optimization-sufficient-necessary-conditions-for-global-optima
グローバルオプティマの十分かつ必要な条件
定理
fを2階微分可能な関数とします。 $ \ bar \ {x} $がローカルミニマムの場合、$ \ bigtriangledown f \ left（\ bar \ {x} \ right）= 0 $およびヘッセ行列$ H \ left（\ bar \ {x} \ right）$は正の半正定です。
証明
$ d \ in \ mathbb \ {R} ^ n $とします。 fは$ \ bar \ {x} $で2階微分可能であるため。
したがって、
$ f \ left（\ bar \ {x} + \ lambda d \ right）= f \ left（\ bar \ {x} \ right）+ \ lambda \ bigtriangledown f \ left（\ bar \ {x} \ right） ^ T d + \ lambda ^ 2d ^ TH \ left（\ bar \ {x} \ right）d + \ lambda ^ 2d ^ TH \ left（\ bar \ {x} \ right）d + $
$ \ lambda ^ 2 \ left \ | d \ right \ | ^ 2 \ beta \ left（\ bar \ {x}、\ lambda d \ right）$
ただし、$ \ bigtriangledown f \ left（\ bar \ {x} \ right）= 0 $および$ \ beta \ left（\ bar \ {x}、\ lambda d \ right）\ rightarrow 0 $ as $ \ lambda \ rightarrow 0 $
$ \ Rightarrow f \ left（\ bar \ {x} + \ lambda d \ right）-f \ left（\ bar \ {x} \ right）= \ lambda ^ 2d ^ TH \ left（\ bar \ {x} \ right）d $
$ \ bar \ {x} $は極小値であるため、$ f \ left（x \ right）\ leq f \ left（\ bar \ {x} + \ lambda d \ right）、\ forall \ lambda \ in \ left（0、\ delta \ right）$
定理
$ f：S \ rightarrow \ mathbb \ {R} ^ n $で、$ S \ subset \ mathbb \ {R} ^ n $をSで2階微分可能とします。 $ \ bigtriangledown f \ left（x \ right）= 0 $および$ H \ left（\ bar \ {x} \ right）$が正の半正である場合、すべての$ x \ in S $に対して$ \ bar \ {x} $はグローバルな最適解です。
証明
$ H \ left（\ bar \ {x} \ right）$は半正の正であるため、fはS上の凸関数です。 fは微分可能であり、$ \ bar \ {x} $で凸であるため
$ \ bigtriangledown f \ left（\ bar \ {x} \ right）^ T \ left（x- \ bar \ {x} \ right）\ leq f \ left（x \ right）-f \ left（\ bar \ {x} \ right）、\ forall x \ in S $
$ \ bigtriangledown f \ left（\ bar \ {x} \ right）= 0なので、f \ left（x \ right）\ geq f \ left（\ bar \ {x} \ right）$
したがって、$ \ bar \ {x} $はグローバルな最適値です。
定理
$ \ bar \ {x} \ in S $が問題$ f：S \ rightarrow \ mathbb \ {R} $の局所最適解であるとします。Sは$ \ mathbb \ {R} ^の空でないサブセットですn $およびSは凸です。 $ min \：f \ left（x \ right）$ここで、$ x \ in S $。
その後：
- $ \ bar \ {x} $はグローバルな最適なソリューションです。
- $ \ bar \ {x} $が厳密に局所的最小値であるか、fが厳密に凸関数である場合、$ \ bar \ {x} $は一意のグローバル最適解であり、強い局所的最小値でもあります。
証明
$ \ bar \ {x} $を、$ x \ neq \ bar \ {x} $および$ f \ left（\ bar \ {x} \ right）= f \ left（ \ hat \ {x} \ right）$
$ \ hat \ {x}、\ bar \ {x} \ in S $およびSは凸であるため、$ \ frac \ {\ hat \ {x} + \ bar \ {x}} \ {2} \ in S $とfは厳密に凸です。
$ \ Rightarrow f \ left（\ frac \ {\ hat \ {x} + \ bar \ {x}} \ {2} \ right）<\ frac \ {1} \ {2} f \ left（\ bar \ {x} \ right）+ \ frac \ {1} \ {2} f \ left（\ hat \ {x} \ right）= f \ left（\ hat \ {x} \ right）$
これは矛盾です。
したがって、$ \ hat \ {x} $は一意のグローバル最適ソリューションです。
帰結
$ f：S \ subset \ mathbb \ {R} ^ n \ rightarrow \ mathbb \ {R} $を微分可能な凸関数とし、$ \ phi \ neq S \ subset \ mathbb \ {R} ^ n $を凸とするセット。 問題$ min f \ left（x \ right）、x \ in S $を考慮し、$ \ bigtriangledown f \ left（\ bar \ {x} \ right）の場合、$ \ bar \ {x} $は最適なソリューションです^ T \ left（x- \ bar \ {x} \ right）\ geq 0、\ forall x \ in S. $
証明
$ \ bar \ {x} $が最適なソリューションであるとします。つまり、$ f \ left（\ bar \ {x} \ right）\ leq f \ left（x \ right）、\ forall x \ in S $
$ \ Rightarrow f \ left（x \ right）= f \ left（\ bar \ {x} \ right）\ geq 0 $
$ f \ left（x \ right）= f \ left（\ bar \ {x} \ right）+ \ bigtriangledown f \ left（\ bar \ {x} \ right）^ T \ left（x- \ bar \ { x} \ right）+ \ left \ | x- \ bar \ {x} \ right \ | \ alpha \ left（\ bar \ {x}、x- \ bar \ {x} \ right）$
ここで、$ \ alpha \ left（\ bar \ {x}、x- \ bar \ {x} \ right）\ rightarrow 0 $ as $ x \ rightarrow \ bar \ {x} $
$ \ Rightarrow f \ left（x \ right）-f \ left（\ bar \ {x} \ right）= \ bigtriangledown f \ left（\ bar \ {x} \ right）^ T \ left（x- \ bar \ {x} \ right）\ geq 0 $
帰結
fを$ \ bar \ {x} $で微分可能な凸関数とすると、$ \ bigtriangledown f \ left（\ bar \ {x} \ right）= 0 $の場合、$ \ bar \ {x} $はグローバルな最小値になります。
例
- $ f \ left（x \ right）= \ left（x ^ 2-1 \ right）^ \ {3}、x \ in \ mathbb \ {R} $。 + $ \ bigtriangledown f \ left（x \ right）= 0 \ Rightarrow x = -1,0,1 $。 + $ \ bigtriangledown ^ 2f \ left（\ pm 1 \ right）= 0、\ bigtriangledown ^ 2 f \ left（0 \ right）= 6> 0 $。 + $ f \ left（\ pm 1 \ right）= 0、f \ left（0 \ right）=-1 $ +したがって、$ f \ left（x \ right）\ geq -1 = f \ left（0 \ right）\ Rightarrow f \ left（0 \ right）\ leq f \ left（x \ right）\ forall x \ in \ mathbb \ {R} $
- $ f \ left（x \ right）= x \ log x $は$ S = \ left \\ {x \ in \ mathbb \ {R}、x> 0 \ right \} $で定義されています。 + $ \ {f} 'x = 1 + \ log x $ + $ \ {f}' 'x = \ frac \ {1} \ {x}> 0 $ +したがって、この関数は厳密に凸です。
- $ f \ left（x \ right）= e ^ \ {x}、x \ in \ mathbb \ {R} $は厳密に凸です。
