精华内容
下载资源
问答
  • 拉格朗日乘数

    万次阅读 多人点赞 2017-12-26 16:48:50
    阅读目录 1. 拉格朗日乘数法的基本思想 2.... 3. 拉格朗日乘数法的基本形态 ... 拉格朗日乘数法(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∗)梯度的线性组合。

    展开全文
  • 拉格朗日乘数法(Lagrange Multiplier Method)基本思想 作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有...

    拉格朗日乘数法(Lagrange Multiplier Method)基本思想
    作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。
    如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题?拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n+k)变量的(n+k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。

    维基百科:最优化解
    在这里插入图片描述
    绿线标出的是约束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)达到极值时g(x,y)−c等于零。
    min( F(x,λ) )取得极小值时其导数为0,即▽f(x)+▽∑ni=λihi(x)=0,也就是说f(x)和h(x)的梯度共线。
    简言之,在F(x,λ)取得最优化解时,即F(x,λ)取极值(导数为0,▽[f(x,y)+λ(g(x,y)−c)]=0)时,f(x)与g(x) 梯度共线,此时就是在条件约束g(x)下,f(x)的最优化解。

    例子

    给定椭球,式子如下所示。求这个椭球的内接长方体的最大体积。
    在这里插入图片描述
    这个问题实际上就是条件极值问题,即在题目条件 下,求解 f(x,y,z)=8xyz的最大值。

    先根据条件消去 z,然后带入转化为无条件极值问题来处理。但是有时候这样做很困难,甚至是做不到的,这时候就需要用拉格朗日乘数法了。通过拉格朗日乘数法将问题转化为
    在这里插入图片描述
    接着,要对**F(x,y,z,λ)**求偏导得到
    在这里插入图片描述
    联立前三个方程得到:bx=ay、az=cx,带入第四个方程求解得到
    在这里插入图片描述
    最后,带回原式求解得到最大值,如下所示。
    在这里插入图片描述

    Python求解

    题目同刚刚所求解的例子。

    from scipy.optimize import minimize
    import numpy as np
    e = 1e-10 # 非常接近0的值
    fun = lambda x : 8 * (x[0] * x[1] * x[2]) # f(x,y,z) =8 *x*y*z
    cons = ({'type': 'eq', 'fun': lambda x: x[0]**2+ x[1]**2+ x[2]**2 - 1}, # x^2 + y^2 + z^2=1
            {'type': 'ineq', 'fun': lambda x: x[0] - e}, # x>=e等价于 x > 0
            {'type': 'ineq', 'fun': lambda x: x[1] - e},
            {'type': 'ineq', 'fun': lambda x: x[2] - e}
           )
    x0 = np.array((1.0, 1.0, 1.0)) # 设置初始值
    res = minimize(fun, x0, method='SLSQP', constraints=cons)
    print('最大值:',res.fun)
    print('最优解:',res.x)
    print('迭代终止是否成功:', res.success)
    print('迭代终止原因:', res.message)
    

    运行结果如下:
    在这里插入图片描述

    参考教程:https://www.cnblogs.com/maybe2030/p/4946256.html

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

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

    背景

    线性可分 SVM 的目标函数最终转换为一个带约束条件的求极值问题,而拉格朗日乘子法,恰恰是一种多元函数在变量受到条件约束时,求极值的方法。正好可以用来解决 SVM 的目标函数最优化。

    那么拉格朗日乘数法的理论过程如何呢?

    本文将摘录高等数学下册中拉格朗日乘数法的数学知识,08年学的高等数学下册,十多年了早还给老师了,只是还保留着当年的书本,这次春节回家把两本高数书带来了,当作AI学习的参考资料。
    在这里插入图片描述
    (百度来的图片)理工科的同学们看到它有没有觉得很亲切?

    拉格朗日乘数法

    图一

    这段话作为引言,说明多元函数求取最大值的过程中,受限于一定的条件,接下来以长方体体积的问题继续讨论。

    图二公式(1)和(2)比较好理解,分别表示我们待求取的问题的二元函数和二元函数满足的约束条件。
    图三
    这里求取了y关于自变量x的隐函数Ψ(x),那么z就转换为一元函数了。
    关于公式(5)和(2)隐函数的求导公式的知识还要再查找补充下,这里姑且就当作是已知条件吧,继续看后面的说明过程。
    图四
    (图四)

    式子(7)中的第一、三两个好理解,第二个怎么来的待解释。
    图五

    实际应用:
    在这里插入图片描述

    启示录

    从图四拉格朗日乘法的说明来看,本质上就是构造了一个拉格朗日函数,然后分别对其求偏导数,加上约束条件而得到的式子(8)本质上跟前面推导过程中的假设得到的公式(7)一致。

    我的感觉这也仅仅是一个知识点的介绍,关键的思想并没有提及:比如,为什么拉格朗日函数是关于x,y的两个函数呢?它把目标函数f(x,y)和限制函数φ(x,y)整合在一起,对求极值的意义何在?

    扩展搜索时在知乎上看到一个例子解释这个公式比较清晰的,参考链接为:https://www.zhihu.com/question/38586401/answer/134473412
    点击GIF动态图有助于更好理解推导过程。

    展开全文
  • 拉格朗日乘数法 —— 通俗理解

    万次阅读 多人点赞 2019-02-15 17:03:38
    拉格朗日乘数法(Lagrange Multiplier Method)在数学最优问题中,是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。记得以前大学高数、数模等课程多次提到过,在求解最有问题中很有用处,最近重温了...

      拉格朗日乘数法(Lagrange Multiplier Method)在数学最优问题中,是一种寻找变量受一个或多个条件所限制的多元函数极值的方法。记得以前大学高数、数模等课程多次提到过,在求解最有问题中很有用处,最近重温了下拉格朗日乘数法的思想:

      拉格朗日乘数法将一个有n个变量与k个约束条件最优化问题转换为一个有n + k个变量的方程组的极值问题,其变量不受任何约束。这种方法引入了一种新的标量未知数,即拉格朗日乘数:约束方程的梯度(gradient)的线性组合里每个向量的系数。此方法的证明牵涉到偏微分,全微分或链法,从而找到能让设出的隐函数的微分为零的未知数的值。

    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

    s.t.  xy=3

    由▽f=λ*▽g得:

      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. 拉格朗日乘数法的基本形态

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

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

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

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

    \nabla[f(x,y)+\lambda (g(x,y)-c)]=0, \lambda \neq 0

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

    F(x,y)=f(x,y)+\lambda (g(x,y)-c)

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

      上述式子取得极小值时其导数为0,即\nabla f(x)+\nabla\sum \lambda_{i} g_{i}(x)=0,也就是说f(x)和g(x)的梯度共线。

    题目1:

      给定椭球

         

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

        

      下,求的最大值。

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

         

      对求偏导得到

         

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

          

      带入解得最大体积为

          

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

    题目2:

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

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

         

         而约束条件为

         

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

         

         对所有的pk求偏导数,得到

         

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

         

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

         

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

     


    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

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

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

      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∗)梯度的线性组合。


    PS:本文转自Poll的笔记[Math & Algorithm] 拉格朗日乘数法,并更正原文几点小错误,算是对拉格朗日乘数法比较通俗的解释

    展开全文
  • 前言: 通过拉格朗日乘数法可以将原来带约束的优化问题转换为无约束的优化问题。 阅读目录1. 拉格朗日乘数法的基本思想2. 数学实例3. 拉格朗日乘数法的基本形态4. 拉格朗日乘数法与KKT条件  拉格朗日乘数法(La...
  • 最优化方法:拉格朗日乘数

    万次阅读 多人点赞 2016-08-18 14:34:38
    解决约束优化问题——拉格朗日乘数法拉格朗日乘数法(Lagrange Multiplier Method)应用广泛,可以学习麻省理工学院的在线数学课程。1. 拉格朗日乘数法的基本思想 作为一种优化算法,拉格朗日乘子法主要用于解决...
  • 约束规划——拉格朗日乘数

    千次阅读 2020-04-15 20:12:49
    拉格朗日乘数拉格朗日乘数法的基本思想 拉格朗日乘数法(Lagrange Multiplier Method)是一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束...
  • [Math & Algorithm] 拉格朗日乘数

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

    千次阅读 2016-11-19 18:39:08
    在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k...
  • 拉格朗日乘数法(Lagrange Multiplier Method)基本思想 作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的...拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导
  • 拉格朗日乘数法(Lagrange Multiplier Method)之前听数学老师授课的时候就是一知半解,现在越发感觉拉格朗日乘数法应用的广泛性,所以特意抽时间学习了麻省理工学院的在线数学课程。新学到的知识一定要立刻记录下来...
  • 拉格朗日乘数法整理

    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)受...
  • 拉格朗日乘数法及KKT条件-通俗理解

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

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 798
精华内容 319
关键字:

拉格朗日乘数的意义