机器学习：优化算法（三）—— 拉格朗日对偶法

在有约束的最优化问题中，常常利用拉格朗日对偶法(Lagrange duality)将原始问题转化为对偶问题，通过求解对偶问题得到原始问题的解。

原始问题

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

$$\begin{align*} \underset{x \in R^n}{min}\ &f(x)\\ s.t.\ &c_i(x)\leqslant 0,\ i=1,2,...,k\\ &h_j(x)=0,\ j=1,2,...,l \end{align*}$$

拉格朗日函数的极小极大问题

拉格朗日函数：$\alpha_i,\ \beta_j$为拉格朗日乘子，其中 $\alpha_i\geqslant 0$

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

令：

$$\theta_P(x)=\underset{\alpha ,\beta }{max}\ L(x,\alpha ,\beta )$$

有：

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

带约束的原始问题可以转化为无约束的拉格朗日函数极小极大问题：

$$\underset{x}{min}\theta_P(x)=\underset{x}{min}\ \underset{\alpha ,\beta }{max}\ L(x,\alpha ,\beta )$$

拉格朗日的极大极小问题(对偶问题)

令：

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

拉格朗日的极大极小问题:

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

KKT 条件

定理1（弱对偶性）：如果原始问题和对偶问题都有最优解，则对偶问题的最优值是原始问题最优值的一个下界：

$$\underset{\alpha ,\beta }{max}\ \underset{x}{min}\ \ L(x,\alpha ,\beta )\leqslant \underset{x}{min}\ \underset{\alpha ,\beta }{max}\ L(x,\alpha ,\beta )$$

证明：强者中最弱的也比弱者中最强的要强

$$\theta_D(x)\leqslant L(x,\alpha ,\beta)\leqslant \theta_P(x)$$

故：

$$\underset{\alpha ,\beta }{max}\ \theta_D(x)\leqslant\underset{x}{min}\ \theta_P(x)$$

定理2（强对偶性）：假设$f(x)$和$c_i(x)$是凸函数，$h_j(x)$是仿射函数，并且不等式约束$c_j(x)$是严格可行的，即存在x对所有i都有$c_i(x)<0$，则$x^$和$\alpha^, \beta^$分别是原始问题和对偶问题的解的充要条件是$x^,\alpha^, \beta^$满足KKT条件：

$$\left\{\begin{matrix} \nabla_xL(x^*,\alpha^*\beta^* )=0 & \\ \nabla_{\alpha }L(x^*,\alpha^*\beta^*)=0 & \\ \nabla_{\beta }L(x^*,\alpha^*\beta^* )=0 & \\ c_i(x^*)\leqslant 0 & i=1,2,...,k\\ h_j(x^*)=0& j=1,2,...,l\\ \alpha_i *\geqslant 0& i=1,2,...,k \\ \alpha_i *c_i(x^*)=0& i=1,2,...,k \end{matrix}\right.$$

$\alpha_i c_i(x^)=0$称为KKT的对偶互补条件，$\alpha_i ,\ c_i(x^*)$必有一个为0.