机器学习导论(附录)–拉格朗日乘子法

2,039次阅读次阅读
没有评论

在LDA线性判别分析中使用到拉格朗日乘子法,本着从理论到实践搞清楚机器学习原理,深入研究下每个方法的本质,虽然百度会有一大堆介绍,自己也尝试在此基础上使用白话的方式来阐述

最优化问题分类

最优化问题有如下几类:

(i) 无约束优化问题,可以写为:

min f(x);

(ii) 有等式约束的优化问题,可以写为:

min f(x),

s.t. h_i(x) = 0; i =1, …, n

(iii) 有不等式约束的优化问题,可以写为:

min f(x),

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

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

对于第(i)类的优化问题,常常使用的方法就是Fermat定理,即使用求取f(x)的导数,然后令其为零,可以求得候选最优值,再在这些候选值中验证;如果是凸函数,可以保证是最优解。

对于第(ii)类的优化问题,常常使用的方法就是拉格朗日乘子法(Lagrange Multiplier) ,即把等式约束h_i(x)用一个系数与f(x)写为一个式子,称为拉格朗日函数,而系数称为拉格朗日乘子。通过拉格朗日函数对各个变量求导,令其为零,可以求得候选值集合,然后验证求得最优值。

对应的函数可以表示为

F(x,y)=f(x,y)+lambda*h_i(x,y)

分别对变量x和lambda求导,得到最优化问题的求解

数学解释

机器学习导论(附录)--拉格朗日乘子法上述圆形虚线圈表示等高线,等高线的概念(可以想象一个山从山顶往下俯视就会得到不同山高度的等高线,类似上图一圈一圈)

g(x,y)相当于之前给定的方程中的h_i(x,y)也是优化问题中的约束条件,g(x,y)与等高线存在相交和相切的时候。相交的点符合最优化问的解,但是相交点并不是我们需要的点,为什么?如果二者相交,证明还存在相应的等高线使得达到最大值或者最小值,当前的点并不是最优的。

机器学习导论(附录)--拉格朗日乘子法上图红色约束条件与等高线相交,必然还存在其他等高线符合约束条件且达到最优。

所以不言而喻二者在相交的时候就会达到最优值,此时二者在该点的法向量相同方向或者相反,因此

对F(x,y)=f(x,y)+lambda*h_i(x,y)求解x偏是函数在无约束条件下的充分条件

admin
版权声明:本站原创文章,由admin2016-11-22发表,共计1569字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)