拉格朗日对偶

乘子为约束分配权重。在可行点处，$f_i(x)\le 0$、${\lambda }_i\ge 0$ 且 $h_j(x)=0$，所以 $L(x,\lambda ,\nu )\le f_0(x)$；再对 $x$ 取下确界，就得到原目标值的下界。对偶问题调整这些权重，寻找尽可能高的下界。

$g$ 总是凹函数，因为它是关于 $(\lambda ,\nu )$ 的一族仿射函数的逐点下确界。这一性质与弱对偶一样，也适用于非凸原问题。

最优乘子还描述约束扰动的代价。在强对偶成立且最优值对约束右端可微时，将 $f_i(x)\le 0$ 放松为 $f_i(x)\le u_i$，最优值对 $u_i$ 的导数为 $-{\lambda }_i^{\ast }$。因此 ${\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$ 上凸，却始终非负，因而没有严格可行点。拉格朗日函数通过增大 $y$ 使约束罚项任意小，得到的下界与原可行集上固定的目标值之间留下了间隙。

经典 Lagrange 乘子法公理库拉格朗日乘子法Lagrange multiplier method约束极值处目标梯度位于约束梯度张成空间中的必要条件。通过驻点方程寻找光滑约束下的局部极值候选；对偶函数则通过对整个定义域取下确界，建立全局下界。两种方法都使用乘子，分别把它用于局部微分条件与全局比较。

Fenchel 对偶与原对偶单调包含公理库Fenchel 对偶与原对偶单调包含Fenchel duality · Primal-dual monotone inclusion从复合凸问题的相对内部资格推出对偶乘子，以两份 Fenchel 等号认证最优，再构造极大单调系统并手算完整预解轨道。处理扩展实值的复合模型 $f(x)+g(Ax)$：通过 $\mathrm{ri}\mathrm{dom}g\cap A(\mathrm{ri}\mathrm{dom}f)\ne \varnothing$ 的资格条件建立对偶可达性，再以两份共轭等号给出证书。它把不等式形式的 Slater 条件接到定义域几何，并继续证明原对偶隐式系统的有限维收敛；原问题的最优点存在仍单独核对。

Fisher 市场均衡与 Eisenberg–Gale 规划公理库Fisher 市场均衡与 Eisenberg–Gale 规划Linear Fisher market · Eisenberg–Gale convex program · Fisher 市场均衡用加权对数效用的凸规划刻画线性 Fisher 市场均衡，证明最优分配与价格乘子的双向对应，并计算需要拆分商品的均衡。给资源影子价格一个具体的市场含义：最大化预算加权的对数效用时，供给约束的最优乘子正是支持均衡分配的商品价格。KKT 条件进一步证明每个买家在这些价格下花完预算并取得个人最大效用，从而把集中式凸优化与分散的最优购买行为连接起来。

锥规划的对偶与证书公理库锥规划的对偶与证书Conic programming certificates · Conic duality用对偶锥统一最优性与不可行性证书，并以二阶半正定规划区分零间隙、最优值可达和弱不可行。把非负乘子推广到对偶锥，并用二阶半正定例子说明：零间隙未必伴随对偶最优值可达，不可行也未必存在普通的严格分离证书。

给定原始可行点 $x$ 和对偶可行点 $(\lambda ,\nu )$，弱对偶立即给出

右侧是可计算的最优性误差上界，可用于分支定界和求解器停止。强对偶进一步说明：当原、对偶点都逼近最优时，上下界能够贴合。

Lasso 的最优性与对偶间隙公理库Lasso 的最优性与对偶间隙Lasso optimality conditions · Lasso duality gap · Lasso primal-dual certificate从残差相关性核验 Lasso 的零与非零坐标，并用可行对偶值认证剩余优化误差。先把残差公理库残差、误差估计与停止准则Residual and error estimation · Stopping criterion区分可计算残差与未知真误差，并说明把缺陷转成误差界和停止证书所需的条件。缩放到 $\Vert A^T\theta {\Vert }_{\mathrm{\infty }}\le \lambda$，再由 $D(\theta )=b^T\theta -\Vert \theta {\Vert }^2/2$ 计算下界。缩放让残差信息成为对偶可行点，原始目标值与该下界之差便能用于判断剩余优化误差。

在结构层面，线性规划对偶公理库线性规划对偶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$ 在凸性、约束资格及最优解存在等条件下，可通过最优乘子转成正则化 ERM公理库正则化经验风险最小化regularized ERM · RERM在经验拟合项上加入结构惩罚，以显式控制解的复杂度与统计—优化权衡。的惩罚项 $\lambda \mathrm{\Omega }(h)$。半径与乘子可以呈多对一关系，例如一段半径范围内约束都不活跃时，对应乘子均为零。FTRL公理库Follow-the-Regularized-LeaderFTRL · 正则化跟随领先者在历史累计损失上加入强凸正则器，以稳定下一轮决策并控制 regret。则在累计历史损失上加入正则器，用它控制相邻轮次决策的变化，再由在线学习分析得到遗憾界。

在输运对偶公理库Kantorovich 对偶性Kantorovich duality用满足两侧势之和不超过成本的对偶函数，构造可核验的输运最优性证书。中，为两组边缘约束引入势函数后，非负计划的下确界迫使势和不超过路线成本。有限线性规划或紧连续输运条件负责保证无对偶间隙，形式上的乘子推导本身只给弱对偶。