卡鲁什-库恩-塔克最优性必要条件

---

考虑这个问题 -

$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\左 ( x_1, x_2 \右)=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}$

因此卡鲁什-库恩-塔克条件得到满足。