[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)$）时的定义。