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