NJU1healer的个人博客分享 http://blog.sciencenet.cn/u/NJU1healer

博文

拉格朗日乘子法

已有 572 次阅读 2021-4-22 15:31 |个人分类:机器学习|系统分类:科研笔记

主要解决两个问题:

(1)理解拉格朗日乘子法;(2)为什么拉格朗日乘子法构造的公式又可写为min max f(x).

(一)理解拉格朗日乘子法

image.png

现在我们想求其上的点与原点的最短距离:

1.gif

这里介绍一种解题思路。首先,与原点距离为[公式] 的点全部在半径为[公式] 的圆上:

2.gif

那么,我们逐渐扩大圆的半径:

3.gif

显然,第一次与[公式] 相交的点就是距离原点最近的点:

image.png

此时,圆和曲线相切,也就是在该点切线相同:

image.png

至此,我们分析出了:在极值点,圆与曲线相切

2.等高线

为了继续解题,需要引入等高线。这些同心圆:

image.png

可以看作函数[公式] 的等高线:

image.png

根据梯度的性质(关于梯度可以查看如何通俗地理解梯度?),梯度向量:

image.png

是等高线的法线:

image.png

另外一个函数[公式] 的等高线为:

image.png

之前的曲线[公式] 就是其中值为3的等高线:

image.png

因此,梯度向量:

image.png

也垂直于等高线[公式] :

image.png

梯度向量是等高线的法线,更准确地表述是:梯度与等高线的切线垂直

3 拉格朗日乘子法

3.1 求解

根据之前的两个分析:

image.png

综合可知,在相切点,圆的梯度向量和曲线的梯度向量平行:

4.gif

也就是梯度向量平行,用数学符号表示为:

image.png

还必须引入[公式] 这个条件,否则这么多等高线,不知道指的是哪一根:

image.png

因此联立方程:

image.png

求一下试试:

image.png

这就是拉格朗日乘子法!!

3.2 定义

要求函数[公式] 在[公式] 约束下的极值这种问题可以表示为:

image.png

[公式] 意思是subject to,服从于,约束于的意思。

可以列出方程组进行求解:

image.png

用这个定义来翻译下刚才的例子,要求:

令:

image.png

求:

image.png

联立方程进行求解:

image.png

3.3 变形

这个定义还有种变形也比较常见,要求:

image.png

定义:

image.png

求解下面方程组即可得到答案:

image.png

把等式左边的偏导算出来就和上面的定义是一样的了。

3.4 多个约束条件

如果增加一个约束条件呢?比如说:

image.png

求:

image.png

从图上看约束条件是这样的:

image.png

很显然,所求的距离是这样的:

image.png

那这三者的法线又有什么关系呢?[公式] 的法线是[公式] 和[公式] 的法线的线性组合:

image.png

假设:

image.png

那么线性组合就表示为:

image.png

联立方程:

image.png

即可求解。

       往更高维度走的话,多约束条件的情况下,问题变为了[公式] 围成的曲线 [公式] 和 相切,直观上看[公式] 必然在[公式] 张成的空间中:

image.png

(二)min max f(x)

       KKT条件是满足强对偶条件的优化问题的必要条件,可以这样理解:我们要求min f(x),  且满足约束条件

                                            s.t.  g_i(x) <= 0; i =1, ..., n

                                                   h_j(x) = 0; j =1, ..., m

       我们构造了函数L(a, b, x) = f(x) + a*g(x) + b*h(x),a>=0,

       此处详细解释为什么在KKT条件下就可以将f(x)写为:max_{a,b} L(a,b,x):我们的目标函数是要求min f(x),为此我们构造了函数L(a, b, x) = f(x) + a*g(x) + b*h(x)(a>=0),那么,由于约束条件为h(x)=0, g(x)<=0,所以我们这里为了使f(x)与L(a, b, x) 等价,用了两个方法:一是给取L(a,b,x)的最大值,这样便于后面用求导方法计算最优值,二是要满足KKT条件,因为a*g(x)是<=0,所以L(a,b,x)只有在a*g(x) = 0的情况下才能取得最大值,否则,就不满足约束条件,因此max_{a,b} L(a,b,x)在满足约束条件的情况下就是f(x)。

       因此我们的目标函数minf(x)可以写为 min_x max_{a,b} L(a,b,x)。如果用对偶表达式: 

       max_{a,b} min_x  L(a,b,x);

       由于我们的优化是满足强对偶的(强对偶就是说对偶式子的最优值是等于原问题的最优值的),所以在取得最优值x0的条件下,它满足 f(x0) = max_{a,b} min_x  L(a,b,x) = min_x max_{a,b} L(a,b,x) =f(x0),我们来看看中间两个式子发生了什么事情:

       f(x0) = max_{a,b} min_x  L(a,b,x) =  max_{a,b} min_x f(x) + a*g(x) + b*h(x) =  max_{a,b}      

       f(x0)+a*g(x0)+b*h(x0) = f(x0)

       可以看到上述加黑的地方本质上是说 min_x f(x) + a*g(x) + b*h(x) 在x0取得了最小值,用fermat定理,即是说对于函数 f(x) + a*g(x) + b*h(x),求取导数要等于零,即

       f(x)的梯度+a*g(x)的梯度+ b*h(x)的梯度 = 0

       这就是kkt条件中第一个条件:L(a, b, x)对x求导为零。

【参考】

https://www.zhihu.com/question/38586401

https://blog.csdn.net/weixin_41694823/article/details/83411435

点滴分享,福泽你我!Add oil!




https://wap.sciencenet.cn/blog-3428464-1283235.html

上一篇:理解判别模型与生成模型
下一篇:[转载]Numpy、GDAL、C++对应数据类型及描述

0

该博文允许注册用户评论 请点击登录 评论 (2 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2021-6-15 05:43

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部