拉格朗日对偶性

导言

拉格朗日对偶性常常用于带约束的最优化问题。这个原理的简化版本在高中数学中就出现过，当时称作拉格朗日乘数法。先回顾一下拉格朗日乘数法的基本形式：

\begin{aligned} \min_x \quad & f(x) \\ \text{s.t.} \quad & g(x) = 0 \end{aligned}

找到 $x$ 使得 $f(x)$ 最小，且满足 $g(x) = 0$ 。我们引入拉格朗日乘子构造新的函数：

L(x, \lambda) = f(x) + \lambda g(x)

接着令两个偏导数为 0：

\begin{cases} \dfrac{\partial L}{\partial x} = 0 \\[6pt] \dfrac{\partial L}{\partial \lambda} = 0 \end{cases}

求解出 $x$ 和 $\lambda$ 即可。

事实上，最后这一步求导然后令其等于 0 叫做 KKT（Karush-Kuhn-Tucker）条件，当然完整的版本更加复杂一些。在本文中依然不会证明 KKT 条件，所以想要了解这样做的依据是什么的小伙伴们可能要失望了。不过接下来，我将展开说明更为普适的拉格朗日对偶性。

拉格朗日对偶性

原始问题

\begin{aligned} \min_{x \in \mathbb{R}^n} \quad & f(x) \\ \text{s.t.} \quad & c_i(x) \leq 0, \quad i = 1, 2, \ldots, k \\ & h_j(x) = 0, \quad j = 1, 2, \ldots, l \end{aligned}

广义拉格朗日函数

L(x, \alpha, \beta) = f(x) + \sum_{i=1}^{k} \alpha_i c_i(x) + \sum_{j=1}^{l} \beta_j h_j(x)

$\alpha_i$ 和 $\beta_j$ 是拉格朗日乘子，规定 $\alpha_i \geq 0$ （为什么会这样规定，下面会解释）。

构造一个函数：

\theta_P(x) = \max_{\alpha, \beta:\, \alpha_i \geq 0} L(x, \alpha, \beta)

下标 $P$ 表示原始问题。

可以看出，如果 $x$ 违反原始问题的某个约束条件，即存在某个 $i$ 使得 $c_i(x) > 0$ 或者存在某个 $j$ 使得 $h_j(x) \neq 0$ ，那么就有：

\theta_P(x) = +\infty

因为存在 $c_i(x) > 0$ 的话，可令对应的 $\alpha_i \to +\infty$ （这里就说明了为什么规定 $\alpha_i \geq 0$ ，因为不作此规定的话，即使满足 $c_i(x) < 0$ 的条件，也可以取 $\alpha_i \to -\infty$ 从而让整个 $\theta_P = +\infty$ ）；存在 $h_j(x) \neq 0$ 的话，可令对应的 $\beta_j h_j(x) \to +\infty$ ，最后让其余所有 $\alpha_i, \beta_j$ 取 0。

如果满足所有约束，则 $\theta_P(x) = f(x)$ ，所以有：

\theta_P(x) = \begin{cases} f(x), & x \text{ 满足原始问题约束} \\ +\infty, & \text{其他} \end{cases}

与最初的原始问题等价的形式就是：

\min_x \theta_P(x) = \min_x \max_{\alpha, \beta:\, \alpha_i \geq 0} L(x, \alpha, \beta)

记：

p^* = \min_x \theta_P(x)

称为原始问题的值。

对偶问题

定义：

\theta_D(\alpha, \beta) = \min_x L(x, \alpha, \beta)

定义对偶问题的最优值：

d^* = \max_{\alpha, \beta:\, \alpha_i \geq 0} \theta_D(\alpha, \beta)

原始问题与对偶问题的关系

d^* \leq p^*

KKT 条件

\begin{aligned} \nabla_x L(x, \alpha, \beta) &= 0 \\ \nabla_\alpha L(x, \alpha, \beta) &= 0 \\ \nabla_\beta L(x, \alpha, \beta) &= 0 \\ \alpha_i c_i(x) &= 0, \quad i = 1, 2, \ldots, k \\ c_i(x) &\leq 0, \quad i = 1, 2, \ldots, k \\ \alpha_i &\geq 0, \quad i = 1, 2, \ldots, k \\ h_j(x) &= 0, \quad j = 1, 2, \ldots, l \end{aligned}

KKT 条件给出了求解的方法。其中，上面第 4 条式子称为 KKT 的对偶互补条件。由此条件可知：若 $\alpha_i > 0$ ，则 $c_i(x) = 0$ 。