Каруш-Кун-Такер Оптимальность Необходимые условия

Рассмотрим проблему —

minf left(x right)$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 {х}$. Кроме того, $\ bigtriangledown g_i \ left (\ hat {x} \ right), i \ in I$ линейно независимы. Если $\ hat {x}$ решает вышеуказанную проблему локально, то существует $u_i, i \ in I$, такой что

$\ bigtriangledown f \ left (x \ right) + \ displaystyle \ sum \ limit_ {i \ in I} u_i \ bigtriangledown g_i \ left (\ hat {x} \ right) = 0$, ui geq0,i inI$\: \: u_i \ geq 0, i \ in I$

Если $g_i, i \ in J$ также дифференцируемы в $\ hat {x}$. затем $\ hat {x}$, затем

$\ bigtriangledown f \ left (\ hat {x} \ right) + \ displaystyle \ sum \ limit_ {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$

пример

Рассмотрим следующую проблему —

minf left(x1,x2 right)= left(x1−3 right)2+ left(x2−2 right)2$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 \}$ , u3=0,u4=0$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)$

Таким образом, помещая эти значения в первое условие условий Каруша-Куна-Такера, мы получаем —

$u_1 = \ frac {1} {3}$ и $u_2 = \ frac {2} {3}$

Таким образом, условия Каруша-Куна-Такера выполняются.