等价的对偶问题

本小节的例子将说明，对一个问题进行简单的等价变形有可能得到非常不一样的对偶问题。

引入新的变量以及相应的等式约束

minimize f_{0} (A x + b)

该问题的 Lagrange 对偶函数是常数 $p^{⋆}$ 。即使强对偶性成立，但其 Lagrange 对偶问题没有什么意义和用途。

现在我们对原问题作等价变形

\begin{aligned} minimize & f_{0} (y) \\ subject to & A x + b = y \end{aligned}

我们引入了新的变量 $y$ ，并且增加了新的等式约束，将原来作为目标函数的复合函数拆开了。这样，变换之后的问题的 Lagrange 函数为

L (x, y, ν) = f_{0} (y) + ν^{⊤} (A x + b - y)

求解 Lagrange 对偶函数

g (ν) = b^{⊤} ν + inf_{y} (f_{0} (y) - ν^{⊤} y) = b^{⊤} - f_{0}^{⋆} (ν)

于是对偶问题可以描述为

\begin{aligned} minimize & b^{⊤} ν - f_{0}^{⋆} (ν) \\ subject to & A^{⊤} ν = 0 \end{aligned}

显然，变换后的问题的对偶问题要比原问题的对偶问题更有意义。

引入新的等式约束的思想同样可以用在约束函数上面。例如，考虑问题

\begin{aligned} minimize & f_{0} (A_{0} x + b_{0}) \\ subject to & f_{i} (A_{i} x + b_{i}) ⩽ 0, i = 1, \dots, m \end{aligned}

其中 $A_{i} \in R^{k_{i} \times n}$ ，函数 $f_{i} : R^{k_{i}} \to R$ 是凸函数。对 $i = 0, \dots, m$ ，引入新的变量 $y_{i} \in R^{k_{i}}$ ，将原问题重新描述为

\begin{aligned} minimize & f_{0} (y_{0}) \\ subject to & f_{i} (y_{i}) ⩽ 0, i = 1, \dots, m \\ A_{i} x + b_{i} = y_{i}, i = 0, \dots, m \end{aligned}

后面的步骤与之前类似，同样也是求解 Lagrange 对偶函数，并描述对偶问题。

如果我们将目标函数 $f_{0}$ 替换为 $f_{0}$ 的增函数，得到的问题与原问题显然是等价的。但是，等价问题的对偶问题可能和原问题的对偶问题大不相同。

考虑最小范数问题

minimize ∥ A x - b ∥

我们将问题重新描述为

\begin{aligned} minimize & \frac{1}{2} ∥ y ∥^{2} \\ subject to & A x - b = y \end{aligned}

接下来考虑一个简单的重新描述问题的方式，通过修改目标函数将约束包含到目标函数中，当约束被违背时，目标函数为无穷大。

考虑下列具有框约束的线性规划问题

\begin{aligned} minimize & c^{⊤} x \\ subject to & A x = b \\ l ⪯ x ⪯ u \end{aligned}

原问题的对偶问题很容易就能够得到，但是特别复杂。我们换一种做法，将原问题重新描述为

\begin{aligned} minimize & f_{0} (x) \\ subject to & A x = b \end{aligned}

其中 $f_{0} (x)$ 定义为

f_{0} (x) = {\begin{matrix} c^{⊤} x & l ⪯ x ⪯ u \\ \infty & otherwise \end{matrix}

这样一来新问题的对偶问题则是一个更为简单的无约束问题。