Lagrange 对偶与对偶间隙

Lagrange 对偶把约束搬进目标，并用乘子为违反约束“定价”。它不仅能给下界，还能解释 KKT、分解算法和灵敏度。

从原问题到对偶函数

采用

$$\min_{x\in D}f(x),\qquad g_i(x)\ge0,\qquad h_j(x)=0.$$

定义

$$L(x,\mu,\lambda)=f(x)-\sum_i\mu_i g_i(x)+\sum_j\lambda_jh_j(x), \quad \mu\ge0.$$

对固定乘子，让 $x$ 自由选择：

$$q(\mu,\lambda)=\inf_{x\in D}L(x,\mu,\lambda).$$

这就是对偶函数。对偶问题为

$$\max_{\mu\ge0,\lambda}q(\mu,\lambda).$$

为什么给下界

若 $x$ 原可行，则 $g_i(x)\ge0,h_j(x)=0$，所以

$$L(x,\mu,\lambda)\le f(x).$$

再由下确界定义，$q(\mu,\lambda)\le L(x,\mu,\lambda)$，故

$$q(\mu,\lambda)\le f(x).$$

对偶最优值 $d^*$ 不超过原最优值 $p^*$，差

$$p^*-d^*\ge0$$

叫对偶间隙。

对偶函数总是凹

对固定 $x$，$L$ 关于 $(\mu,\lambda)$ 是仿射函数；一族仿射函数的逐点下确界是凹函数。因此即使原问题非凸，对偶问题仍是凹最大化问题。

算一个二次例子

$$\min_x\frac12x^2,\qquad x\ge1.$$

取 $\mu\ge0$：

$$L(x,\mu)=\frac12x^2-\mu(x-1).$$

对 $x$ 求极小，$x=\mu$，于是

$$q(\mu)=\mu-\frac12\mu^2.$$

最大化得 $\mu^*=1,q^*=1/2$，与原问题 $x^*=1,p^*=1/2$ 相等。

强对偶与 Slater 条件

凸规划中，若存在严格可行点满足所有不等式严格成立、等式成立，即 Slater 条件，则通常有

$$p^*=d^*,$$

且对偶最优乘子存在。此时 KKT 条件对最优性既必要又充分。

非凸问题一般只能保证弱对偶；即使原、对偶都可解，也可能有正间隙。

鞍点

若 $(x^*,\mu^*,\lambda^*)$ 满足

$$L(x^*,\mu,\lambda)\le L(x^*,\mu^*,\lambda^*)\le L(x,\mu^*,\lambda^*)$$

（对允许的乘子和 $x$），则它是 Lagrange 函数鞍点，意味着 $x^*$ 原最优、乘子对偶最优且零间隙。凸问题的 KKT 条件可理解为鞍点条件。

考试要点

• 对偶函数一定先对 $x$ 取 $\inf$，不能把“消去驻点”与“取到全局下确界”混为一谈。
• 若 $\inf_xL=-\infty$，该乘子仍定义了对偶函数值，只是对对偶最大化没帮助。
• 强对偶需要条件；不要从弱对偶直接跳到等号。
• 对偶函数的凹性与原问题是否凸无关。