Karush-Kuhn-Tucker 最优性必要条件

考虑问题 −

$min \:f\left ( x ight )$ 使得 $x \in X$，其中 X 是 $\mathbb{R}^n$ 中的开集，且 $g_i \left ( x ight )\leq 0, i=1, 2,...,m$

设 $S=\left \{ x \in X:g_i\left ( x ight )\leq 0, \forall i ight \}$

设 $\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} ight), i \in I$ 是线性独立的。如果 $\hat{x}$ 局部解决了上述问题，则存在 $u_i,i \in I$ 使得

$\bigtriangledown f\left ( x ight)+\displaystyle\sum\limits_{i\in I} u_i \bigtriangledown g_i\left ( \hat{x} ight)=0$，$\:\:u_i \geq 0, i \in I$

如果 $g_i,i \in J$ 在 $\hat{x}$ 处也是可微的。然后 $\hat{x}$，然后

$\bigtriangledown f\left ( \hat{x} ight)+\displaystyle\sum\limits_{i= 1}^m u_i \bigtriangledown g_i\left ( \hat{x} ight)=0$

$u_ig_i\left ( \hat{x} ight)=0, \forall i=1,2,...,m$

$u_i \geq 0 \forall i=1,2,...,m$

示例

考虑以下问题 −

$min \:f\left ( x_1,x_2 ight )=\left ( x_1-3 ight )^2+\left ( x_2-2 ight )^2$

使得 $x_{1}^{2}+x_{2}^{2}\leq 5$，

$x_1,2x_2 \geq 0$ 且 $\hat{x}=\left ( 2,1 ight )$

设 $g_1\left ( x_1, x_2 ight)=x_{1}^{2}+x_{2}^{2}-5$，

$g_2\left ( x_1, x_2 ight)=x_{1}+2x_2-4$

$g_3\left ( x_1, x_2 ight)=-x_{1}$ 且 $g_4\left ( x_1,x_2 ight )=-x_2$

因此上述约束可以写成−

$g_1 \left ( x_1,x_2 ight)\leq 0, g_2 \left ( x_1,x_2 ight) \leq 0$

$g_3 \left ( x_1,x_2 ight)\leq 0,$ 和 $g_4 \left ( x_1,x_2 ight) \leq 0$ 因此，$I=\left \{ 1,2 ight \}$ 因此，$ u_3=0,\:\: u_4=0$

$\bigtriangledown f \left ( \hat{x} ight)=\left ( 2,-2 ight), \bigtriangledown g_1 \left ( \hat{x} ight)= \left ( 4,2 ight)$和

$\bigtriangledown g_2\left ( \hat{x} ight ) =\left ( 1,2 ight )$

因此，将这些值放入 Karush-Kuhn-Tucker 条件的第一个条件中，我们得到 −

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

因此，Karush-Kuhn-Tucker 条件得到满足。