Lagrange 对偶问题

定义

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

$$ \begin{aligned} \mathrm{maximize} \quad & g(\lambda, \nu) \\ \mathrm{subject\ to} \quad & \lambda \succeq 0 \end{aligned} $$

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

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

显式表达对偶约束

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

$$ \begin{aligned} \mathrm{minimize} \quad & c^Tx \\ \mathrm{subject\ to} \quad & Ax = b \\ \quad & x \succeq 0 \end{aligned} $$

其 Lagrange 对偶函数为

$$ g(\lambda, \nu) = \left\{ \begin{matrix} -b^T \nu & A^T \nu - \lambda + c = 0 \\ -\infty & \text{其他情况} \end{matrix} \right. $$

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

$$ \begin{aligned} \mathrm{maximize} \quad & g(\lambda, \nu) \\ \mathrm{subject\ to} \quad & \lambda \succeq 0 \end{aligned} $$

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

$$ \begin{aligned} \mathrm{maximize} \quad & -b^T \nu \\ \mathrm{subject\ to} \quad & A^T \nu - \lambda + c = 0 \\ \quad & \lambda \succeq 0 \end{aligned} $$

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

$$ \begin{aligned} \mathrm{maximize} \quad & -b^T \nu \\ \mathrm{subject\ to} \quad & A^T \nu + c \succeq 0 \\ \end{aligned} $$

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

弱对偶性

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

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

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

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

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

强对偶性和 Slater 约束准则

如果对偶间隙为零,即

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

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

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

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

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

举例

线性方程组的最小二乘解

再次考虑问题

$$ \begin{aligned} \mathrm{minimize} \quad & x^Tx \\ \mathrm{subject\ to} \quad & Ax = b \end{aligned} $$

其相应的对偶问题为

$$ \mathrm{maximize} \quad -\frac{1}{4} \nu^T AA^T \nu - b^T \nu $$

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

线性规划的 Lagrange 对偶

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

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

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

Previous
Next