统计学习方法 拉格朗日对偶性

统计学习方法 拉格朗日对偶性

读李航的《统计学习方法》时，关于拉格朗日对偶性的笔记。

在许多统计学习的约束最优化问题中，例如最大熵模型和支持向量机，常常使用拉格朗日对偶性（Lagrange duality）将原始问题转换为对偶问题，通过求解对偶问题而得到原始问题的解。

原始问题

假设 $f(x)$ ，$c_i(x)$ 和 $h_j(x)$ 是定义在 ${\mathbb{R}}^n$ 上的连续可微函数，考虑约束最优化问题（记为 $P$ ）：
$$\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{\min }& f(x)\\ \text{s.t.}& c_i(x)\le 0,i=1,2,\cdots ,k\\ & h_j(x)=0,j=1,2,\cdots ,l\end{array}$$
它的 Lagrangian 为：
$$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\ge 0$ ；以下是一个关于 $x$ 的函数，下标 $P$ 代表原始问题：
$${\theta }_P(x)=\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )$$
可以得到该函数的性质：
$${\theta }_P(x)=\{\begin{array}{ll}f(x),& x\text{ 满足原始问题的约束}\\ +\infty ,& \text{else}\end{array}$$

• 如果 $x$ 不满足原始问题的约束，即存在某个 $i$ 使得 $c_i(x)>0$ 或者存在某个 $j$ 使得 $h_j(x)\ne 0$ ，那么就有：
  • 若存在某个 $i$ 使得 $c_i(x)>0$ ：我们令 ${\alpha }_i\to +\infty$ ，则 ${\theta }_P(\theta )\to +\infty$ ；
  • 若存在某个 $j$ 使得 $h_j(x)\ne 0$ ：我们令 ${\beta }_j$ 取和 $h_j(x)$ 相同的符号，并且令 $|{\beta }_j|\to +\infty$ ，即 ${\beta }_j{h}_j(x)\to +\infty$ ，则 ${\theta }_P(\theta )\to +\infty$ ；

$${\theta }_P(x)=\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }\left[f(x)+\sum _{i=1}^k{\alpha }_i{c}_i(x)+\sum _{j=1}^l{\beta }_j{h}_j(x)\right]=+\infty$$

• 若 $x$ 满足原始问题的约束，则 $\sum _{i=1}^k{\alpha }_i{c}_i(x)\le 0$ ，$\sum _{j=1}^l{\beta }_j{h}_j(x)=0$ ，因此：

$${\theta }_P(x)=f(x)$$

基于 ${\theta }_P(x)$ 的性质，我们考虑其极小化问题：
$$\underset{x}{\min }{\theta }_P(x)=\underset{x}{\min }\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )$$
它与原始问题 $P$ 是等价的（因为 $x$ 满足约束条件时，${\theta }_P(x)$ 和 $f(x)$ 是等价的）。以上这个问题称为广义拉格朗日函数的极小极大问题。我们定义原始问题的最优值：
$$p^{\ast }=\underset{x}{\min }{\theta }_P(x)$$
称为原始问题的值。

对偶问题

以下是一个关于 $\alpha$ 和 $\beta$ 的函数，下标 $D$ 代表对偶问题：
$${\theta }_D(\alpha ,\beta )=\underset{x}{\min }L(x,\alpha ,\beta )$$
再考虑 ${\theta }_D(\alpha ,\beta )$ 的极大化问题：
$$\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }\underset{x}{\min }L(x,\alpha ,\beta )$$
该问题称为广义拉格朗日函数的极大极小问题，其还可以表示为约束最优化问题：
$$\begin{array}{rl}\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }& {\theta }_D(\alpha ,\beta )=\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }\underset{x}{\min }L(x,\alpha ,\beta )\\ \text{s.t.}& {\alpha }_i\ge 0,i=1,2,\cdots ,k\end{array}$$
极大极小问题称为原始问题的对偶问题，定义对偶问题的最优值为：
$$d^{\ast }=\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )$$
称为对偶问题的值。

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

Th C.1：若原始问题和对偶问题都有最优值，则对偶问题的最优值小于等于原始问题的最优值：
$$d^{\ast }\le p^{\ast }$$
证明：由前面的定义得，对于任意的 $\alpha$ ，$\beta$ ，$x$ ，有：
$${\theta }_D(\alpha ,\beta )=\underset{x}{\min }L(x,\alpha ,\beta )\le L(x,\alpha ,\beta )\le \underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }L(x,\alpha ,\beta )={\theta }_P(x)$$
即：
$${\theta }_D(\alpha ,\beta )\le {\theta }_P(x)$$
即：
$$d^{\ast }=\underset{\alpha ,\beta ;{\alpha }_i\ge 0}{\max }{\theta }_D(\alpha ,\beta )\le \underset{x}{\min }{\theta }_P(x)=p^{\ast }$$
推论 C.1：设 $x^{\ast }$ 和 ${\alpha }^{\ast }$ ，${\beta }^{\ast }$ 分别是原始问题和最优问题的可行解（即满足约束条件），且 $d^{\ast }=p^{\ast }$ ，则 $x^{\ast }$ 和 ${\alpha }^{\ast }$ ，${\beta }^{\ast }$ 分别是原始问题和最优问题的最优解。

Th C.2：对于原始问题和对偶问题，假设：

• 函数 $f(x)$ 和 $c_i(x)$ 是凸函数，$h_j(x)$ 是仿射函数；
• 存在 $x$ ，对于任意 $i$ ，满足 $c_i(x)<0$ （即不等式约束 $c_i(x)$ 严格可行）；

则存在 $x^{\ast }$ ，${\alpha }^{\ast }$ ，${\beta }^{\ast }$ ，使得 $x^{\ast }$ 是原始问题的解，${\alpha }^{\ast }$ ，${\beta }^{\ast }$ 是对偶问题的解，并且：
$$p^{\ast }=d^{\ast }=L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })$$
Th C.3：跟 Th C.2 一样的假设下， $x^{\ast }$ 和 ${\alpha }^{\ast }$ ，${\beta }^{\ast }$ 分别是原始问题和最优问题的可行解的充分必要条件是： $x^{\ast }$ ，${\alpha }^{\ast }$ ，${\beta }^{\ast }$ 满足 KKT 条件：
$$\begin{array}{c}{\nabla }_{x}L(x^{\ast },{\alpha }^{\ast },{\beta }^{\ast })=0\\ {\alpha }_i^{\ast }{c}_i(x^{\ast })=0,i=1,2,\cdots ,k\\ c_i(x^{\ast })\le 0,i=1,2,\cdots ,k\\ {\alpha }_i^{\ast }\ge 0,i=1,2,\cdots ,k\\ h_j(x^{\ast })=0,j=1,2,\cdots ,k\end{array}$$
其中 ${\alpha }_i^{\ast }{c}_i(x^{\ast })=0,i=1,2,\cdots ,k$ 称为 KKT 的对偶互补条件。由此可知，若 ${\alpha }_i>0$ ，则 $c_i(x^{\ast })=0$ ；