证明 Kuhn-Tucker 定理

定理 (Kuhn-Tucker). 若存在 $x^* = (x_1^*, \dots, x_k^*)$ 和 $λ^* = (λ_1^*, \dots, λ_n^*)$ 使得 $$\min_{λ \ge 0} d(λ) = \min_{λ \ge 0}\, \max_x L (x, λ) = L(x^*, λ^*)$$ 则 $x^*$ 为原最优化问题 $\mathcal M$ 的解.

由于 $(x^*, λ^*)$ 满足 $\min_{λ \ge 0}\, \max_x L (x, λ) = L(x^*, λ^*)$, $(x^*, λ^*)$ 为函数 $L(x, λ)$ 的鞍点 (saddle point). 证明的核心在于利用鞍点的如下性质: $$L(x, \lambda^*) \leq L(x^*, \lambda^*) \leq L(x^*, \lambda), \quad \forall x \in ℝ^k, \, \forall λ \ge 0$$

我们从这两个不等式出发, 依次说明:

• $x^*$ 是可行的, 即它没有违反任何约束
• 互补松弛性: $\lambda_j^* g_j(x^*) = 0$, $j=1,...,n$
• 对任意可行的 $x \in D$, 均有 $f(x^*) \geq f(x)$

第一步: 证明 $x^*$ 的可行性

观察右侧不等式: $L(x^*, \lambda^*) \leq L(x^*, \lambda)$. 展开拉格朗日函数后可得: $$f(x^*) - \sum_{j=1}^{n} \lambda_j^* g_j(x^*) \leq f(x^*) - \sum_{j=1}^{n} \lambda_j g_j(x^*)$$ 消去 $f(x^*)$ 并移项, 得到: $$\sum_{j=1}^{n} \lambda_j g_j(x^*) \leq \sum_{j=1}^{n} \lambda_j^* g_j(x^*)$$ 反设 $x^*$ 违反了某个约束: $g_k(x^*) > 0$. 我们可以让 $\lambda_k \to \infty$, 不等式左边将趋于正无穷. 矛盾

第二步: 证明互补松弛性

由于不等式 $\sum \lambda_j g_j(x^*) \leq \sum \lambda_j^* g_j(x^*)$ 对任意 $λ \ge 0$ 都成立, 令 $\lambda = 0$: $$0 \leq \sum_{j=1}^{n} \lambda_j^* g_j(x^*)$$ 由于我们已经证明了 $g_j(x^*) \leq 0$, 且已知 $\lambda_j^* \geq 0$, 那么每一项 $\lambda_j^* g_j(x^*)$ 都必定 $\leq 0$. 要使它们的和 $\geq 0$, 唯一的可能就是每一项都等于 0: $$\lambda_j^* g_j(x^*) = 0 \quad \forall j$$ 这意味着 $L(x^*, \lambda^*) = f(x^*) - 0 = f(x^*)$.

第三步: 证明最优性

观察左侧不等式: $L(x, \lambda^*) \leq L(x^*, \lambda^*)$, 代入互补松弛性的结果 $L(x^*, \lambda^*) = f(x^*)$: $$f(x) - \sum_{j=1}^{n} \lambda_j^* g_j(x) \leq f(x^*)$$ 对任意可行的 $x$, 有 $g_j(x) \leq 0$. 又因为 $\lambda_j^* \geq 0$, 所以 $-\sum \lambda_j^* g_j(x) \geq 0$. 由此可得: $$f(x) \leq f(x) - \sum_{j=1}^{n} \lambda_j^* g_j(x) \leq f(x^*)$$ 即对于所有可行解 $x$, 都有 $f(x) \leq f(x^*)$. QED.