凸最適化-プログラミングの問題

凸計画問題には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 $です。