拉格朗日对偶性
整理自统计机器学习附录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)=max \quad L(x,\alpha,\beta)$
若x违反原始问题的约束，即$c_i(x)>0,h_j(x)!=0$，则$\theta_p(x)=+\infty$；相反，若x满足约束，则$\theta_p(x)=f(x)$；即：
$$\theta_p(x) = \begin{cases} f(x), & \text{如果$x$满足约束} \\ +\infity, & \text{如果$x$ 违反约束} \end{cases} $$
故，原始问题等价于：$\underset{x}{min} \quad \theta_p(x) = \underset{x}{min} \quad \underset{\alpha,\beta:\alpha_i \geq 0}{max} \quad 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} \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
$$
称为原始问题的对偶问题。
定义$\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} \quad \underset{\alpha,\beta:\alpha_i \geq 0}{max} \quad L(x,\alpha,\beta) = p^* $
推论C.1 : 设$x^*$和$\alpha^*,\beta^*$分别为原始问题和对偶问题的可行解，且$d^*=p^*$，则$x^*$和$\alpha^*,\beta^*$分别是原始问题和对偶问题的最优解。
定理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,h_j(x)=0,i=1,2…,k,j=1,2,…,l
$$
以上。