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条件が満たされます。