[ML Notes] 拉格朗日函数:对偶性

1. 原始问题

  假设 $f(\boldsymbol{x})$、$g_i(\boldsymbol{x})$、$h_i(\boldsymbol{x})$ 式定义在 $\mathbb{R}^n$ 上的连续可微函数,对于约束最优化问题

$$
\begin{aligned}
\min_\boldsymbol{x \in \mathbb{R}^n} \; & f(\boldsymbol{x}) \\
\text{s.t.} \; & g_i(\boldsymbol{x}) \leq 0, \quad i = 1, 2, \dots, k & \qquad (i) \\
& h_j(\boldsymbol{x}) = 0, \quad j = 1, 2, \dots, l & \qquad (ii)
\end{aligned} \tag{1}
$$

将上述形式称为原始最优化问题。

2. 广义拉格朗日函数

  广义拉格朗日函数(generalized Lagrange function)定义为

$$
L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = f(\boldsymbol{x}) + \sum_{i=1}^k \alpha_i g_i(\boldsymbol{x}) + \sum_{j=1}^l \beta_j h_j(\boldsymbol{x}) \tag{2}
$$

其中 $\boldsymbol{x} \in \mathbb{R}^n$,$\alpha_i$、$\beta_j$ 称为拉格格朗日乘子,$\alpha_i \geq 0$。

  考虑 $\boldsymbol{x}$ 的函数

$$
\theta_P(\boldsymbol{x}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} \; L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{3}
$$

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

  假设给定某个 $\boldsymbol{x}$,如果 $\boldsymbol{x}$ 违反原始问题的约束条件,即

  • 存在某个 $i$ 使得 $g_i(\boldsymbol{x}) > 0$,如果此时令 $\alpha_i \rightarrow +\infty$,而其余各 $\alpha_i$、$\beta_j$ 均取 $0$,
  • 或者存在某个 $j$ 使得 $h_j(\boldsymbol{x}) \neq 0$,如果此时令 $\beta_j$ 使 $\beta_j h_j(\boldsymbol{x}) \rightarrow +\infty$,而其余各 $\alpha_i$、$\beta_j$ 均取 $0$,

则有

$$
\theta_P(\boldsymbol{x}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} \; \bigg( f(\boldsymbol{x}) + \sum_{i=1}^k \alpha_i g_i(\boldsymbol{x}) + \sum_{j=1}^l \beta_j h_j(\boldsymbol{x}) \bigg) = +\infty
$$

  反之,如果 $\boldsymbol{x}$ 满足原始问题的约束条件,由式 $(2)$、$(3)$ 可知,此时有

$$
\theta_P(\boldsymbol{x}) = f(\boldsymbol{x})
$$

  综上有

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

考虑极小化问题

$$
\min_{\boldsymbol{x}} \theta_P(\boldsymbol{x}) = \min_{\boldsymbol{x}} \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{5}
$$

式 $(5)$ 称为广义拉格朗日函数的极小极大问题,它与式 $(1)$ 所示的原始问题式等价的,有相同的解。

  由此就将原始问题表示为了广义拉格朗日函数的极小极大问题,定义原始问题的最优解

$$
p^* = \min_{\boldsymbol{x}} \theta_P(\boldsymbol{x}) \tag{6}
$$

称为原始问题的值。

3. 对偶问题

  定义

$$
\theta_D(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \min_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{7}
$$

再考虑极大化 $\theta_D(\boldsymbol{\alpha}, \boldsymbol{\beta})$,即

$$
\max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} \theta_D(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} \min_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \tag{8}
$$

上述问题称为广义拉格朗日函数的极大极小问题。

  可以将广义拉格朗日函数的极大极小问题表示为约束最优化问题

$$
\begin{aligned}
\max_{\boldsymbol{\alpha}, \boldsymbol{\beta}} \; & \theta_D(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}} \min_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \\
\text{s.t.} \; & \alpha_i \geq 0, \quad i = 1, 2, \dots, k
\end{aligned} \tag{9}
$$

称为原始问题的对偶问题。定义对偶问题的最优值

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

称为对偶问题的值。

