Lagrange 对偶问题

定义

Lagrange 对偶函数实际上给出了优化问题最优值的下界。也就是说，对于一对给定的 $\lambda$ 和 $\nu$，就有一个确定的下界值相对应。那么，一个自然的问题是：Lagrange 对偶函数的最优下界是什么？即如下的一个优化问题

$$\begin{array}{rl}\mathrm{maximize}& g(\lambda ,\nu )\\ \mathrm{subject}\mathrm{to}& \lambda ⪰0\end{array}$$

该问题被称为 Lagrange 对偶问题。称解 $({\lambda }^{\star },{\nu }^{\star })$ 为对偶最优解或者最优 Lagrange 乘子。

Lagrange 对偶问题是一个凸优化问题，这是因为极大化的目标函数是凹函数，且约束集合是凸集。因此，对偶问题的凸性和原问题是否是凸优化问题无关。

显式表达对偶约束

下面我们以标准形式线性规划的 Lagrange 对偶为例，说明如何显式表达对偶约束。

$$\begin{array}{rl}\mathrm{minimize}& c^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& Ax=b\\ & x⪰0\end{array}$$

其 Lagrange 对偶函数为

$$g(\lambda ,\nu )=\{\begin{array}{cc}-b^{\mathrm{\top }}\nu & A^{\mathrm{\top }}\nu -\lambda +c=0\\ -\mathrm{\infty }& \text{其他情况}\end{array}$$

严格来讲,标准形式线性规划的对偶问题是在满足约束 $\lambda ⪰0$ 的条件下极大化对偶函数

$$\begin{array}{rl}\mathrm{maximize}& g(\lambda ,\nu )\\ \mathrm{subject}\mathrm{to}& \lambda ⪰0\end{array}$$

当且仅当 $A^{\mathrm{\top }}\nu -\lambda +c=0$ 时对偶函数 $g$ 有界。我们看看可以通过将此“隐含”的等式约束“显式”化来得到一个等价的问题

$$\begin{array}{rl}\mathrm{maximize}& -b^{\mathrm{\top }}\nu \\ \mathrm{subject}\mathrm{to}& A^{\mathrm{\top }}\nu -\lambda +c=0\\ & \lambda ⪰0\end{array}$$

进一步地，这个问题可以描述为

$$\begin{array}{rl}\mathrm{maximize}& -b^{\mathrm{\top }}\nu \\ \mathrm{subject}\mathrm{to}& A^{\mathrm{\top }}\nu +c⪰0\end{array}$$

这是一个不等式形式的线性规划。

弱对偶性

Lagrange 对偶问题的最优值用 $d^{\star }$ 表示，这是通过 Lagrange 函数得到的原问题最优值 $p^{\star }$ 的最好下界。特别地，我们有下面虽然简单但是非常重要的不等式

$$d^{\star }⩽p^{\star }$$

即使原问题不是凸问题，上述表达式亦成立。这个性质称为弱对偶性。

定义差值 $p^{\star }-d^{\star }$ 是原问题的最优对偶间隙。

当原问题很难求解时，弱对偶不等式可以给出原问题最优值的一个下界，这是因为对偶问题总是凸问题，而且在很多情况下都可以进行有效的求解得到 $d^{\star }$。

强对偶性和 Slater 约束准则

如果对偶间隙为零，即

$$p^{\star }=d^{\star }$$

那么强对偶性成立。这说明从 Lagrange 对偶函数得到的最好下界是紧的。

如果原问题是凸优化问题，那么强对偶性通常（但不总是）成立。这意味着还需要满足一些额外条件，这些条件被称为约束准则。一个简单的约束准则是 Slater 条件：存在一点 $x\in \mathrm{relint}\mathcal{D}$ 使得

$$f_i(x)<0,i=1,\cdots ,m,Ax=b$$

满足上述条件的点被称为严格可行，这是因为不等式约束严格成立。Slater 定理说明，当 Slater 条件成立（且原问题是凸问题）时，强对偶性成立。

举例

线性方程组的最小二乘解

再次考虑问题

$$\begin{array}{rl}\mathrm{minimize}& x^{\mathrm{\top }}x\\ \mathrm{subject}\mathrm{to}& Ax=b\end{array}$$

其相应的对偶问题为

$$\mathrm{maximize}-{\displaystyle \frac{1}{4}}{\nu }^{\mathrm{\top }}A{A}^{\mathrm{\top }}\nu -b^{\mathrm{\top }}\nu$$

它是一个凹二次函数的无约束极大化问题。Slater 条件此时即是原问题的可行性条件。

线性规划的 Lagrange 对偶

对于任意线性规划问题，只要原问题可行，强对偶性都成立。

二次约束二次规划的 Lagrange 对偶

考虑 QCQP，根据 Slater 条件，当二次不等式约束严格成立时，则强对偶成立。