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}$ 处也可微，则

$\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 条件得到满足。