拉格朗日对偶性

整理自统计机器学习附录C。

目录：

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

1、原始问题

$\underset{x \in R^n} {min} \quad f(x)$

$s.t. \quad c_i(x) \leq 0,\quad i=1,2,...,k  $

$\ \qquad h_i(x)=0,\quad i=1,2,...,l$

引入拉格朗日函数：$L(x,\alpha,\beta)=f(x)+\sum_{i=1}^k\alpha_ic_i(x)+\sum_{j=1}^l\beta_i \quad \alpha_i \geq 0$

考虑x的函数：$\theta_p(x)=\underset{x}{max} \ L(x,\alpha,\beta)$

若x违反原始问题的约束，即$c_i(x)>0,h_j(x)!=0$，则$\theta_p(x)=+\infty$；相反，若x满足约束，则$\theta_p(x)=f(x)$；

故，原始问题等价于：$\underset{x}{min} \ \theta_p(x) = \underset{x}{min} \ \underset{\alpha,\beta:\alpha_i \geq 0}{max} \ L(x,\alpha,\beta)$

这个称为广义拉格朗日问题的极小极大问题。

至此，原始问题就可以表示为另一种形式，即广义拉格朗日问题的极小极大问题，这样做也是把一个约束优化问题转变成了无约束优化问题。

定义：$p^*=min \ \theta_p(x)$，为原始问题的最优值。

2、对偶问题

定义：$\theta_D(\alpha,\beta)=\underset{x}{min} \ L(x,\alpha,\beta) $

考虑极大化$\theta_D(\alpha,\beta)=\underset{x}{min} \ L(x,\alpha,\beta) $，即：

$\underset{\alpha,\beta:\alpha_i \geq 0}{max} \theta_D(\alpha,\beta)=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \ min \ L(x,\alpha,\beta) $

称之为广义拉格朗日问题的极大极小问题。

则：

$\underset{\alpha,\beta:\alpha_i \geq 0}{max} \quad \theta_D(\alpha,\beta)=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \ min \ L(x,\alpha,\beta) $

$s.t.\quad \alpha_i \geq 0,\ i=1,2,...,k$

称为原始问题的对偶问题，（把max和min互换即可）。

定义$\quad d^*=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \theta_D(\alpha,\beta)\quad$ 是对偶问题的最优值。

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

定理C.1 :  若原始问题和对偶问题都有最优值，则：

$d^*=\underset{\alpha,\beta:\alpha_i \geq 0}{max} \ min \ L(x,\alpha,\beta) \leq \underset{x}{min} \ \underset{\alpha,\beta:\alpha_i \geq 0}{max} \ L(x,\alpha,\beta) = p^* $

这个很显然： $\theta_D(\alpha,\beta)=\underset{x}{min} \ L(x,\alpha,\beta) \leq \theta_p(x)=\underset{x}{max} \ L(x,\alpha,\beta)$，故

$\underset{x}{max} \ \theta_D(\alpha,\beta) \leq \underset{x}{min}  \ \theta_p(x)$，得证。

以上称之为弱对偶性（weak duality），$p^*-d^*$称为对偶间隙（duality gap）。

推论C.1 : 设$x^*$和$\alpha^*,\beta^*$分别为原始问题和对偶问题的可行解，且$d^*=p^*$，则$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的最优解。

以上称之为强对偶性（strong duality）,

定理C.2：考虑对偶问题和原始问题，假设f(x),$c_i(x)$皆为凸函数，$h_j(x)$为仿射函数，且假设$c_i(x)$严格可行，则存在$\alpha^*,\beta^*,x^*$，使$x^*$是原始问题的解，$\alpha^*,\beta^*$是对偶问题的解，且$p^*=d^*=L(x^*,\alpha^*,\beta^*)$.

定理C.3：同C.2的假设，则$\alpha^*,\beta^*,x^*$是解的充分必要条件是，满足KKT条件：

$\bigtriangledown_x L(x^*,\alpha^*,\beta^*)=0     \qquad 最优条件$

$\bigtriangledown_\alpha L(x^*,\alpha^*,\beta^*)=0$

$\bigtriangledown_\beta L(x^*,\alpha^*,\beta^*)=0$

$\alpha_ic_i(x)=0  \qquad  互补条件$

$c_i(x)=0,\alpha_i \geq 0,,i=1,2...,k \qquad 约束条件$

$h_j(x)=0,j=1,2,...,l  \qquad 约束条件$

以上。