定理B.30 Karush-Kuhn-Tucker定理

定理B.30 Karush-Kuhn-Tucker定理

假设 $f$, $g_i$ :$X\to \mathbb{R},\forall i\in \left[m\right]$,

• 是凸的且可微，
• 约束条件合格。

那么 $\overline{\mathbf{x}}$ 是约束程序的解 当且仅当 存在 $\overline{\alpha }\ge 0$ 使得，

$$\begin{array}{rl}{\nabla }_{\mathbf{x}}\mathcal{L}\left(\overline{\mathbf{x}},\overline{\alpha }\right)& ={\nabla }_{\mathbf{x}}f\left(\overline{\mathbf{x}}\right)+\overline{\alpha }\cdot {\nabla }_{\mathbf{x}}g\left(\overline{\mathbf{x}}\right)=0,\\ {\nabla }_{\alpha }\mathcal{L}\left(\overline{\mathbf{x}},\overline{\alpha }\right)& =g\left(\overline{\mathbf{x}}\right)\le 0,\\ \overline{\alpha }\cdot g\left(\overline{\mathbf{x}}\right)& =\sum _{i=1}^m{\overline{\alpha }}_i{g}_i\left(\overline{\mathbf{x}}\right)=0.\end{array}\text{\hspace{1em}(B.11)(B.12)(B.13)}$$

条件 B.11-B.13 被称为 KKT条件。

注意，最后两个 KKT条件 等价于

$$g\left(\overline{\mathbf{x}}\right)\le 0\wedge \left(\forall i\in \{1,\dots ,m\},{\bar{\alpha }}_i{g}_i\left(\overline{\mathbf{x}}\right)=0\right).\text{\hspace{1em}(B.14)}$$

这些等式被称为 互补条件。

\begin{proof} 对于正向，由于约束条件合格，如果 $\overline{\mathbf{x}}$ 是解，那么存在 $\overline{\alpha }$ 使得 $\left(\overline{\mathbf{x}},\overline{\alpha }\right)$ 是拉格朗日函数的鞍点且三个条件均满足(第一个条件由鞍点的定义得出，后两个条件由(B.10)得出)。

在相反的方向，如果条件满足，那么对于任何 $\mathbf{x}$ 使得 $g\left(\mathbf{x}\right)\le 0$ ，我们可以写出

$$\begin{array}{rl}& f\left(\mathbf{x}\right)-f\left(\overline{\mathbf{x}}\right)\\ & \ge {\nabla }_{\mathbf{x}}f\left(\overline{\mathbf{x}}\right)\cdot \left(\mathbf{x}-\overline{\mathbf{x}}\right)\text{(convexity of }f\text{)}\\ & =-\sum _{i=1}^m{\overline{\alpha }}_i{\nabla }_{\mathbf{x}}{g}_i\left(\overline{\mathbf{x}}\right)\cdot \left(\mathbf{x}-\overline{\mathbf{x}}\right)\text{(first condition)}\\ & \ge -\sum _{i=1}^m{\overline{\alpha }}_i\left[g_i\left(\mathbf{x}\right)-g_i\left(\overline{\mathbf{x}}\right)\right]\text{(convexity of }{g}_i\text{s)}\\ & =-\sum _{i=1}^m{\overline{\alpha }}_i{g}_i\left(\mathbf{x}\right)\ge 0\text{(third condition)}.\end{array}$$

这表明 $f\left(\overline{\mathbf{x}}\right)$ 是满足约束条件点集中 $f$ 的最小值。 \end{proof}