拉格朗日对偶性

拉格朗日对偶性 - Lagrange Duality

1. 原始问题

假设$ f(x),c_i(x),h_j(x) $是定义在$R^n$上的连续可微函数，考虑约束最优化问题

$\mathop{\min}_{x \in R^n} f(x)$ $s.t. c_i(x) \leq 0, \quad i=1,2,...,k$ $\quad \quad h_j(x) = 0, \quad j=1,2,...,k$

称此约束最优化问题为原始最优化问题或原始问题。

引入广义拉格朗日函数

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

这里，$x=(x^{(1)}, x^{(2)}, …, x^{(n)})^T \in R^n, \alpha_i, \beta_j$是拉格朗日乘子，$ \alpha_i \geq 0 $, [不要求$ \beta_j \geq 0 $，详细可以看这里]。考虑$x$的函数：

$\theta_P(x) = \mathop{\max}_{\alpha, \beta: \alpha_i \geq 0} L(x, \alpha, \beta)$

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

当有约束条件不满足时，可以调整该约束条件的拉格朗日乘子，可以使得$ \theta_P(x)=+\infty $,只有当所有的约束条件全都满足时，则可知$\theta_P(x) = f(x)$。所以，

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

所以，如果考虑极小化问题

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

该问题与原始最优化问题$式(1) \sim 式(3)$等价，即它们具有相同解。问题$ \mathop{\min}_x \theta_P(x) = \mathop{\min_x\max_{\alpha, \beta: \alpha_i \geq 0}} L(x, \alpha, \beta) $ 称为广义拉格朗日函数的极小极大问题，这样，原始最优化问题表示为广义拉格朗日函数的极小极大问题。

定义原始问题的最优值：

$p^{\ast} = \mathop{\min_x} \theta_P(x)$

称为原始问题的值。

2. 对偶问题

定义

$\theta_D(\alpha, \beta) = \mathop{\min_x} L(x, \alpha, \beta)$

再考虑极大化

$\mathop{\max_{\alpha,\beta:\alpha_i \geq 0}} \theta\_D(\alpha, \beta) = \mathop{\max\_{\alpha,\beta:\alpha\_i \geq 0} \min\_x} L(x,\alpha, \beta)$

问题$ \mathop{\max}_{\alpha,\beta:\alpha_i \geq 0} \mathop{\min_x} L(x,\alpha, \beta) $称为广义拉格朗日函数的极大极小问题。

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

$\mathop{\max_{\alpha, \beta}} \theta_D(\alpha, \beta) = \mathop{\max_{\alpha, \beta} \min_x} L(x, \alpha, \beta)$ $s.t. \quad \alpha_i \geq 0, \quad i=1,2,...,k$

称为原始问题的对偶问题。

定义对偶问题的最优解：

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

称为对偶问题的值。

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

3.1 定理 1

若原始问题和对偶问题都有最优值，则

$d^{\ast} = \mathop{\max_{\alpha,\beta:\alpha_i \geq 0} \min_x}L(x,\alpha, \beta) \leq \mathop{\min_x \max_{\alpha,\beta:\alpha_i \geq 0}} L(x, \alpha, \beta) = p^{\ast}$

3.2 定理 2

考虑原始问题$式(1) \sim 式(3)$和对偶问题$式(11) \sim 式(12)$，假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数[最高次数为1的多项式函数,常数项为零的仿射函数称为线性函数]；并且假设不等式约束$c_i(x)$是严格可行的，即存在$x$，对所有$i$有$c_i(x)<0$，则存在$ x^{\ast}, \alpha^{\ast}, \beta^{\ast} $，使$x^{\ast}$是原始问题的解，$ \alpha^{\ast}, \beta^{\ast} $是对偶问题的解，并且

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

3.3 定理 3

对原始问题$式(1) \sim 式(3)$和对偶问题$式(11) \sim 式(12)$，假设函数$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且假设不等式约束$c_i(x)$是严格可行的，则$ x^{\ast} 和 \alpha^{\ast}, \beta^{\ast} $分别是原始问题和对偶问题的解的充分必要条件是$ x^{\ast}, \alpha^{\ast}, \beta^{\ast} $满足下面的$ Karush-Kuhn-Tucker(KKT) $条件：

$\nabla_x L(x^{\ast}, \alpha^{\ast}, \beta^{\ast}) = 0 \\ \nabla_\alpha L(x^{\ast}, \alpha^{\ast}, \beta^{\ast}) = 0 \\ \nabla_\beta L(x^{\ast}, \alpha^{\ast}, \beta^{\ast}) = 0$ $\alpha_i^{\ast}c_i(x^{\ast}) = 0, \quad i=1,2,...,k$ $c_i(x^{\ast}) \leq 0, \quad i=1,2,...,k$ $\alpha_i^{\ast} \geq 0, \quad i=1,2,...,k$ $h_j(x^{\ast}) = 0, \quad i=1,2,...,l$

特别指出，$ 式(17) $称为$KKT$的对偶互补条件，由此条件可知：若$ \alpha^{\ast} > 0 $，则$ c_i(x^{\ast})=0 $。

参考

李航 - 《统计学习方法》