机器学习 学习笔记（2）拉格朗日乘子法 拉格朗日对偶性

拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法，通过引入拉格朗日乘子，可将有d个变量与k个约束条件的最优化问题转化为具有d+k个变量的无约束优化问题的求解。

拉格朗日对偶性

原始问题：

假设

f(x)

，

c_i(x)

，

h_j(x)

是定义在

\bold R^n

上的连续可微函数，考虑约束最优化问题：

\mathop{\arg\min}_{x\in \bold R^n} f(x)

，

s.t. 

c_i(x)\leqslant 0 ,i=1,2,...,k

，

h_j(x)=0,j=1,2,...,l

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

广义拉格朗日函数（generalized Lagrange function）:

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

这里，

x=(x^{(1)},x^{(2)},...,x^{(n)})^T\in \bold R^n

，

\alpha_i

和

\beta _j

是拉格朗日乘子，

\alpha _i\geqslant 0

，考虑x的函数：

\theta _P(x)= \max \limits_{\alpha, \beta: \alpha_i\geqslant 0} L(x,\alpha, \beta )

下标P表示原始问题，给定某个x，如果x违反原始问题的约束条件，即存在某个i使得

c_i(w)>0

,或者存在某个j使得

h_j(x)\neq 0

，那么就有

\theta _P(x)= \max \limits_{\alpha, \beta: \alpha_i\geqslant 0}[f(x)+\sum_{i=1}^k\alpha _ic_i(x)+\sum_{j=1}^l\beta _jh_j(x)]=+\infty

，如果x满足约束条件，则

\theta _P=f(x)

考虑极小化问题：

\min \limits_{x} \theta _P(x)= \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i\geqslant 0} L(x,\alpha,\beta)

\min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i\geqslant 0} L(x,\alpha,\beta)

是广义拉格朗日函数的极小极大问题，把原始最优化问题表示为广义拉格朗日函数的极小极大问题.

定义原始问题的最优值为：

p^*=\min \limits_{x} \theta _P(x)

对偶问题：

定义：

\theta _D(x)= \min \limits_{x} L(x,\alpha, \beta )

考虑极大化

\theta _D(x)= \min \limits_{x} L(x,\alpha, \beta )

，即：

\max \limits_{\alpha, \beta: \alpha_i\geqslant 0} \theta _D(x)= \max \limits_{\alpha, \beta: \alpha_i\geqslant 0} \min \limits_{x} L(x,\alpha, \beta )

为广义拉格朗日函数的极大极小问题：

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

\max \limits_{\alpha, \beta: \alpha_i\geqslant 0} \theta _D(x)= \max \limits_{\alpha, \beta: \alpha_i\geqslant 0} \min \limits_{x} L(x,\alpha, \beta )

s.t. \alpha_i\geqslant 0, i=1,2,...,k

称为原始问题的对偶问题，定义对偶问题的最优值为：

d^*=\max \limits_{\alpha, \beta: \alpha_i\geqslant 0} \theta _D(x)

，为对偶问题的值

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

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

d^*= \max \limits_{\alpha, \beta: \alpha_i\geqslant 0} \min \limits_{x} L(x,\alpha, \beta )\leqslant \min \limits_{x} \max \limits_{\alpha,\beta:\alpha_i\geqslant 0} L(x,\alpha,\beta)=p*

1、

设

x^*

和

\alpha ^*

，

\beta ^*

分别是原始问题和对偶问题的可行解，并且

d^*=p^*

，则

x^*

和

\alpha ^*

，

\beta ^*

分别是原始问题和对偶问题的最优解。

2、考虑原始问题和对偶问题，假设函数

f(x)

和

c_i(x)

 是凸函数，

h_j(x)

是仿射函数，并且假设不等式约束

c_i(x)

是严格可行的，即存在x，对所有i有

c_i(x)< 0

，则存在

x^*

，

\alpha ^*

，

\beta ^*

，使得

x^*

是原始问题的解，

\alpha ^*

，

\beta ^*

是对偶问题的解，并且：

p^*=d^*=L(x^*,\alpha^*,\beta^*)

3、对原始问题和对偶问题，假设函数 是凸函数， 是仿射函数，并且假设不等式约束是严格可行的，则分别是原始问题和对偶问题的解的充分必要条件是 满足下面的Karush-kuhn-Tucker（KKT）条件：

\nabla_xL(x^*,\alpha^*,\beta^*)=0

\nabla_{\alpha} L(x^*,\alpha^*,\beta^*)=0

\nabla_{\beta} L(x^*,\alpha^*,\beta^*)=0

\alpha^*_i c_i(x)=0,i=1,2,....,k

(KKT对偶互补条件)

c_i(x^*)\leqslant 0, i=1,2,...,k

\alpha^*_i\geqslant 0, i=1,2,...,k

h_j(x^*)=0, j=1,2,...,l

由KKT对偶互补条件可知，若

\alpha ^*_i> 0

，则

c_i(x^*)=0

。

内容参考：

1. 《统计学习方法》
2. 《机器学习》
3. 简易解说拉格朗日对偶（Lagrange duality）