Created by potrace 1.13, written by Peter Selinger 2001-2015

拉格朗日对偶

在讲拉格朗日对偶之前,我们首先复习一下拉格朗日乘数法.

拉格朗日乘数法-等式约束

求此方程的最小值：

f(x, y) = x^2 + y^2

同时需要满足条件:

x^2 y = 3

令:

g(x, y) = x^2 y -3 = 0

image

图中蓝色是 g(x, y) ,红色是 f(x, y) ,什么时候能保证 f(x, y) 最小且与 g(x, y) 相交呢?答案是相切的时候,此时两个方程的梯度方向相同,大小不同,所以有:

\nabla f = \lambda \nabla g

其中 \lambda 为拉格朗日乘子.

实际上,还有更简便的方式,定义:

L(x, y, \lambda) = f(x,y) + \lambda g(x, y)

这个函数被称之为拉格朗日函数,将所有 L 方程的偏微分设为零，得到一个方程组，最小值是以下方程组的解中的一个：

\frac{dL}{dx} = 0

\frac{dL}{dy} = 0

\frac{dL}{d\lambda} = 0

拉格朗日乘数法-不等式约束

情况一

求极值:

f(x, y) = x^2 + y^2

同时需要满足不等式约束:

h ( x , y ) = x + y \leq 1

image

可以看到，这个不等式约束有和没有没区别.

情况二

换一个不等式约束:

h ( x , y ) = x + y \leq -2

image

在不等式约束下，最小值是在边缘相切的地方取得：

image

\left\{ \begin{array} { l } { \nabla f + \mu \nabla h = 0 } \\ { h ( x , y ) = x + y = - 2 } \end{array} \right.

此外这里的 \nabla f 与 \nabla h 方向相反,否则约束条件就不起作用了:

image

所以再增加一个条件:

\left\{ \begin{array} { l } { \nabla f + \mu \nabla h = 0 } \\ { h ( x , y ) = x + y = - 2 } \\ { \mu \geq 0 } \end{array} \right.

KKT条件

综合上面的所有情况，同时包含等式和不等式约束的一般优化问题：

\min f(x) \quad s.t. \, g _ { i } = 0 ,h _ { i } \leq 0 , i = 1,2 , \cdots , n

KKT条件为：

\left\{ \begin{array} { l } { \nabla f + \sum _ { i } ^ { n } \lambda _ { i } \nabla g _ { i } + \sum _ { j } ^ { m } \mu _ { j } \nabla h _ { j } = 0 } \\ { g _ { i } = 0 , i = 1,2 , \cdots , n } \\ { h _ { j } \leq 0 , j = 1,2 , \cdots , m } \\ { \mu _ { j } \geq 0 } \\ { \mu _ { j } h _ { j } = 0 } \end{array} \right.

这个方程组也就是所谓的KKT条件。

KKT条件是 x^* 为最优解的必要条件.

拉格朗日对偶

image

拉格朗日对偶是拉格朗日乘数法的一个扩展.

对于带有等式和不等式多个约束条件的优化问题:

\min_w f(w) \quad s.t. \quad g_i(w) \leq 0 , i=1,...,k. \\\qquad\qquad\qquad\qquad h_i(w) = 0 , i=1,...,l.

转换成拉格朗日函数

L(w,\alpha,\beta)=f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^n\beta_ih_i(w)

这里的 \alpha 与 \beta 是拉格朗日乘数.对于

θ_p(w) =\underset{\alpha,\beta:\alpha_i \ge 0}{\max}\ L( w,b,\alpha)

不难得出如果符合约束条件 g_i(w) ≤ 0 ;hi(w) = 0

θ_p(w) = f(x)

如果不符合约束条件

θ_p(w) =\underset{\alpha,\beta:\alpha_i \ge 0}{\max}f(w)+\sum_{i=1}^k\alpha_ig_i(w)+\sum_{i=1}^n\beta_ih_i(w)=+\infty

即

θ_p(w) =\begin{cases} f(x)\ ,\text{满足约束条件}\\+\infty \ \ \ \ \ ,\text{不满足约束条件}\end{cases}

由此我们可以得出一个和原始问题等价的问题:

\underset{w}{\min}θ_p(w) =\underset{w}{\min}\underset{\alpha,\beta:\alpha_i \ge 0}{\max}\ L( w,\alpha,\beta)

稍后我们会用到这个公式,我们现在再来看一个问题:

θ_D(\alpha,\beta) =\underset{w}{\min}\ L( w,\alpha,\beta)

下表D表示对偶,现在我们来看一下对偶优化问题

\underset{\alpha,\beta:\alpha_i \ge 0}{\max}θ_D(w) =\underset{\alpha,\beta:\alpha_i \ge 0}{\max}\underset{w}{\min}\ L( w,\alpha,\beta)

不难证明

d^∗ = \underset{\alpha,\beta:\alpha_i \ge 0}{\max}\underset{w}{\min}\ L( w,\alpha,\beta) \leq \underset{w}{\min}\underset{\alpha,\beta:\alpha_i \ge 0}{\max}\ L( w,\alpha,\beta) = p^*

(小的里面挑出来的大的,一定小于等于大的里面挑出来的小的).当满足一定条件时,可以取等号,即

d^∗ = p^*

如果我们能证明满足条件,那么我们就可以用求对偶函数的方式来求原函数.让我们来看看这些条件是什么.

假设函数 f(w) 与 g_i(w) 是凸函数, g_i(w) 是仿射函数.进一步假设约束 g_i(w) 是连续的,这就意味着有 w 使 g_i(w) < 0 在所有i上成立.

在上述假设之下,一定存在 w^* 为原始问题的解, \alpha^*,\beta^* 是对偶问题的解.使 d^∗ = p^* = L(w^*,\alpha^*,\beta^*) ,并且 w^*,\alpha^*,\beta^* 遵从KKT条件:

\dfrac{\partial}{\partial w_i}L(w^*,\alpha^*,\beta^*) = 0, i=1,...,n

\dfrac{\partial}{\partial \beta_i}L(w^*,\alpha^*,\beta^*) = 0, i=1,...,l

\alpha_i^*g_i(w^*) = 0, i=1,...,k

g_i(w^*) \leq 0, i=1,...,k

\alpha_i^* \geq 0, i=1,...,k

如果 w^*,\alpha^*,\beta^* 满足以上条件,则:

\underset{\alpha,\beta:\alpha_i \ge 0}{\max}\underset{w}{\min}\ L( w,\alpha,\beta) = \underset{w}{\min}\underset{\alpha,\beta:\alpha_i \ge 0}{\max}\ L( w,\alpha,\beta)

参考:
https://zhuanlan.zhihu.com/p/26514613
https://mp.weixin.qq.com/s/SnHGG7ZEZ9SJapPmWhhHpQ

posted @ 2018-12-08 12:08:36
评论加载中...
发表评论