拉格朗日对偶

把硬约束换成价格。乘子 ${\lambda }_i$ 是对"违反第 $i$ 条不等式"的单位罚金：在任何可行点处 $f_i(x)\le 0$、$h_j(x)=0$，罚项之和非正，于是 $L(x,\lambda ,\nu )\le f_0(x)$；对 $x$ 取下确界只会更小，弱对偶一步即得。这解释了对偶函数的角色：每组合法价格都给出原最优值的一份"下界证书"，无须解出原问题就能核验。对偶问题不过是在所有证书中挑最紧的那张。这个视角也说明 $\lambda \ge 0$ 为何必不可少：若允许 ${\lambda }_i<0$，严格满足 $f_i(x)<0$ 的可行点反而被奖励，$L$ 可能超过 $f_0$，证书随即作废。经济学解读同样贴切：${\lambda }_i^{\ast }$ 是第 $i$ 项资源的影子价格——把约束右端放松一个单位，最优成本一阶意义下约下降 ${\lambda }_i^{\ast }$。

一个能算到底的例子：$min{x}^2$ 受约束 $x\ge 1$，即 $f_1(x)=1-x\le 0$，显然 $p^{\ast }=1$。Lagrange 函数 $L(x,\lambda )=x^2+\lambda (1-x)$ 关于 $x$ 在 $x=\lambda /2$ 处取最小，得

在 ${\lambda }^{\ast }=2$ 处最大化，$d^{\ast }=g(2)=1=p^{\ast }$：强对偶成立（$x=2$ 严格可行，Slater 条件满足），且 $x^{\ast }={\lambda }^{\ast }/2=1$ 与互补松弛 ${\lambda }^{\ast }(1-x^{\ast })=0$ 相符。线性情形会导出线性规划对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。：标准形 $min\{c^{\mathrm{\top }}x:Ax=b,x\ge 0\}$ 的对偶是 $max\{b^{\mathrm{\top }}\nu :A^{\mathrm{\top }}\nu \le c\}$，只要一方可行且最优值有限，两侧最优值就相等。

强对偶不是"只要凸就自动成立"。经典反例：在定义域 $\{(x,y):y>0\}$ 上求 $min{e}^{-x}$ 受约束 $x^2/y\le 0$。可行性迫使 $x=0$，故 $p^{\ast }=1$；而对任意 $\lambda \ge 0$，固定 $x$ 令 $y\to \mathrm{\infty }$ 可让罚项消失，再令 $x\to +\mathrm{\infty }$ 得 $g(\lambda )=0$，于是 $d^{\ast }=0$，对偶间隙为 $1$。这个问题完全是凸的（$x^2/y$ 在 $y>0$ 上凸），坏在 Slater 条件失效：没有任何点能使 $x^2/y$ 严格小于零。一般地，约束资格失效的凸问题可能出现正对偶间隙，也可能 $d^{\ast }=p^{\ast }$ 但对偶最优不可达。非凸问题则连"通常成立"都谈不上，但弱对偶永远在场；同样无条件成立的还有 $g$ 的凹性——它是关于 $(\lambda ,\nu )$ 的一族仿射函数的逐点下确界，即使原问题非凸也凹。

还应与经典的 Lagrange 乘子法公理库拉格朗日乘子法Lagrange multiplier method约束极值处目标梯度位于约束梯度张成空间中的必要条件。区分：乘子法给出光滑等式约束问题局部极值点的必要条件，而对偶理论面向带不等式约束的（尤其凸的）全局最优，产出的是下界与全局最优性证书。两者共享"乘子"这一角色，回答的却是不同的问题。

对偶的第一用途是证书与界：任何对偶可行点都为 $p^{\ast }$ 提供可核验的下界，配合任一原始可行点给出的上界即可界定最优性差距，这是分支定界与大规模求解器停机判据的基础，也是 Lagrange 松弛为组合优化问题提供下界的原理。只有在原始与对偶可行性都达到所声明标准时，计算出的 duality gap 才是这项后验界；单独一个小的方程残差公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。不能替代可行性检查或强对偶假设。

在结构层面，线性规划对偶公理库线性规划对偶Linear programming duality · LP duality从线性约束生成对偶界，并以弱对偶、强对偶和互补松弛连接两侧最优解。把若干组合极小极大定理纳入同一框架：最大流最小割定理公理库最大流最小割定理Max-flow min-cut theorem网络最大流值等于源汇最小割容量。与二部图中的 König 定理公理库Kőnig 二分图定理Kőnig's theorem for bipartite graphs二分图中最大匹配大小等于最小顶点覆盖大小。都可视为特定线性规划及其对偶最优值相等的实例；原始—对偶方法公理库原始—对偶方法Primal-dual method同时维护原问题与对偶问题的可行性和互补条件以构造解的算法框架。直接使用 LP 的可行性、弱对偶与互补松弛来设计精确或近似算法，不必先经过一般凸问题的拉格朗日函数。在连续优化中，对偶分解把耦合约束价格化，将大问题拆成可并行的子问题；支持向量机等模型的标准求解路径正是转入对偶问题后在乘子空间中进行。

学习中的范数约束 $\mathrm{\Omega }(h)\le r$ 在适当凸性和约束资格下可由乘子 $\lambda$ 转成正则化 ERM公理库正则化经验风险最小化regularized ERM · RERM在经验拟合项上加入结构惩罚，以显式控制解的复杂度与统计—优化权衡。的惩罚形式，但并非每个半径都与某个 $\lambda$ 一一对应。FTRL公理库Follow-the-Regularized-LeaderFTRL · 正则化跟随领先者在历史累计损失上加入强凸正则器，以稳定下一轮决策并控制 regret。也把正则器加入累计历史损失，不过它的作用是稳定序贯决策；那一 regret 结论还需强凸性等条件，不是 Lagrange 对偶本身的直接推论。