第 5 章 · 对偶：把问题翻个面看

对偶理论是凸优化的皇冠：每个优化问题都藏着一个"影子问题"，影子问题的最优值给出原问题的全局下界，强对偶时两者相等。拉格朗日乘子不再只是微积分技巧，而是价格的经济学与证书的数学。

拉格朗日函数与对偶函数

对偶函数 $g(\lambda, \nu) = \inf_x L(x, \lambda, \nu)$——它自动是凹的（逐点下确界保凹），无论原问题凸不凸。对偶问题的陈述：

弱对偶的用途：任何 $(\lambda, \nu)$ 都给原问题一个可计算的下界——非凸问题（如整数规划、组合优化）的对偶界正是分支定界与证书的核心。

强对偶与 KKT 条件

凸问题 + Slater 条件（存在严格可行点：不等式严格成立）⟹ 强对偶 $d^* = p^*$。KKT 条件（最优性的完整刻画）：

凸问题 + 强对偶时 KKT 是充要条件——求解、验证、解释三位一体。互补松弛的经济学读法：约束"紧"（起作用）的才有非零价格——影子价格理论。 解释性应用：最小二乘的水填充（通信功率分配：约束的影子价格 = 水位）、SVM 的对偶（支持向量 = 互补松弛的非零 $\alpha$ 点——几何与对偶的互证）、最大熵与 LP 对偶的等价。

老师的提醒

• 用对偶解题的标准动作：写 $L$ → inf 掉 $x$ 得 $g$ → 写对偶问题 → 检查 Slater → 用 KKT 反解原始最优。
• 灵敏度解释要记牢：乘子是"约束的价格"——预算加一元，收益多多少，对偶直接告诉你。

自检

• 写出对偶函数与弱对偶不等式。
• Slater 条件的内容与作用？
• 用互补松弛解释 SVM 的支持向量。

更深一层：对偶理论是"价格的经济学"

拉格朗日对偶的深层含义值得展开：乘子 $\lambda_i$ 是约束的影子价格——约束放松一单位，最优值变化 $\lambda_i$（灵敏度解释 $\partial p^*/\partial b_i$）。"价格是资源的边际价值"这个经济学解读让对偶从数学技巧变成决策语言：预算约束的乘子 = 预算的边际收益、产能约束的乘子 = 扩产的价值、时间约束的乘子 = 时间的价值。对偶变量不是数学副产品，是约束的经济定价——运筹学与经济学在对偶理论上握手。

弱对偶（任何 $(\lambda,\nu)$ 都给原问题一个下界——$d^* \le p^*$ 永远成立）的免费午餐：非凸问题（整数规划、组合优化）的对偶界正是分支定界与证书的核心。强对偶（凸 + Slater ⟹ $d^* = p^*$）与 KKT 条件（凸 + 强对偶时 KKT 是充要）构成最优性的完整刻画——求解、验证、解释三位一体。

推导细读：KKT 条件的"互补松弛"读法

KKT 条件的互补松弛 $\lambda_i f_i(x^*) = 0$ 的物理读法：约束"紧"（起作用）的才有非零价格——不紧的约束（$f_i < 0$）乘子必为零（"不约束的约束没有价格"）。这个性质是支持向量机的"支持向量只有边界点"的对偶解释——$\alpha_i > 0$ 的点就是间隔边界上的点。互补松弛 = 活跃约束识别——内点法的中心路径、SVM 的稀疏性、经济学的"自由处置"，全是这一条的应用。

在真实世界里：对偶的"应用地图"

对偶的应用地图：机器学习（SVM 的对偶形式让核技巧成为可能——原始问题没有核、对偶问题全是内积）、通信（水填充功率分配 = 对偶的解——约束的影子价格 = 水位）、经济学（影子价格 = 对偶变量）、计算几何（最近点对、最小包围球的对偶形式）。学会"把问题翻面看"——对偶的视角常常把"难解"变成"易解"，这是凸优化给所有优化工作者的最高级礼物。

专题深入：拉格朗日对偶的"完整解剖"完整版

第五章是全书理论皇冠，完整解剖一次：拉格朗日函数 $L(x, \lambda, \nu) = f_0(x) + \sum\lambda_if_i(x) + \sum\nu_ih_i(x)$ 的经济学读法（λ 是违反约束的影子价格——把"硬约束"变成"按价付费"，λ ≥ 0 保证惩罚方向正确）；对偶函数 $g(\lambda, \nu) = \inf_x L$——凹性免费获得（x 的逐点下确界）："不管原问题多非凸，对偶函数永远凹"——这是对偶的第一重魔力；弱对偶 $d^* \le p^*$ 无条件成立（对偶可行点给原问题下界——分支定界的下界来源、算法收敛性的证书来源）；强对偶（凸 + Slater：存在严格可行点 ⟹ $d^* = p^*$——"凸性 + 一点内点空间 = 对偶无缝"）；互补松弛（$\lambda_if_i(x^*) = 0$——"约束紧则价格正、价格零则约束松"：SVM 的支持向量（间隔紧 ⟹ α > 0）与自由样本（松 ⟹ α = 0）的定性分界**）。

推导细读：KKT 条件的"力学与经济学"完整版

KKT 条件的完整推导与语义：凸问题的 KKT 是充要的（非凸只必要——"KKT 求解凸问题 = 全局最优证书"是数值求解器的合法性文件）；四条件逐条翻译：平稳性 $\nabla f_0 + \sum\lambda_i\nabla f_i + \sum\nu_i\nabla h_i = 0$（"主动力平衡"：目标梯度被约束反力抵消——被压在墙上的球）；原始可行、对偶可行（λ ≥ 0）、互补松弛——物理读法（力平衡）+ 经济读法（影子价格 + 预算耗尽才付费）+ 算法读法（内点法的中心路径 $t f_i + \lambda_i = -1$ 把互补松弛推到极限）三条线合流。敏度分析的完整版（$p^*(u)$ 的斜率 = 对偶变量：$p^* \approx p^* - \lambda^*u$ 一阶展开——对偶变量是"约束松一寸，目标好几分"的汇率表：产能规划里 λ 直接给出"多一条产线值多少钱"）。对偶的算法身份（对偶分解、ADMM 的对偶上升——分布式优化把对偶变量当协调信号：电网分区的解耦调度）。

工程案例细节：对偶思想的产业出口工程版

第五章的工程出口：SVM 的对偶故事（对偶问题引入核技巧 + 支持向量的稀疏性 + KKT 分类样本——"一个对偶、三重收益"的典范）；网络流与通信（TCP 拥塞控制的对偶解释（丢包/时延是链路价格的信号——Kelly 的网络效用最大化把互联网写成分布式对偶求解）；跨层功率分配的注水（KKT 的显式解）；电力市场的影子价格（节点电价 LMP = 最优潮流的对偶变量——"电价就是 λ"：加州电力市场的定价机制；阻塞约束的价格直接给出电网投资的地理信号）；运筹学的对偶体系（LP 对偶的运输问题解释、整数规划的对偶界（分支定界/割平面的理论基础）；机器学习的对偶视角（核方法、对偶嵌入、GAN 的 minmax 博弈与生成-判别的对偶结构）；量化金融（期权定价的对偶界、风险预算的 KKT）。"对偶是把问题翻个面看"——正面是决策、反面是价格，翻过面的世界常常更好算。