引言
优化问题千差万别，但凸优化问题拥有一个关键性质：任何局部极小点都是全局极小点，且存在完整的最优性判据与对偶理论。这使得「判断一个问题是否为凸」往往比「用什么算法求解」更重要——凸性一旦确认，问题的可解性与求解效率就有了理论保证。本文介绍凸集与凸函数的判定、Lagrange 对偶的构造、强弱对偶定理，重点推导 Karush-Kuhn-Tucker（KKT）最优性条件，并通过数值实验验证这些条件，最后以支持向量机（SVM）为例展示对偶理论的工程价值。
理论基础
凸集与凸函数
集合 $C$ 若对任意两点连线仍在集合内（$\theta x + (1-\theta)y \in C$，$\theta \in [0,1]$）则称为凸集；超平面、半空间、范数球都是凸集，凸集对任意交运算封闭。函数 $f$ 若定义域为凸集且满足 Jensen 不等式 $f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta)f(y)$ 则称为凸函数。可微凸函数有两个常用判据：一阶条件（图象位于任意切线上方）
$$f(y) \ge f(x) + \nabla f(x)^T (y - x), \qquad \forall x, y \in \mathrm{dom},f$$
以及二阶条件 Hessian 半正定 $\nabla^2 f(x) succeq 0$。一阶条件直接蕴含：$\nabla f(x^*) = 0$ 的 $x^*$ 必为全局极小点。
Lagrange 对偶
考虑标准形式问题：极小化 $f_0(x)$，约束 $f_i(x) \le 0$（$i=1,\dots,m$）与 $h_j(x) = 0$（$j=1,\dots,p$），最优值记为 $p^*$。引入乘子 $\lambda succeq 0$ 与 $\nu$，构造 Lagrange 函数
$$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^{m} \lambda_i f_i(x) + \sum_{j=1}^{p} \nu_j h_j(x)$$
对偶函数定义为 $g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)$。无论原问题是否凸，$g$ 都是一族仿射函数的逐点下确界，因而总是凹函数；对偶问题「在 $\lambda succeq 0$ 下极大化 $g$」因此总是凸优化问题。弱对偶不等式 $d^* \le p^*$ 恒成立；对凸问题，若存在严格可行点（Slater 条件：存在 $x$ 使 $f_i(x) < 0$ 对所有不等式约束成立），则强对偶成立 $d^* = p^*$，对偶间隙为零。
KKT 条件
设凸问题强对偶成立，则 $x^*$ 与 $(\lambda^*, \nu^*)$ 分别为原始与对偶最优解的充要条件是 KKT 条件：
$$\nabla f_0(x^*) + \sum_{i=1}^{m} \lambda_i^* \nabla f_i(x^*) + \sum_{j=1}^{p} \nu_j^* \nabla h_j(x^*) = 0 \quad (\text{平稳性})$$
$$f_i(x^*) \le 0 (\text{原始可行}), \qquad \lambda_i^* \ge 0 (\text{对偶可行}), \qquad \lambda_i^* f_i(x^*) = 0 (\text{互补松弛})$$
互补松弛条件含义深刻：只有当约束在最优点处起作用（$f_i(x^*) = 0$）时对应乘子才可能非零；不起作用的约束乘子必为零。经济学中乘子 $\lambda_i^*$ 解释为约束放松一个单位时最优值的边际改善（影子价格），这与灵敏度分析 $\partial p^*/\partial u_i = -\lambda_i^*$ 一致。
数值方法与实现
考察非负约束二次规划（NNLS 型）：极小化 $\frac{1}{2}x^T Q x - b^T x$，约束 $x \ge 0$。这是凸问题且 Slater 条件自动满足，可用投影梯度法求解——每步梯度下降后投影回可行域 $\mathbb{R}_+^n$，步长取梯度 Lipschitz 常数 $L = \lambda_{\max}(Q)$ 的倒数保证单调下降。KKT 条件此处化为 $x \ge 0$、$\nabla f(x) = Qx - b \ge 0$、$x_i \cdot (Qx - b)_i = 0$：
import numpy as np
def proj_grad_qp(Q, b, iters=3000):
"""min 1/2 x'Qx - b'x s.t. x >= 0, 投影梯度法"""
x = np.zeros(len(b))
L = np.linalg.norm(Q, 2) # 梯度 Lipschitz 常数
for _ in range(iters):
x = np.maximum(x - (Q @ x - b) / L, 0.0)
return x
rng = np.random.default_rng(0)
n = 20
M = rng.standard_normal((n, n))
Q = M.T @ M + 0.1 * np.eye(n) # 构造对称正定 Q
b = rng.standard_normal(n)
x = proj_grad_qp(Q, b)
g = Q @ x - b
print(f"原始可行 min(x) = {x.min(): .3e} (应 >= 0)")
print(f"对偶可行 min(grad) = {g.min(): .3e} (应 >= 0)")
print(f"互补松弛 max|x.*grad| = {np.abs(x * g).max():.3e} (应 ≈ 0)")三个残差同时趋零，数值验证 KKT 条件得到满足。对大规模问题可换用加速投影梯度（FISTA，收敛速率 $\mathcal{O}(1/k^2)$）或算子分裂框架。
工程案例分析
SVM 硬间隔问题是对偶理论的经典应用：极小化 $\frac{1}{2}|w|^2$，约束 $y_i(w^T x_i + b) \ge 1$。其对偶问题为极大化 $\sum_i \alpha_i - \frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j x_i^T x_j$，约束 $\alpha_i \ge 0$、$\sum \alpha_i y_i = 0$。互补松弛条件 $\alpha_i,[y_i(w^Tx_i+b)-1]=0$ 表明：只有恰好落在间隔边界上的样本（支持向量）才有非零乘子，$w = \sum_i \alpha_i y_i x_i$ 只由它们决定——这解释了 SVM 解的稀疏性与泛化能力。对偶形式还使目标函数只依赖内积 $x_i^Tx_j$，为核技巧（kernel trick）打开大门。类似地，Markowitz 投资组合优化、电网最优潮流（OPF）的二阶锥松弛，都依赖对偶与 KKT 条件获得可计算的最优性证书。
| KKT 要素 | LP：$\min c^Tx, Ax=b, x\ge0$ | SVM 对偶 | 非负 QP |
|---|---|---|---|
| 平稳性 | $c - A^T\nu - \lambda = 0$ | $\alpha$ 的线性等式约束 | $Qx - b - \lambda = 0$ |
| 原始可行 | $Ax = b, x \ge 0$ | $\alpha \ge 0$ | $x \ge 0$ |
| 对偶可行 | $\lambda \ge 0$ | $0 \le \alpha_i \le C$（软间隔） | $\lambda \ge 0$ |
| 互补松弛 | $x_i\lambda_i = 0$ | $\alpha_i(\text{间隔}-1)=0$ | $x_i\lambda_i = 0$ |
结论与展望
对偶理论把带约束的原始问题转化为总是凸的对偶问题，KKT 条件则给出刻画最优解的完整代数方程组——它既是理论分析工具，也是内点法、原始-对偶混合梯度等现代算法的设计起点。进一步可关注：非凸问题中的对偶间隙估计、锥规划（SOCP/SDP）对偶，以及 ADMM 等算子分裂方法背后的 Douglas-Rachford 不动点解释——它与 Banach 不动点理论一脉相承。
发表回复