Convex-optimization-karush-kuhn-tucker-optimality-necessary-conditions

Karush-Kuhn-Tucker最適性の必要条件

問題を考慮してください-

$ min \：f \ left（x \ right）$ $ x \ in X $（Xは$ \ mathbb \ {R} ^ n $および$ g_i \ left（x \ right）のオープンセット） leq 0、i = 1、2、…​、m $

$ S = \ left \\ {x \ in X：g_i \ left（x \ right）\ leq 0、\ forall i \ right \} $とする

$ \ hat \ {x} \ in S $とし、$ f $と$ g_i、i \ in I $を$ \ hat \ {x} $と$ g_iで微分可能とし、i \ in J $は$ \ hat \ {x} $。 さらに、$ \ bigtriangledown g_i \ left（\ hat \ {x} \ right）、i \ in I $は線形独立です。 $ \ hat \ {x} $が上記の問題をローカルで解決する場合、次のような$ u_i、i \ in I $が存在します。

$ \ bigtriangledown f \ left（x \ right）+ \ displaystyle \ sum \ limits _ \ {i \ in I} u_i \ bigtriangledown g_i \ left（\ hat \ {x} \ right）= 0 $、$ \：\： u_i \ geq 0、i \ in I $

$ g_i、i \ in J $も$ \ hat \ {x} $で微分可能です。 次に$ \ hat \ {x} $、次に

$ \ bigtriangledown f \ left（\ hat \ {x} \ right）+ \ displaystyle \ sum \ limits _ \ {i = 1} ^ m u_i \ bigtriangledown g_i \ left（\ hat \ {x} \ right）= 0 $

$ u_ig_i \ left（\ hat \ {x} \ right）= 0、\ forall i = 1,2、…​、m $

$ u_i \ geq 0 \ forall i = 1,2、…​、m $

例

次の問題を考慮してください-

$ min \：f \ left（x_1、x_2 \ right）= \ left（x_1-3 \ right）^ 2 + \ left（x_2-2 \ right）^ 2 $

$ x _ \ {1} ^ \ {2} + x _ \ {2} ^ \ {2} \ leq 5 $のように、

$ x_1,2x_2 \ geq 0 $および$ \ hat \ {x} = \ left（2,1 \ right）$

$ g_1 \ left（x_1、x_2 \ right）= x _ \ {1} ^ \ {2} + x _ \ {2} ^ \ {2} -5 $とする

$ g_2 \ left（x_1、x_2 \ right）= x _ \ {1} + 2x_2-4 $

$ g_3 \ left（x_1、x_2 \ right）=-x _ \ {1} $および$ g_4 \ left（x_1、x_2 \ right）=-x_2 $

したがって、上記の制約は次のように書くことができます-

$ g_1 \ left（x_1、x_2 \ right）\ leq 0、g_2 \ left（x_1、x_2 \ right）\ leq 0 $

$ g_3 \ left（x_1、x_2 \ right）\ leq 0、$および$ g_4 \ left（x_1、x_2 \ right）\ leq 0 $したがって、$ I = \ left \\ {1,2 \ right \} $したがって、$ u_3 = 0、\：\：u_4 = 0 $

$ \ bigtriangledown f \ left（\ hat \ {x} \ right）= \ left（2、-2 \ right）、\ bigtriangledown g_1 \ left（\ hat \ {x} \ right）= \ left（4,2 \ right）$および

$ \ bigtriangledown g_2 \ left（\ hat \ {x} \ right）= \ left（1,2 \ right）$

したがって、これらの値をKarush-Kuhn-Tucker条件の最初の条件に入れると、

$ u_1 = \ frac \ {1} \ {3} $および$ u_2 = \ frac \ {2} \ {3} $

したがって、Karush-Kuhn-Tuckerの条件が満たされます。