凸优化

假设 $x^\star$ 只是局部极小值，而存在某个 $y \in C$ 使得 $f(y) < f(x^\star)$。凸性迫使 $f$ 在从 $x^\star$ 到 $y$ 的线段上、任意接近 $x^\star$ 处都位于该线段下方：对充分小的 $\theta > 0$，有 $f(\theta y + (1-\theta) x^\star) \le \theta f(y) + (1-\theta) f(x^\star) < f(x^\star)$。这与 $x^\star$ 是局部极小值矛盾，因为点 $\theta y + (1-\theta)x^\star$ 可以任意接近 $x^\star$。

设 $x^\star \in C$ 是局部极小值点，因此存在半径 $r > 0$ 使得对所有满足 $\|z - x^\star\| \le r$ 的 $z \in C$ 都有 $f(z) \ge f(x^\star)$。反证假设存在某点 $y \in C$ 满足 $f(y) < f(x^\star)$。

对任意 $\theta \in (0, 1)$，由集合与函数的凸性可知 $z_\theta = \theta y + (1 - \theta)x^\star \in C$ 且 $f(z_\theta) \le \theta f(y) + (1 - \theta)f(x^\star) = f(x^\star) + \theta(f(y) - f(x^\star)) < f(x^\star)$。

因为 $\|z_\theta - x^\star\| = \theta \|y - x^\star\|$，选取 $0 < \theta \le \dfrac{r}{\|y - x^\star\|}$ 即可保证 $\|z_\theta - x^\star\| \le r$ 同时 $f(z_\theta) < f(x^\star)$，这与局部极小性矛盾。

互补松弛性表明，不等式约束 $g_i(x) \le 0$ 在 $x^\star$ 处要么不起作用（$g_i(x^\star) < 0$，因此边界没有推着 $x^\star$，其乘子 $\lambda_i^\star = 0$），要么起作用（$g_i(x^\star) = 0$，因此边界墙壁可以用力 $\lambda_i^\star \ge 0$ 反向推回）。此时驻点条件说明 $-\nabla f(x^\star)$ 恰好由起作用边界的外法向 $\nabla g_i(x^\star)$ 的非负线性组合所平衡。

首先设 $(x^\star, \lambda^\star, \nu^\star)$ 满足KKT条件。由于 $\lambda_i^\star \ge 0$ 且各约束函数为凸函数或仿射函数，拉格朗日函数 $x \mapsto \mathcal{L}(x, \lambda^\star, \nu^\star)$ 是凸函数，故驻点条件 $\nabla_x \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = 0$ 意味着该点在全空间上极小化拉格朗日函数。

对任意满足 $g_i(x) \le 0$ 和 $h_j(x) = 0$ 的可行点 $x$，利用互补松弛性 $\lambda_i^\star g_i(x^\star) = 0$ 可得不等式链 $f(x^\star) = \mathcal{L}(x^\star, \lambda^\star, \nu^\star) \le \mathcal{L}(x, \lambda^\star, \nu^\star) = f(x) + \sum_{i=1}^m \lambda_i^\star g_i(x) + \sum_{j=1}^p \nu_j^\star h_j(x) \le f(x)$，从而证明全局最优性。

反之，在斯莱特条件下，强对偶性保证存在最优对偶乘子使得 $f(x^\star) = g(\lambda^\star, \nu^\star) = \inf_x \mathcal{L}(x, \lambda^\star, \nu^\star) \le \mathcal{L}(x^\star, \lambda^\star, \nu^\star) = f(x^\star) + \sum_{i=1}^m \lambda_i^\star g_i(x^\star) \le f(x^\star)$。该链中的两个不等号都必须取等号，从而迫使驻点条件与互补松弛性对每个约束均成立。

线性规划是可行集为多面体的凸问题；对于多面体约束无需内点假设，分离超平面定理（法卡斯引理）保证了存在使对偶间隙为零的对偶乘子 $y^\star$。对于一般凸规划，只要满足斯莱特条件，强对偶性就成立。

对任意满足 $Ax = b$、$x \ge 0$ 的原始可行向量和任意满足 $A^\top y \le c$ 的对偶可行向量，取内积即得弱对偶性：$b^\top y = (Ax)^\top y = x^\top(A^\top y) \le x^\top c = c^\top x$。

用乘子 $s \ge 0$ 构造拉格朗日函数 $\mathcal{L}(x, y, s) = c^\top x + y^\top(b - Ax) - s^\top x = b^\top y + (c - A^\top y - s)^\top x$。对无约束原始变量求下确界，仅当 $c - A^\top y - s = 0$ 时才得到有限对偶值，从而恢复对偶约束与对偶目标函数 $g(y, s) = b^\top y$。

若 $x^\star$ 是最优值为 $p^\star = c^\top x^\star$ 的原始最优解，由法卡斯引理（多面体锥的超平面分离）保证存在满足 $A^\top y^\star \le c$ 且 $b^\top y^\star \ge p^\star$ 的向量 $y^\star$。结合弱对偶性即得 $b^\top y^\star = c^\top x^\star$。