凸最適化-プログラミングの問題
凸計画問題には4つのタイプがあります-
Step 1 − $ min \：f \ left（x \ right）$、ここで$ x \ in S $とSは$ \ mathbb {R} ^ n $と$ f \ left（x \ right）の空でない凸集合です。 ）$は凸関数です。
Step 2 − $ min \：f \ left（x \ right）、x \ in \ mathbb {R} ^ n $
$ g_i \ left（x \ right）\ geq 0、1 \ leq m_1 $および$ g_i \ left（x \ right）$は凸関数です。
$ g_i \ left（x \ right）\ leq 0、m_1 + 1 \ leq m_2 $および$ g_i \ left（x \ right）$は凹関数です。
$ g_i \ left（x \ right）= 0、m_2 + 1 \ leq m $および$ g_i \ left（x \ right）$は線形関数です。
ここで、$ f \ left（x \ right）$は凸関数です。
Step 3 − $ max \：f \ left（x \ right）$ここで、$ x \ in S $とSは$ \ mathbb {R} ^ n $と$ f \ left（x \ right）の空でない凸集合です。 $は凹関数です。
Step 4 − $ min \：f \ left（x \ right）$、ここで$ x \ in \ mathbb {R} ^ n $
$ g_i \ left（x \ right）\ geq 0、1 \ leq m_1 $および$ g_i \ left（x \ right）$は凸関数です。
$ g_i \ left（x \ right）\ leq 0、m_1 + 1 \ leq m_2 $および$ g_i \ left（x \ right）$は凹関数です。
$ g_i \ left（x \ right）= 0、m_2 + 1 \ leq m $および$ g_i \ left（x \ right）$は線形関数です。
ここで、$ f \ left（x \ right）$は凹関数です。
実行可能な方向のコーン
Sを$ \ mathbb {R} ^ n $の空でない集合とし、$ \ hat {x} \ in \：Closure \ left（S \ right）$とし、Sの実行可能な方向の円錐を$とします。 Dで表される\ hat {x} $は、$ D = \ left \ {d：d \ neq 0、\ hat {x} + \ lambda d \ in S、\ lambda \ in \ left（0、 \ delta \ right）、\ delta> 0 \ right \} $
ゼロ以外の各ベクトル$ d \ in D $は、実行可能方向と呼ばれます。
与えられた関数$ f：\ mathbb {R} ^ n \ Rightarrow \ mathbb {R} $に対して、$ \ hat {x} $で方向を改善する円錐はFで表され、次の式で与えられます。
$$ F = \ left \ {d：f \ left（\ hat {x} + \ lambda d \ right）\ leq f \ left（\ hat {x} \ right）、\ forall \ lambda \ in \ left（ 0、\ delta \ right）、\ delta> 0 \ right \} $$
$ d \ in F $の各方向は、$ \ hat {x} $でのfの改善方向または下降方向と呼ばれます。
定理
Necessary Condition
$ x \ in S $のような問題$ min f \ left（x \ right）$を考えてみましょう。ここで、Sは$ \ mathbb {R} ^ n $の空でない集合です。fが$ \ hat {x} \ in S $の点で微分可能であると仮定します。$ \ hat {x} $が局所最適解である場合、$ F_0 \ cap D = \ phi $ where $ F_0 = \ left \ {d：\ bigtriangledown f \ left（\ hat {x} \ right）^ T d <0 \ right \} $であり、Dは実行可能な方向の円錐です。
Sufficient Condition
$ F_0 \ cap D = \ phi $ fが$ \ hat {x} $の疑似凸関数であり、$ \ hat {x}、N_ \ varepsilon \ left（\ hat {x} \ right）の近傍が存在する場合、\ varepsilon> 0 $で、$ d = x- \ hat {x} \ in D $ for any $ x \ in S \ cap N_ \ varepsilon \ left（\ hat {x} \ right）$、次に$ \ hat {x} $は局所的な最適解です。
証明
Necessary Condition
$ F_0 \ cap D \ neq \ phi $とします。つまり、$ d \ in F_0 $と$ d \ in D $のような$ d \ in F_0 \ cap D $が存在します。
$ d \ in D $なので、$ \ hat {x} + \ lambda d \ in S、\ lambda \ in \ left（0、\ delta_1 \ right）。$のような$ \ delta_1> 0 $が存在します。
$ d \ in F_0 $なので、$ \ bigtriangledown f \ left（\ hat {x} \ right）^ T d <0 $
したがって、$ f \ left（\ hat {x} + \ lambda d \ right）<f \ left（\ hat {x} \ right）、\ forall \ lambda \ infのような$ \ delta_2> 0 $が存在します。 \ left（0、\ delta_2 \ right）$
$ \ delta = min \ left \ {\ delta_1、\ delta_2 \ right \} $とします
次に、$ \ hat {x} + \ lambda d \ in S、f \ left（\ hat {x} + \ lambda d \ right）<f \ left（\ hat {x} \ right）、\ forall \ lambda \ in f \ left（0、\ delta \ right）$
しかし、$ \ hat {x} $は局所的な最適解です。
したがって、それは矛盾です。
したがって、$ F_0 \ cap D = \ phi $
Sufficient Condition
$ F_0 \ cap D \ neq \ phi $ ndとし、fを疑似凸関数とします。
$ d = x- \ hat {x}、\ forall x \ in S \のような$ \ hat {x}、N _ {\ varepsilon} \ left（\ hat {x} \ right）$の近傍が存在するとします。キャップN_ \ varepsilon \ left（\ hat {x} \ right）$
$ \ hat {x} $が局所的な最適解ではないとします。
したがって、$ \ bar {x} \ in S \ cap N_ \ varepsilon \ left（\ hat {x} \ right）$が存在し、$ f \ left（\ bar {x} \ right）<f \ left（ \ hat {x} \ right）$
$ S \ cap N_ \ varepsilon \ left（\ hat {x} \ right）、d = \ left（\ bar {x}-\ hat {x} \ right）\ in D $を仮定すると
fの擬凸性により、
$$ f \ left（\ hat {x} \ right）> f \ left（\ bar {x} \ right）\ Rightarrow \ bigtriangledown f \ left（\ hat {x} \ right）^ T \ left（\ bar {x}-\ hat {x} \ right）<0 $$
$ \ Rightarrow \ bigtriangledown f \ left（\ hat {x} \ right）^ T d <0 $
$ \ Rightarrow d \ in F_0 $
したがって、$ F_0 \ cap D \ neq \ phi $
これは矛盾です。
したがって、$ \ hat {x} $は局所最適解です。
次の問題を考えてみましょう。$ min \：f \ left（x \ right）$ここで、$ x \ in X $は、$ g_x \ left（x \ right）\ leq 0、i = 1,2、...、 m $
$ f：X \ rightarrow \ mathbb {R}、g_i：X \ rightarrow \ mathbb {R} ^ n $そしてXは$ \ mathbb {R} ^ n $の開集合です
$ S = \ left \ {x：g_i \ left（x \ right）\ leq 0、\ forall i \ right \} $とします。
$ \ hat {x} \ in X $とし、次に$ M = \ left \ {1,2、...、m \ right \} $
$ I = \ left \ {i：g_i \ left（\ hat {x} \ right）= 0、i \ in M \ right \} $とします。ここで、Iは$ \ hat {xのすべてのアクティブな制約のインデックスセットと呼ばれます。 } $
$ J = \ left \ {i：g_i \ left（\ hat {x} \ right）<0、i \ in M \ right \} $とします。ここで、Jは$ \ hat {xのすべてのアクティブな制約のインデックスセットと呼ばれます。 } $。
$ F_0 = \ left \ {d \ in \ mathbb {R} ^ m：\ bigtriangledown f \ left（\ hat {x} \ right）^ T d <0 \ right \} $
$ G_0 = \ left \ {d \ in \ mathbb {R} ^ m：\ bigtriangledown gI \ left（\ hat {x} \ right）^ T d <0 \ right \} $
または$ G_0 = \ left \ {d \ in \ mathbb {R} ^ m：\ bigtriangledown gi \ left（\ hat {x} \ right）^ T d <0、\ forall i \ in I \ right \} $
補題
$ S = \ left \ {x \ in X：g_i \ left（x \ right）\ leq 0、\ forall i \ in I \ right \} $であり、Xが$ \ mathbb {Rで空でない開集合である場合} ^ n $。$ \ hat {x} \ in S $と$ g_i $が$ \ hat {x}、i \ in I $で異なり、$ g_i $が$ i \ in J $が$ \ hat {xで連続であるとします。 } $、次に$ G_0 \ subseteq D $。
証明
$ d \ in G_0 $
$ \ hat {x} \ in X $であり、Xは開集合であるため、$ \ hat {x} + \ lambda d \ in X $ for $ \ lambda \ in \のような$ \ delta_1> 0 $が存在します。左（0、\ delta_1 \ right）$
また、$ g_ \ hat {x} <0 $と$ g_i $は$ \ hat {x}、\ forall i \ in J $で連続しているため、$ \ delta_2> 0 $、$ g_i \ left（\ hat {x} + \ lambda d \ right）<0、\ lambda \ in \ left（0、\ delta_2 \ right）$
したがって、$ d \ in G_0 $なので、$ \ bigtriangledown g_i \ left（\ hat {x} \ right）^ T d <0、\ forall i \ in I $したがって、$ \ delta_3> 0、g_i \ leftが存在します。 （\ hat {x} + \ lambda d \ right）<g_i \ left（\ hat {x} \ right）= 0 $、for $ \ lambda \ in \ left（0、\ delta_3 \ right）i \ in J $
$ \ delta = min \ left \ {\ delta_1、\ delta_2、\ delta_3 \ right \} $とします
したがって、$ \ hat {x} + \ lambda d \ in X、g_i \ left（\ hat {x} + \ lambda d \ right）<0、i \ in M $
$ \ Rightarrow \ hat {x} + \ lambda d \ in S $
$ \ Rightarrow d \ in D $
$ \ Rightarrow G_0 \ subseteq D $
したがって、証明されました。
定理
Necessary Condition
$ f $と$ g_i、i \ in I $が$ \ hat {x} \ in Sで異なり、$と$ g_j $が$ \ hat {x} \ in S $で連続しているとします。$ \ hat {x} $が$ S $の極小値である場合、$ F_0 \ cap G_0 = \ phi $。
Sufficient Condition
$ F_0 \ cap G_0 = \ phi $であり、fが$ \ left（\ hat {x}、g_i 9x \ right）の疑似凸関数である場合、i \ in I $はいくつかの$ \ varepsilon $上の疑似凸関数です-近傍$ \ hat {x}のうち、\ hat {x} $は局所的な最適解です。
備考
$ \ hat {x} $を、$ \ bigtriangledown f \ left（\ hat {x} \ right）= 0 $のように実行可能点とし、$ F_0 = \ phi $とします。したがって、$ F_0 \ cap G_0 = \ phi $ですが、$ \ hat {x} $は最適なソリューションではありません
しかし、$ \ bigtriangledown g \ left（\ hat {x} \ right）= 0 $の場合、$ G_0 = \ phi $、したがって$ F_0 \ cap G_0 = \ phi $
問題を考えてみましょう：$ g \ left（x \ right）= 0 $となるようなmin $ f \ left（x \ right）$。
$ g \ left（x \ right）= 0 $なので、$ g_1 \ left（x \ right）= g \ left（x \ right）<0 $および$ g_2 \ left（x \ right）=-g \ left（x \ right）\ leq 0 $。
$ \ hat {x} \ in S $とし、次に$ g_1 \ left（\ hat {x} \ right）= 0 $および$ g_2 \ left（\ hat {x} \ right）= 0 $とします。
しかし、$ \ bigtriangledown g_1 \ left（\ hat {x} \ right）=-\ bigtriangledown g_2 \ left（\ hat {x} \ right）$
したがって、$ G_0 = \ phi $および$ F_0 \ cap G_0 = \ phi $です。