精华内容
下载资源
问答
  • 拉格朗日乘数法应用
    万次阅读
    2020-06-13 14:55:41

    使用场景

    适用于求条件极值。即对函数求极值,而自变量要满足约束条件。

    使用方法

    例如:求f(x,y,z)的极值,要求f的自变量满足约束条件φ(x,y,z)。
    解:
    第一步:
    设L=f(x,y,z)+λφ(x,y,z);
    第二步:
    求L的驻点,即对各个自变量求L的偏导数,并使其为0;
    第三步:
    解方程组,根据题意求极值点。

    案例

     

    更多相关内容
  • 其次,使用多粒度区域划分和拉格朗日乘数法来计算最终坐标。 由于在实际应用中节点受多种因素的影响,设计了两种定位方法。 当未知节点位于定位单元内部时,我们使用矢量相似度方法。 此外,我们使用质心算法来计算...
  • 拉格朗日乘数法

    万次阅读 多人点赞 2017-12-26 16:48:50
    原文地址:... 阅读目录 1. 拉格朗日乘数法的基本思想 2.... 3.... 4.... 拉格朗日乘数法(Lagrange Multiplier Method)之前听数学老师授课的时候就是一知半解,现在越发感觉拉格朗日乘数法应用的广泛性,...

    原文地址:https://www.cnblogs.com/maybe2030/p/4946256.html

    阅读目录

     

      拉格朗日乘数法(Lagrange Multiplier Method)之前听数学老师授课的时候就是一知半解,现在越发感觉拉格朗日乘数法应用的广泛性,所以特意抽时间学习了麻省理工学院的在线数学课程。新学到的知识一定要立刻记录下来,希望对各位博友有些许帮助。

    回到顶部

    1. 拉格朗日乘数法的基本思想

      作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

      如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题?拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n+k)变量的(n+k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。

      解决的问题模型为约束优化问题:

      min/max a function f(x,y,z), where x,y,z are not independent and g(x,y,z)=0.

      即:min/max f(x,y,z)

        s.t. g(x,y,z)=0

    回到顶部

    2. 数学实例

      首先,我们先以麻省理工学院数学课程的一个实例来作为介绍拉格朗日乘数法的引子。

      【麻省理工学院数学课程实例】求双曲线xy=3上离远点最近的点。

      解:

      首先,我们根据问题的描述来提炼出问题对应的数学模型,即:

      min f(x,y)=x2+y2(两点之间的欧氏距离应该还要进行开方,但是这并不影响最终的结果,所以进行了简化,去掉了平方)

      s.t. xy=3.

      根据上式我们可以知道这是一个典型的约束优化问题,其实我们在解这个问题时最简单的解法就是通过约束条件将其中的一个变量用另外一个变量进行替换,然后代入优化的函数就可以求出极值。我们在这里为了引出拉格朗日乘数法,所以我们采用拉格朗日乘数法的思想进行求解。

      我们将x2+y2=c的曲线族画出来,如下图所示,当曲线族中的圆与xy=3曲线进行相切时,切点到原点的距离最短。也就是说,当f(x,y)=c的等高线和双曲线g(x,y)相切时,我们可以得到上述优化问题的一个极值(注意:如果不进一步计算,在这里我们并不知道是极大值还是极小值)。

      现在原问题可以转化为求当f(x,y)和g(x,y)相切时,x,y的值是多少?

      如果两个曲线相切,那么它们的切线相同,即法向量是相互平行的,▽f//▽g.

      由▽f//▽g可以得到,▽f=λ*▽g。

      这时,我们将原有的约束优化问题转化为了一种对偶的无约束的优化问题,如下所示:

      原问题:min f(x,y)=x2+y2              对偶问题:由▽f=λ*▽g得,

          s.t. xy=3                                       fx=λ*gx,

                                                                         fy=λ*gy,

                                                                              xy=3.

                      约束优化问题                                   无约束方程组问题

      通过求解右边的方程组我们可以获取原问题的解,即

      2x=λ*y

      2y=λ*x

      xy=3

      通过求解上式可得,λ=2或者是-2;当λ=2时,(x,y)=(sqrt(3), sqrt(3))或者(-sqrt(3), -sqrt(3)),而当λ=-2时,无解。所以原问题的解为(x,y)=(sqrt(3), sqrt(3))或者(-sqrt(3), -sqrt(3))。

      通过举上述这个简单的例子就是为了体会拉格朗日乘数法的思想,即通过引入拉格朗日乘子(λ)将原来的约束优化问题转化为无约束的方程组问题。

    回到顶部

    3. 拉格朗日乘数法的基本形态

       求函数在满足下的条件极值,可以转化为函数的无条件极值问题。

    即等式约束条件

     

             min f(x,y)    

              s.t. g(x,y) = c

      我们可以画图来辅助思考。

      绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率,和等高线的法线平行。

         分析:从梯度的方向上来看,显然有d1>d2。绿色的线是约束,也就是说,只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约    束,f(x,y)的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束,最小值点应该在哪里呢?显然应该是在f(x,y)的等高线正好和约束线相切的位置,因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部,使得新的等高线与目标函数的交点的值更大或者更小,只有到等高线与目标函数的曲线相切的时候,可能取得最优值。

     

         如果我们对约束也求梯度∇g(x,y),则其梯度如图中绿色箭头所示。很容易看出来,要想让目标函数f(x,y)的等高线和约束相切,则他们切点的梯度一定在一条直线上(f和g的斜率平行)。

      也即在最优化解的时候:∇f(x,y)=λ(∇g(x,y)-C)    (其中∇为梯度算子; 即:f(x)的梯度 = λ* g(x)的梯度,λ是常数,可以是任何非0实数,表示左右两边同向。)

          即:▽[f(x,y)+λ(g(x,y)−c)]=0 , λ≠0

      一旦求出λ的值,将其套入下式,易求在无约束极值和极值所对应的点。

      F(x,y)=f(x,y)+λ(g(x,y)−c)

      新方程F(x,y)在达到极值时与f(x,y)相等,因为F(x,y)达到极值时g(x,y)−c总等于零。

      上述式子取得极小值时其导数为0,即▽f(x)+▽∑λigi(x)=0,也就是说f(x)和g(x)的梯度共线。

     简单的说,在F(x,λ)取得最优化解的时候,即F(x,λ)取极值(导数为0,▽[f(x,y)+λ(g(x,y)−c)]=0)的时候,f(x)与g(x) 梯度共线,此时就是在条件约束g(x)下,f(x)的最优化解。

      题目1:

      给定椭球

         

      求这个椭球的内接长方体的最大体积。这个问题实际上就是条件极值问题,即在条件   

        

      下,求的最大值。

      当然这个问题实际可以先根据条件消去,然后带入转化为无条件极值问题来处理。但是有时候这样做很困难,甚至是做不到的,这时候就需要用拉格朗日乘数法了。通过拉格朗日乘数法将问题转化为

         

      对求偏导得到

         

      联立前面三个方程得到,带入第四个方程解之

          

      带入解得最大体积为

          

      拉格朗日乘数法对一般多元函数在多个附加条件下的条件极值问题也适用。

      题目2:

      题目:求离散分布的最大熵。

      分析:因为离散分布的熵表示如下

         

         而约束条件为

         

         要求函数的最大值,根据拉格朗日乘数法,设

         

         对所有的求偏导数,得到

         

         计算出这个等式的微分,得到

         

         这说明所有的都相等,最终解得

         

         因此,使用均匀分布可得到最大熵的值。

    回到顶部

    4. 拉格朗日乘数法与KKT条件

      我们上述讨论的问题均为等式约束优化问题,但等式约束并不足以描述人们面临的问题,不等式约束比等式约束更为常见,大部分实际问题的约束都是不超过多少时间,不超过多少人力,不超过多少成本等等。所以有几个科学家拓展了拉格朗日乘数法,增加了KKT条件之后便可以用拉格朗日乘数法来求解不等式约束的优化问题了。

      首先,我们先介绍一下什么是KKT条件。

      KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式参考开头的式子, 所谓 Karush-Kuhn-Tucker 最优化条件,就是指上式的最优点x∗必须满足下面的条件:

      1). 约束条件满足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q    (h(x) =0;

      2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇为梯度算子; (L(a, b, x)对x求导为零;

      3). λj≠0且不等式约束条件满足μi≥0,μigi(x∗)=0,i=1,2,…,p。 (a*g(x) = 0;

      KKT条件第一项是说最优点x∗必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的. 第二项表明在最优点x∗, ∇f必须是∇gi和∇hj的线性組合, μi和λj都叫作拉格朗日乘子. 所不同的是不等式限制条件有方向性, 所以每一个μi都必须大于或等于零, 而等式限制条件没有方向性,所以λj没有符号的限制, 其符号要视等式限制条件的写法而定.

      为了更容易理解,我们先举一个例子来说明一下KKT条件的由来。

      let L(x,μ)=f(x)+∑k=1μkgk(x),其中μk≥0,gk(x)≤0

      ∵μk≥0 gk(x)≤0  =>  μg(x)≤0

      ∴maxμL(x,μ)=f(x)                  (2)

      ∴minxf(x)=minxmaxμL(x,μ)     (3)

      maxμminxL(x,μ)=maxμ[minxf(x)+minxμg(x)]=maxμminxf(x)+maxμminxμg(x)=minxf(x)+maxμminxμg(x)

      又∵μk≥0, gk(x)≤0

      

      ∴maxμminxμg(x)=0, 此时μ=0 or g(x)=0.

      ∴maxμminxL(x,μ)=minxf(x)+maxμminxμg(x)=minxf(x)      (4)

      此时μ=0 or g(x)=0.

      联合(3),(4)我们得到minxmaxμL(x,μ)=maxμminxL(x,μ), 亦即

       

      minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)

      我们把maxμminxL(x,μ)称为原问题minxmaxμL(x,μ)的对偶问题,上式表明当满足一定条件时原问题、对偶的解、以及minxf(x)是相同的,且在最优解x∗处μ=0 or g(x∗)=0。把x∗代入(2)得maxμL(x∗,μ)=f(x∗),由(4)得maxμminxL(x,μ)=f(x∗),所以L(x∗,μ)=minxL(x,μ),这说明x∗也是L(x,μ)的极值点,即

      

      最后总结一下:

      

      KKT条件是拉格朗日乘子法的泛化,如果我们把等式约束和不等式约束一并纳入进来则表现为:

      

      注:x,λ,μ都是向量。

      

      表明f(x)在极值点x∗处的梯度是各个hi(x∗)和gk(x∗)梯度的线性组合。

    展开全文
  • 为了求解带有多个约束条件的多元线性回归的参数估计问题,基于广义逆矩阵理论,利用多元微积分求条件极值的拉格朗日乘数法,通过建立辅助函数,把带有多个约束条件的多元线性回归参数估计问题转化为计算无条件极值,并给...
  • #16 拉格朗日乘数法 所谓拉格朗日乘数法,是一种求条件极值的办法。所谓条件极值,就是在给定的约束条件下,求目标函数的极值。 符号解释:目标函数 u=f(x,y)u = f(x,y)u=f(x,y), 约束条件 φ(x,y)=0\varphi(x,y) = ...

    #16 拉格朗日乘数法

    所谓拉格朗日乘数法,是一种求条件极值的办法。所谓条件极值,就是在给定的约束条件下,求目标函数的极值。

    符号解释:目标函数 u = f ( x , y ) u = f(x,y) u=f(x,y), 约束条件 φ ( x , y ) = 0 \varphi(x,y) = 0 φ(x,y)=0

    应用条件: f ( x , y ) f(x,y) f(x,y) φ ( x , y ) \varphi(x,y) φ(x,y)一阶偏导数连续( ⇒ \Rightarrow 可微)

    证明:可参考拉格朗日乘数法-wiki

    使用方法:

    1. 构造拉格朗日函数 F ( x , y , λ ) = f ( x , y ) + λ φ ( x , y ) F(x,y,\lambda) = f(x,y)+\lambda \varphi(x,y) F(x,y,λ)=f(x,y)+λφ(x,y)
    2. 梯度为零,构造方程组: ∇ F = 0 \nabla F = \mathbf{0} F=0
    3. 解得满足方程组的驻点
    4. 根据实际情况判断这些点是不是极值点

    从使用方法4可以看出,拉格朗日乘数法,求得的点其实仅仅可能是极值点。

    举例:证明当离散信源均匀分布的时候熵最大

    目标函数: H = − ∑ i = 1 N p i l o g 2 ( p i ) H = -\sum_{i=1}^N p_i log_2(p_i) H=i=1Npilog2(pi)

    约束条件: p 1 + p 2 + p 3 + ⋯ + p N = 1 p_1 + p_2 + p_3 + \cdots + p_N = 1 p1+p2+p3++pN=1,且 p i > 0 p_i > 0 pi>0

    证明:

    proof_maxEntropy_DMS

    展开全文
  • 最优化方法:拉格朗日乘数法

    千次阅读 2020-12-24 06:50:20
    拉格朗日乘数法的基本思想作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。...

    解决约束优化问题——拉格朗日乘数法

    拉格朗日乘数法(Lagrange Multiplier Method)应用广泛,可以学习麻省理工学院的在线数学课程。

    拉格朗日乘数法的基本思想

    作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

    如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题?拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n+k)变量的(n+k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。

    解决的问题模型为约束优化问题:

    min/max a function f(x,y,z), where x,y,z are not independent and g(x,y,z)=0.

    即:min/max f(x,y,z)

    s.t. g(x,y,z)=0

    数学实例

    首先,我们先以麻省理工学院数学课程的一个实例来作为介绍拉格朗日乘数法的引子。

    【麻省理工学院数学课程实例】求双曲线xy=3上离远点最近的点。

    解:

    首先,我们根据问题的描述来提炼出问题对应的数学模型,即:

    min f(x,y)=x2+y2(两点之间的欧氏距离应该还要进行开方,但是这并不影响最终的结果,所以进行了简化,去掉了平方)

    s.t. xy=3.

    根据上式我们可以知道这是一个典型的约束优化问题,其实我们在解这个问题时最简单的解法就是通过约束条件将其中的一个变量用另外一个变量进行替换,然后代入优化的函数就可以求出极值。我们在这里为了引出拉格朗日乘数法,所以我们采用拉格朗日乘数法的思想进行求解。

    我们将x2+y2=c的曲线族画出来,如下图所示,当曲线族中的圆与xy=3曲线进行相切时,切点到原点的距离最短。也就是说,当f(x,y)=c的等高线和双曲线g(x,y)相切时,我们可以得到上述优化问题的一个极值(注意:如果不进一步计算,在这里我们并不知道是极大值还是极小值)。

    现在原问题可以转化为求当f(x,y)和g(x,y)相切时,x,y的值是多少?

    如果两个曲线相切,那么它们的切线相同,即法向量是相互平行的,▽f//▽g.

    由▽f//▽g可以得到,▽f=λ*▽g。

    这时,我们将原有的约束优化问题转化为了一种对偶的无约束的优化问题,如下所示:

    原问题:min f(x,y)=x2+y2              对偶问题:由▽f=λ*▽g得,

    s.t. xy=3                                       fx=λ*gx,

    fy=λ*gy,

    xy=3.

    约束优化问题                                   无约束方程组问题

    通过求解右边的方程组我们可以获取原问题的解,即

    2x=λ*y

    2y=λ*x

    xy=3

    通过求解上式可得,λ=2或者是-2;当λ=2时,(x,y)=(sqrt(3), sqrt(3))或者(-sqrt(3), -sqrt(3)),而当λ=-2时,无解。所以原问题的解为(x,y)=(sqrt(3), sqrt(3))或者(-sqrt(3), -sqrt(3))。

    通过举上述这个简单的例子就是为了体会拉格朗日乘数法的思想,即通过引入拉格朗日乘子(λ)将原来的约束优化问题转化为无约束的方程组问题。

    拉格朗日乘数法的基本形态

    求函数

    在满足

    下的条件极值,可以转化为函数

    的无条件极值问题。

    我们可以画图来辅助思考。

    绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率,和等高线的法线平行。

    从图上可以直观地看到在最优解处,f和g的斜率平行。

    ▽[f(x,y)+λ(g(x,y)−1)]=0, λ≠0

    一旦求出λ的值,将其套入下式,易求在无约束极值和极值所对应的点。

    F(x,y)=f(x,y)+λ(g(x,y)−c)

    新方程F(x,y)在达到极值时与f(x,y)相等,因为F(x,y)达到极值时g(x,y)−c总等于零。

    上述式子取得极小值时其导数为0,即▽f(x)+▽∑λigi(x)=0,也就是说f(x)和g(x)的梯度共线。

    题目1:

    给定椭球

    求这个椭球的内接长方体的最大体积。这个问题实际上就是条件极值问题,即在条件

    下,求

    的最大值。

    当然这个问题实际可以先根据条件消去

    ,然后带入转化为无条件极值问题来处理。但是有时候这样做很困难,甚至是做不到的,这时候就需要用拉格朗日乘数法了。通过拉格朗日乘数法将问题转化为

    求偏导得到

    联立前面三个方程得到

    ,带入第四个方程解之

    带入解得最大体积为

    拉格朗日乘数法对一般多元函数在多个附加条件下的条件极值问题也适用。

    题目2:

    题目:求离散分布的最大熵。

    分析:因为离散分布的熵表示如下

    而约束条件为

    要求函数

    的最大值,根据拉格朗日乘数法,设

    对所有的

    求偏导数,得到

    计算出这

    个等式的微分,得到

    这说明所有的

    都相等,最终解得

    因此,使用均匀分布可得到最大熵的值。

    拉格朗日乘数法与KKT条件

    拉格朗日乘数法

    对于第二种形式,带约束条件的问题,我们更倾向于将其转化为无约束问题。在数学最优化问题中,拉格朗日乘数法是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题,其变量不受任何约束。这种方法引入了一种新的标量未知数,即拉格朗日乘数(:约束方程的梯度(gradient)的线性组合里每个向量的系数,搞不懂这句话在说神马)。

    上面这段话读起来挺绕的,还是举个例子吧。

    目标是求f(x,y)=x2∗yf(x,y)=x2∗y的最大值

    同时满足x2+y2=1x2+y2=1

    怎么将这两个式子凑到一起呢?引入个系数变量λλ

    构造新目标函数F(x,y,λ)=x2∗y+λ∗(x2+y2−1)F(x,y,λ)=x2∗y+λ∗(x2+y2−1)

    我们看看新目标函数的特点:

    对λλ求导,则得:(1)∂f(x,y,λ)∂λ=x2+y2−1∂f(x,y,λ)∂λ=x2+y2−1

    对xx求导,则得:(2)∂f(x,y,λ)∂x=2xy+2λx∂f(x,y,λ)∂x=2xy+2λx

    对yy求导,则得:(3)∂f(x,y,λ)∂y=x2+2λy∂f(x,y,λ)∂y=x2+2λy

    若是按照一个函数的最值存在于其极值的思想来解答,则令这三个式子为0,可以看到,原来的约束也包括进了新目标函数中,不过是引入了个新变量λλ。

    并且在F(x,y,λ)F(x,y,λ)取得极值时,与f(x,y)f(x,y)相等,因为FF取得极值时,∂f(x,y,λ)∂λ=x2+y2−1=0∂f(x,y,λ)∂λ=x2+y2−1=0,F(x,y,λ)F(x,y,λ)变为f(x,y)f(x,y)。故,F(x,y,λ)F(x,y,λ)的极值必然是f(x, y)的极值。这段话很重要~

    但是这里对原参数的偏导数里多出来的λλ项怎么解释呢?

    λλ的物理意义:表示原目标函数在约束下,所能达到的最大增长率(梯度)。其解释如下:

    F(w,λ)=f(w)+λ∗g(w)F(w,λ)=f(w)+λ∗g(w);

    ∂F∂w=∂f∂w+λ∂g∂w∂F∂w=∂f∂w+λ∂g∂w;

    ∂F∂λ=g(w)∂F∂λ=g(w)

    令∂F∂w=0∂F∂w=0,则得λ=−f′wg′wλ=−fw′gw′,可以看出来原目标函数f(w)f(w)的的梯度(最大增长率)受到了g(w)g(w)的梯度约束。

    若是将∂F∂λ=g(w)=0∂F∂λ=g(w)=0带入上述λλ式子中,可以得到在确定约束条件下的原目标函数的梯度。(这个说法有问题没有?上面λλ式子已经是在极值下求解得到的,不过没有考虑约束g(x)=0g(x)=0,所以这个说法是没问题的)

    (因此,上面的求解最优值,就变成了在约束条件下,原目标函数在约束函数下的梯度求解问题。怎么感觉怪怪的,没想到就变成了这样的问题。错误原因:有地方理解的有问题,对新目标求极值,中间找到了参数间的关系,然后把一个变量表示了出来,只能说明新目标函数在极值时的某个参数的样子)

    画个图或许更直观一些。

    在约束条件下某目标函数的最值,只可能出现在约束函数的等高线和目标函数在参数面投影的相切的地方。

    上图中,f(x,y)f(x,y)为目标函数,g(x,y)=cg(x,y)=c为约束条件,我们将两者投影到xyxy平面上得到两者的等高线分布,体现在空间中就是g(x,y)=0g(x,y)=0向上做垂直切面,切割了f(x,y)f(x,y),得到了个曲线,这个曲线投影到xyxy面上刚好与g(x,y)=0g(x,y)=0重合,可以看到随着f(x,y)f(x,y)的xyxy范围缩小(对应其值逐渐增大),会有个与g(x,y)=0g(x,y)=0的切点B,对应于f(x,y)f(x,y)上的A点。A点则是满足约束的,刚好又是最值的地方。

    对逻辑回归里惩罚的解释

    现在回过头来看,线性回归目标函数里面的惩罚,是怎么个情况,明白了没?结果发现还是没能够解释为什么要加惩罚12wTw12wTw。哎~!~好囧~!~

    经过跟马博和贾老师的讨论,终于把这个问题整出了一个较为合理的解释。

    首先高次多项式回归的评估函数是误差函数:

    cost(x,w)=12∑Mi=1[f(x,w)−y]2cost(x,w)=12∑i=1M[f(x,w)−y]2;前面的1/2是为了后期求导的时候方便。

    现在对参数ww进行约束,因为高次对应的参数会很大程度上影响拟合度,并且会有甩尾现象,想把其影响降到较小程度,并且尽可能保留主要部分(w0w0对应的信息)使得泛化能力强,我们想怎么去约束ww呢?

    如果wT∗w⩽w20wT∗w⩽w02(二阶范数约束,肯定还有其他约束的情况),那岂不是实现了我们的约束目的,一方面对高次对应的参数进行了约束,一方面他们对整体的影响还不会对整体超过w0w0的影响。

    这样,还不能够用拉格朗日乘子法,因为该方法是解决等式约束的最值问题。怎么办呢?好好看看误差函数,这是一个凸函数,我们对ww的约束是在某个范围内,那么根据上面手绘图来看,最值的解只可能出现在,误差函数的等高线与约束最外边缘的切点上。啊哈,这个地方给了我们很大启示,可以直接在约束边缘上找到误差函数的最小值即可。

    看下面这个图,就很直观地说明了这个问题。左侧为二阶范数约束,右侧为一阶范数约束。

    于是对误差函数的在不等式wTw⩽w20wTw⩽w02的最值问题的解,就是误差函数在等式wTw=w20wTw=w02的最值的解。

    哈哈,终于可以正大光明的应用拉格朗日乘子法了,于是就有了我们加入惩罚之后的新的代价函数:

    Cost(x,w)=∑Mi=1[f(x,w)−y]2+λ[wT∗w−w20]Cost(x,w)=∑i=1M[f(x,w)−y]2+λ[wT∗w−w02]

    这地方离着我们在书本上看到的代价函数还有点区别,就是λλ向量统一变成了1212,目测估计是为了方便求解。

    可以有其他的约束,比如∑Mj=0|wj|q⩽η∑j=0M|wj|q⩽η

    KKT条件下最优求解

    对于第三种情况,又有等式约束,又有不等式约束的,怎么搞呢?上面我们是用拉格朗日乘数法搞定的等式约束的问题,那么对于包括有不等式约束的,可不可以把拉格朗日乘数法扩展一下,充分利用它,解决现在的问题呢?答案是可以,就是满足KKT条件时的最值求解。

    KKT条件:在满足一些有规则的条件下,一个非线性规划(Nonlinear Programming)问题能有最优化解的一个必要和充分条件。这是一个广义化拉格朗日乘数的成果,KKT是三个作者的首字母,Karush & Kuhn &Tucker。

    求解的问题是:

    minf(w)minf(w)

    s.t.gi(w)=0,i=1,2,...,n;s.t.gi(w)=0,i=1,2,...,n;

    hj(w)⩽0,j=1,2,...,m;hj(w)⩽0,j=1,2,...,m;

    什么条件下,上述问题有最值解呢?

    KKT出场了~

    先说充分条件:

    如果有常数μi⩾0μi⩾0及vjvj满足下述条件:

    ▽f(w)+∑ni=1μi▽gi(w)+∑mj=1vj▽hj(w)=0▽f(w)+∑i=1nμi▽gi(w)+∑j=1mvj▽hj(w)=0

    且μigi(w)=0μigi(w)=0 forfor allall i=1,2,...,ni=1,2,...,n

    当然有个重要的前提假设,就是目标函数ff和约束函数gg都是凸函数。

    再说必要条件:

    如果目标函数和约束函数在某点ww连续可微,点ww为一局部极小值,那么则存在一组所称乘子的常数λ⩾0,λ⩾0, μi⩾0(i=1,2,3,...,n)μi⩾0(i=1,2,3,...,n)及vj(j=1,2,...,m)vj(j=1,2,...,m)满足如下条件:

    λ+∑ni=1μi+∑mj=1|vj|>0λ+∑i=1nμi+∑j=1m|vj|>0

    λ▽f(w)+∑ni=1μi▽gi(w)+∑mj=1vj▽hj(w)=0λ▽f(w)+∑i=1nμi▽gi(w)+∑j=1mvj▽hj(w)=0

    μigi(w)=0μigi(w)=0 forfor i=1,2,...,ni=1,2,...,n

    那么这个点ww是全局最小值。(▽▽都是对参数ww求导)

    小结

    约束下的函数最值问题求解,即将约束问题转化为无约束问题,然后再去解决。

    中间会有一些小技巧,自己需要在实际应用中灵活应变。

    展开全文
  • 拉格朗日乘数法基础

    万次阅读 2019-02-19 10:17:33
    背景 线性可分 SVM 的目标函数...本文将摘录高等数学下册中拉格朗日乘数法的数学知识,08年学的高等数学下册,十多年了早还给老师了,只是还保留着当年的书本,这次春节回家把两本高数书带来了,当作AI学习的参考资...
  • 拉格朗日乘数法整理

    2020-07-24 20:22:54
    拉格朗日乘数法 一种不直接依赖消元法而求解条件极值问题的有效方法 二元函数入手 我们从 f,φf, \varphif,φ皆为二元函数这一简单情况人手. 欲求函数 z=f(x,y) z=f(x, y) z=f(x,y) 的极值,其中(x,y)( x,y)(x,y)受...
  • [Math & Algorithm] 拉格朗日乘数法

    千次阅读 2019-05-27 19:57:54
    阅读目录 1. 拉格朗日乘数法的基本思想 ... 拉格朗日乘数法(Lagrange Multiplier Method)之前听数学老师授课的时候就是一知半解,现在越发感觉拉格朗日乘数法应用的广泛性,所以特意抽时间学...
  • 拉格朗日乘数法及KKT条件-通俗理解

    千次阅读 2020-12-07 16:10:26
    1.拉格朗日乘数法的基本思想 在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的...
  • x^2+y^2<=1 求x^2+xy-y^2的最大值,最小值 最大值√5/2,最小值-√5/2。
  • 条件极值问题、拉格朗日乘数法

    千次阅读 2020-12-24 12:33:54
    最近有一道网红题长这样: 求 这看上去不是很像高中题,倒像是联赛的送分题,或者是拉格朗日乘数法的练习题。在这里,我就给出一个有拉乘味道的解法:取等条件看了文章的标题,就能够知道上面 的系数是怎么来的了。...
  • 文章目录定义理解「拉格朗日乘数法」一些例题 定义 拉格朗日乘数法(Lagrange multiplier,以数学家约瑟夫·拉格朗日命名),在数学中的最优化问题中,是一种寻找多元函数在其变量受到一个或多个条件的约束时的极值...
  • 张量恢复的混合增强拉格朗日乘数法及其应用
  • 最优化方法:拉格朗日乘数法 2016年08月18日 14:34:38-柚子皮-阅读数 31809更多 分类专栏:机器学习MachineLearningMath 版权声明:本文为博主原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上...
  • 拉格朗日乘数法到KKT条件 最近看论文遇到了Karush–Kuhn–Tucker (KKT)条件,想搞清楚这是个什么东东,因此就把这个东西认真学习一下并且分享出来,希望对大家有用。学习KKT就不得不先学习一下拉格朗日乘数法,...
  • 回到上面的题目,通过拉格朗日乘数法将问题转化为: F(x,y,z,λ)=f(x,y,z)+λφ(x,y,z)=8xyz+λ(x2a2+y2b2+z2c2−1)F(x,y,z,\lambda)=f(x,y,z)+\lambda\varphi (x,y,z)=8xyz+\lambda(\frac{x^2}{a^2}+\frac{y^2}{b^...
  • 拉格朗日乘数法在消费者均衡原则中的应用.doc
  • A C − B 2 ^2−B2极值不存在 A C − B 2 ^2−B2机制可能存在可能不存在   若存在极值,则极值为 f ( x 0 , y 0 ) f(x_0, y_0) f(x0​,y0​) 拉格朗日乘数法   这个就是用来求在满足 φ ( x , y ) = 0 \varphi...
  • 机器学习之拉格朗日乘数法

    千次阅读 2016-11-19 18:39:08
    在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k...
  • 应用拉格朗日乘数法,将空闲时间分布到数据通路的各个操作节点上,从而有效地降低了设计电路的能耗。该方法在调度和调整过程中,可以同时处理关键通路和非关键通路上的节点。实验结果表明了该方法在功耗优化方面的...
  • - 有约束最优化问题:拉格朗日乘数法。 一、梯度下降法 1、算法简介   梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,...
  •  拉格朗日乘数法(Lagrange Multiplier Method)之前听数学老师授课的时候就是一知半解,现在越发感觉拉格朗日乘数法应用的广泛性,所以特意抽时间学习了麻省理工学院的在线数学课程。新学到的知识一定要立刻记录...
  • 假定求目标函数: u = f ( x , y ) u=f(x,y) u = f ( x , y ) 在条件 φ ( x , y ) = 0 φ(x,y)=0 φ ( x , y ) = 0 下的极值。 ...这种方法称之为拉格朗日乘数法。 并且支持类似的推广。
  • 多元函数条件极值的求法 拉格朗日乘数法

    万次阅读 多人点赞 2018-05-30 16:08:16
    拉格朗日乘数法可直接寻求条件极值,不必先把问题转化到无条件极值的问题。 二、拉格朗日乘数法 要找函数 在附加条件 下的可能极值点,可以先做拉格朗日函数 其中 λ为参数(称为拉格朗日乘子) 。求其对x与y的一阶...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,520
精华内容 608
关键字:

拉格朗日乘数法应用