拉格朗日对偶 · aiwiki.page

拉格朗日对偶是数学优化中的一个框架，它将称为原问题的约束优化问题与一个对偶问题联系起来；对偶问题的变量用于对原问题的约束赋予权重。对于最小化问题，对偶可行点给出原问题最优值的下界。在适当条件下，最好的下界等于原问题的最优值。这一框架将优化中的界、最优性条件和算法联系起来，也涵盖求解非凸问题的方法。(mit.edu)

原问题与对偶构造

考虑原问题

p^\star=\inf_{x\in D} f_0(x) \quad\text{满足约束}\quad f_i(x)\leq0,\quad h_j(x)=0,

其中 $i=1,\ldots,m$ ， $j=1,\ldots,r$ ， $D$ 是这些函数的公共定义域。目标函数为 $f_0$ ；约束决定了可行集。其拉格朗日函数为

L(x,\lambda,\nu) =f_0(x)+\sum_{i=1}^{m}\lambda_i f_i(x) +\sum_{j=1}^{r}\nu_j h_j(x).

拉格朗日乘子满足 $\lambda_i\geq0$ ，而等式约束的乘子 $\nu_j$ 不受符号限制。这些符号要求专门对应于写成 $f_i(x)\leq0$ 形式的不等式约束。(mit.edu)

对偶函数和对偶最优值分别为

g(\lambda,\nu)=\inf_{x\in D}L(x,\lambda,\nu), \qquad d^\star=\sup_{\lambda\geq0,\nu}g(\lambda,\nu).

内层最小化保留定义域 $D$ ，但去除了已纳入 $L$ 的约束。对偶函数可能取值为 $-\infty$ ，因此其有效定义域由使函数值有限的乘子选择构成。即使原问题是非凸的，对偶函数仍是凹函数，因为它是一族关于乘子的仿射函数的逐点下确界。因此，最大化对偶函数是一个凸优化问题，尽管计算其函数值仍可能很困难。(mit.edu)

弱对偶与界

对于任意原问题可行点 $x$ 以及满足 $\lambda\geq0$ 的乘子，

g(\lambda,\nu)\leq L(x,\lambda,\nu)\leq f_0(x).

第二个不等式成立，是因为等式约束项为零，而不等式约束项非正。对乘子取上确界，并对可行点取下确界，即可得到弱对偶：

d^\star\leq p^\star.

这一结论既不要求凸性，也不要求可微性。(mit.edu)

当最优值有限时， $p^\star-d^\star$ 称为对偶间隙。更具实用意义的是，原问题的一个可行点和一组对偶可行乘子给出

0\leq f_0(x)-p^\star \leq f_0(x)-g(\lambda,\nu).

因此，两者的目标值之差给出了该可行点偏离最优值程度的可验证上界。如果两者的目标值相等，就能证明它们都是最优解，而无须另行计算未知的最优值。(mit.edu)

强对偶与约束资格条件

强对偶是指 $d^\star=p^\star$ 。它并非自动成立，即使是凸问题，也不是每个问题都满足强对偶。对于凸优化，目标函数和不等式约束函数是凸函数，等式约束函数是仿射映射，定义域是凸集。称为约束资格条件的附加假设可以保证两个最优值相等。(stanford.edu)

一个重要的充分条件是斯莱特条件：公共定义域的相对内部中存在一个点，满足所有等式约束，并严格满足所有不等式约束。当原问题最优值有限时，这一条件还保证对偶最优值能够取到。更精细的版本不要求仿射不等式约束严格成立。强对偶本身涉及的是最优值，应将其与任一问题是否能取到最优值区分开来。(stanford.edu)

最优性条件与鞍点

对于定义在开集上的可微函数，卡鲁什—库恩—塔克条件包括原问题可行性、对偶可行性、互补松弛，

\lambda_i f_i(x)=0,

以及驻点条件，

\nabla f_0(x)+\sum_i\lambda_i\nabla f_i(x) +\sum_j\nu_j\nabla h_j(x)=0.

驻点条件要求拉格朗日函数关于原变量的梯度为零。互补松弛意味着，严格满足的不等式约束所对应的乘子为零。(stanford.edu)

对于凸问题，这些条件足以保证全局最优性；在满足斯莱特条件时，最优解也可以通过存在适当乘子使这些条件成立来刻画。更一般地，对偶间隙为零的原问题最优解和对偶最优解构成一个鞍点：

L(x^\star,\lambda,\nu) \leq L(x^\star,\lambda^\star,\nu^\star) \leq L(x,\lambda^\star,\nu^\star),

其中 $x,\lambda,\nu$ 取各自允许的值。(stanford.edu)

示例

对于约束为 $x\geq1$ 的问题 $\min x^2$ ，将约束写成 $1-x\leq0$ 。直接计算可得

L(x,\lambda)=x^2+\lambda(1-x), \qquad g(\lambda)=\lambda-\frac{\lambda^2}{4}.

关于 $x$ 的下确界在 $x=\lambda/2$ 处取得。在 $\lambda\geq0$ 上最大化，得到 $\lambda^\star=2$ 和 $d^\star=1$ ，与原问题的 $x^\star=1$ 和 $p^\star=1$ 相吻合。这个例子展示了二次问题的对偶构造，以及如何给出确切的最优性证明。(stanford.edu)

敏感性与计算

对偶乘子可用于敏感性分析。如果将不等式约束扰动为 $f_i(x)\leq u_i$ ，且在 $u=0$ 时强对偶成立，则最优乘子给出

p^\star(u)\geq p^\star(0)-(\lambda^\star)^Tu.

当最优值函数在零点可微时，其导数为 $-\lambda^\star$ 。因此，乘子衡量了放宽相应约束界限时最优值的边际敏感程度。(stanford.edu)

在对偶分解中，乘子将具有可分离目标函数和耦合约束的问题分解为若干较小的优化子问题。一个起协调作用的算法根据约束残差更新乘子。这种方法支持分布式计算，但在最优乘子下最小化拉格朗日函数，并不一定能得到原问题的可行点；恢复原问题的解可能需要额外步骤。(see.stanford.edu)