4. 原始问题和对偶问题的关系

  定理 1 若原始问题和对偶问题都有最优值,则

$$
d^* = \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} \min_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) \leq \min_{\boldsymbol{x}} \max_{\boldsymbol{\alpha}, \boldsymbol{\beta}: \alpha_i \geq 0} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta}) = p^*
$$

  推论 1 设 $\boldsymbol{x}^*$ 和 $\boldsymbol{\alpha}^*$、$\boldsymbol{\beta}^*$ 分别是原始问题 $(1)$ 和对偶问题 $(9)$ 的可行解,并且 $d^* = p^*$,$\boldsymbol{x}^*$ 和 $\boldsymbol{\alpha}^*$、$\boldsymbol{\beta}^*$ 分别是原始问题和对偶问题的最优解。

  推论 1 表明,在某些条件下,原始问题和对偶问题的最优值相等,即 $d^* = p^*$,这时可以用解对偶问题替代解原始问题。

  定理 2 对原始问题 $(1)$ 和对偶问题 $(9)$,假设函数 $f(\boldsymbol{x})$ 和 $g_i(\boldsymbol{x})$ 是凸函数,$h_j(\boldsymbol{x})$ 是仿射函数;并且假设不等式约束 $g_i(\boldsymbol{x})$ 是严格可行的,即存在 $\boldsymbol{x}$ 对所有 $i$ 有 $g_i(\boldsymbol{x}) < 0$,则存在 $\boldsymbol{x}^*$、 $\boldsymbol{\alpha}^*$、$\boldsymbol{\beta}^*$ 使 $\boldsymbol{x}^*$ 是原问题的解,$\boldsymbol{\alpha}^*$、$\boldsymbol{\beta}^*$ 是对偶问题的解,并且

$$
p^* = d^* = L(\boldsymbol{x}^*,\boldsymbol{\alpha}^*,\boldsymbol{\beta}^*)
$$

  定理 3 对原始问题 $(1)$ 和对偶问题 $(9)$,假设函数 $f(\boldsymbol{x})$ 和 $g_i(\boldsymbol{x})$ 是凸函数,$h_j(\boldsymbol{x})$ 是仿射函数;并且假设不等式约束 $g_i(\boldsymbol{x})$ 是严格可行的,则 $\boldsymbol{x}^*$ 和 $\boldsymbol{\alpha}^*$、$\boldsymbol{\beta}^*$ 分别是原始问题和对偶问题的解的充分必要条件是 $\boldsymbol{x}^*$、$\boldsymbol{\alpha}^*$、$\boldsymbol{\beta}^*$ 满足下面的条件

$$
\begin{aligned}
\begin{cases}
\nabla_{\boldsymbol{x}} L(\boldsymbol{x}^*, \boldsymbol{\alpha}^*, \boldsymbol{\beta}^*) = 0 \qquad & (i) \\
\alpha_i^* g_i(\boldsymbol{x}^*) = 0, \quad i = 1, 2, \dots, k \qquad & (ii) \\
g_i(\boldsymbol{x}^*) \leq 0, \quad i = 1, 2, \dots, k \qquad & (iii) \\
\alpha_i^* \geq 0, \quad i = 1, 2, \dots, k \qquad & (iv) \\
h_j(\boldsymbol{x}^*) = 0, \quad j = 1, 2, \dots, l \qquad & (v) \\
\end{cases}
\end{aligned} \tag{11}
$$

上述条件称为 KKT(Karush-Kuhn-Tucker)条件。其中:

  • 条件 $(i)$ 表示求解式 $(7)$,即 $\theta_D(\boldsymbol{\alpha}, \boldsymbol{\beta}) = \min_{\boldsymbol{x}} L(\boldsymbol{x}, \boldsymbol{\alpha}, \boldsymbol{\beta})$;
  • 条件 $(ii)$ 称为 KKT 的对偶互补条件,由该条件可知,若 $\alpha_i^* > 0$,则 $g_i(\boldsymbol{x}^*) = 0$;
  • 条件 $(iii)$、$(v)$ 为原始问题的约束;
  • 条件 $(iv)$ 为构造广义拉格朗日函数(式 $(2)$)时的定义。