精华内容
下载资源
问答
  • 拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子,可将有ddd个变量与kkk个约束条件的最优化问题转化为具有d+kd+kd+k个变量的无约束优化问题求解。 先考虑一个等式约束的优化问题。...

    分类目录:《算法设计与分析》总目录
    相关文章:
    ·拉格朗日乘子法(一):等式约束的拉格朗日乘子法
    ·拉格朗日乘子法(二):不等式约束与KKT条件


    拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子,可将有 d d d个变量与 k k k个约束条件的最优化问题转化为具有 d + k d+k d+k个变量的无约束优化问题求解。即对于:
    min ⁡ f ( x ) s.t. g i ( x ) = 0 , i = 1 , 2 , ⋯   , k \begin{aligned} \min&\quad f(x)\\ \text{s.t.}&\quad g_i(x)=0\qquad ,i=1,2,\cdots,k \end{aligned} mins.t.f(x)gi(x)=0,i=1,2,,k我们定义拉格朗日函数:
    L ( x , λ ) = f ( x ) + λ i g i ( x ) L(x,\lambda)=f(x)+\lambda_ig_i(x) L(x,λ)=f(x)+λigi(x)
    我们即可将原优化问题转化为:
    ∇ X L ( x , λ ) = ∇ f + λ i ∇ g k = 0 ∇ λ L ( x , λ ) = g ( x ) = 0 \begin{aligned} \nabla_X L(x,\lambda)&=\nabla f+\lambda_i \nabla g_k=0\\ \nabla_\lambda L(x,\lambda)&=g(x)=0 \end{aligned} XL(x,λ)λL(x,λ)=f+λigk=0=g(x)=0

    先考虑一个等式约束的优化问题。假定 x x x d d d维向量,欲寻找 x x x的某个取值 x ∗ x^* x,使目标函数 f ( x ) f(x) f(x)最小且同时满足 g ( x ) = 0 g(x)=0 g(x)=0的约束。从几何角度看,该问题的目标是在由方程 g ( x ) = 0 g(x)=0 g(x)=0确定的 d − 1 d-1 d1维曲面上寻找能使目标函数 f ( x ) f(x) f(x)最小化的点。此时可以得到如下结论:

    • 对于约束曲面上的任意点 x x x,该点的梯度 ∇ g ( x ) \nabla g(x) g(x)正交于约束曲面
    • 在最优点 x ∗ x^* x,目标函数在该点的梯度 ∇ f ( x ∗ ) \nabla f(x^*) f(x)正交于约束曲面

    由此可知,在最优点 x ∗ x^* x,如下图所示,梯度 ∇ g ( x ) \nabla g(x) g(x) ∇ f ( x ∗ ) \nabla f(x^*) f(x)的方向必相同或相反,即存在 λ ≠ 0 \lambda\neq0 λ=0使得:
    ∇ f ( x ∗ ) + λ ∇ g ( x ∗ ) = 0 \nabla f(x^*) + \lambda\nabla g(x^*) =0 f(x)+λg(x)=0
    λ \lambda λ称为拉格朗日乘子,我们定义拉格朗日函
    L ( x , λ ) = f ( x ) + λ g ( x ) L(x,\lambda)=f(x)+\lambda g(x) L(x,λ)=f(x)+λg(x)
    不难发现,将其对 x x x的偏导数 ∇ x L ( x , λ ) \nabla_x L(x,\lambda) xL(x,λ)置零即得上式。同时,将其对入的偏导数 ∇ λ L ( x , λ ) \nabla_\lambda L(x,\lambda) λL(x,λ)置零即得约束条件 g ( x ) = 0 g(x)=0 g(x)=0

    等式约束
    于是,原约束优化问题可转化为对拉格朗日函数 L ( x , λ ) L(x,\lambda) L(x,λ)的无约束优化问题。

    现在我们以一个常见的例子来考虑拉格朗日乘子法。假设 x x x为2维向量,且:
    g ( x ) = x 1 2 x 2 − 3 = 0 g(x)=x_1^2x_2-3=0 g(x)=x12x23=0
    现在我们想求其上的点与原点的最短距离,即:
    min ⁡ f ( x ) = x 1 2 + x 2 2 \min f(x)=x_1^2+x_2^2 minf(x)=x12+x22
    此时,圆( f ( x ) f(x) f(x))和曲线( g ( x ) g(x) g(x))相切,也就是在该点切线相同:

    示例图

    此时 f f f梯度:
    ∇ f x 1 = 2 x 1 ∇ f x 2 = 2 x 2 \nabla f_{x_1}=2x_1 \\ \nabla f_{x_2}=2x_2 fx1=2x1fx2=2x2
    此时 g g g梯度:
    ∇ g x 1 = 2 x 1 x 2 ∇ g x 2 = x 1 2 \begin{aligned} &\nabla g_{x_1}=2x_1x_2\\ &\nabla g_{x_2}=x_1^2 \end{aligned} gx1=2x1x2gx2=x12

    梯度向量平行,我们可以写为:
    ∇ f = λ ∇ g \nabla f=\lambda \nabla g f=λg

    所以我们可得:
    ∇ f = λ ∇ g g ( x ) = x 1 2 x 2 − 3 = 0 \begin{aligned} \nabla f&=\lambda \nabla g\\ g(x)&=x_1^2x_2-3=0 \end{aligned} fg(x)=λg=x12x23=0
    我们构造拉格朗日函数:
    L ( x , λ ) = f ( x ) + λ g ( x ) L(x,\lambda)=f(x)+\lambda g(x) L(x,λ)=f(x)+λg(x)
    并利用拉格朗日乘子法即可得到与上式相同的等式:
    ∇ X L ( x , λ ) = ∇ f + λ ∇ g = 0 ∇ λ L ( x , λ ) = g ( x ) = x 1 2 x 2 − 3 = 0 \begin{aligned} \nabla_X L(x,\lambda)&=\nabla f+\lambda \nabla g=0\\ \nabla_\lambda L(x,\lambda)&=g(x)=x_1^2x_2-3=0 \end{aligned} XL(x,λ)λL(x,λ)=f+λg=0=g(x)=x12x23=0

    展开全文
  • 拉格朗日乘子法

    2021-07-27 14:09:06
    一、拉格朗日乘子法简介 拉格朗日乘子法的应用十分广泛,它是SVM的理论基础,是凸优化的重要研究部分。它用于求解约束条件下的极值问题,过程简单巧妙,也是各类考试的常考题型。然而,拉格朗日乘子法的原理我却...

    一、拉格朗日乘子法简介

    拉格朗日乘子法的应用十分广泛,它是SVM的理论基础,是凸优化的重要研究部分。它用于求解约束条件下的极值问题,过程简单巧妙,也是各类考试的常考题型。然而,拉格朗日乘子法的原理我却一直模模糊糊,每次看的时候才知道,一段时间不看就又忘了,所以特地写这篇博客来供自己时刻学习。

    先从一个简单的例子开始:

    假如我们需要求一个函数的最小值,即约束条件为。我们用拉格朗日乘子法来求解:

     首先用描述约束条件,即

    而后引入拉格朗日乘子λ,并构造一个新的函数:

    因为,于是,因此当取得极小值时有:

          (1)

    于是得到: =>

    即当==1时,取得最小值,最小值为2。这就是拉格朗日乘子法求解过程。

    拉格朗日乘子法非常巧妙,但其中的原理却难以琢磨,从几何角度观察,我们可以更加直观地理解拉格朗日乘子法的原理以及这个乘子λ的几何含义。

    首先我们观察约束条件,在平面上是一条直线如下图中的蓝色直线所示。

     再看,令这表示的某一条等高线,随着r的改变我们得到了多条等高线,在上图中以绿色圆圈表示。

    在图中,如果某一条等高线与直线相交,则表示在的约束条件下,可以取到r的值。为了求得的最小值,在保证绿色圆圈与蓝色直线有交点的前提下,逐渐将r缩小,直到绿色等高线圆小到与蓝色直线相切,此时r0最小,我们认为获得了最小值

     

     

    下面我们来计算,在图中我们看到等高线圆与约束直线相切。此时在切点处,等高线圆与约束直线具有相同的切线方向与法线方向。

    又因为等高线f的切线方向与在该点的梯度方向相互正交,于是的法线方向即是的梯度方向,而该梯度方向为

    同理直线的法线方向也就是的梯度方向

    在切点处GfGg的方向相同,即相切。那么f ( x ) g ( x ) 在这一点的梯度一定是成比例的(具体理解起来就是法向量一定成比例)。

    因此我们引入乘子λ,并且有

      =>    2

    上式与式(1)相同。这个方程组总共包含n + 1个方程(梯度是一个向量,梯度等于0必须每一维都为0),恰好可以解出所有的λ ​    

    到此我们也已经获得了与拉格朗日乘子法相一致的结论。于是我们从几何角度解释了拉格朗日乘子引入的过程,也验证了拉格朗日乘子法的结论。

    二、拉格朗日乘子法求解带等式约束的最优化问题

    拉格朗日求得的并不一定是最优解,只有在凸优化的情况下,才能保证得到的是最优解,所以我们说拉格朗日乘子法得到的为可行解,其实就是局部极小值。

    1、构造拉格朗日函数

    之所以这样构造的原理我们可以继续看上面式(2,我们把式子的右边移到左边,并把常数移进微分算子,得到:

    把这个式子重新解释一下,这个就是函数无约束条件下极值点的充分条件。

    2、构造完之后就可以分别对参数求偏导,并令其等于0,就能解出无约束极值和极值所对应的点。

    三、引入KKT条件求带不等式约束条件的最优化问题

    所谓的KKT条件,是指对一类符合条件的所有拉格朗日乘子法问题进行公式化求解的过程。在机器学习中,我们解决的问题一般最后都化为目标函数最优化问题,即转化为在给定约束条件下最大或最小化目标函数。

    约束条件会有一般包括以下三类:

    1)仅含等式约束

    2)仅含不等式约束

    3)等式和不等式约束混合型

    当然还有一类没有任何约束条件的最优化问题。仅含等式约束的目标函数不再赘述。

    对于不等式约束g(x)<=0,和等式约束h(x)=0不一样,h(x)=0可以在平面上画出一条等高线,而g(x)<=0是一个区域,很多个等高线堆叠而成的一块区域,我们把这块区域称为可行域。

    不等式约束分两种情况来讨论,第一种是原有函数的(不考虑可行域限制时的)极值点落在可行域内(不包含边界),第二种是原有函数的(不考虑可行域限制时的)极值点落在可行域外(包含边界)。

    下面举两个例子来解释这两种情况,然后总结两种情况给出转换求解。

    (一)带不等式约束条件的最优化

    在有不等式g(x)<=0的约束下,可行解 x 只能在 g(x)<0 或者 g(x)=0 的区域里取得:

    当可行解 x 落在 g(x)<0 的区域内,此时直接极小化 f(x) 即可;

    当可行解 x 落在 g(x)=0 即边界上,此时等价于等式约束优化问题.

    case1:当约束区域包含目标函数原有的的可行解时,此时加上约束可行解仍落在约束区域内部,对应 g(x)<0 的情况,这时约束条件不起作用;

    现在我们假设问题是:,其中

     我们很容易知道f(x)的最小值在(00),等高线如下图:

    接下来我们画上g(x1,x2)限制的可行域(以(00)为圆心,半径为1的圆型区域,包括边界):

    很明显这个约束并不起作用,函数f(x1,x2)的极值点不变,这种情况约束不起作用,考虑极小值点x*,这个时候,g(x*) < 0f(x*)的梯度等于0

    case2:当约束区域不包含目标函数原有的可行解时,此时加上约束后可行解落在边界 g(x)=0 上。下面我们考虑另外一个不等式约束下的问题:,其中

    我们可以看一下这个问题的等高线情况:

    以上两种情况就是说,要么可行解落在约束边界上即得 g(x)=0,要么可行解落在约束区域内部,此时约束不起作用,令 λ=0 消去约束即可,所以无论哪种情况都会得到λ(也就是KKT条件的其中之一)。

    还有一个问题是 λ 的取值,在等式约束优化中,约束函数与目标函数的梯度只要满足平行即可,而在不等式约束中则不然,若 λ≠0,这便说明 可行解 x 是落在约束区域的边界上的,这时可行解应尽量靠近无约束时的解,所以在约束边界上,目标函数的负梯度方向应该远离约束区域朝向无约束时的解,此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同:

    上式需要满足的要求是拉格朗日乘子 λ>0

    (二)满足KKT条件

    可见对于不等式约束,只要满足一定的条件,依然可以使用拉格朗日乘子法解决,这里的条件便是 KKT 条件。

    对于如下:

    我们定义的拉格朗日函数:

    这时,KKT条件如下:

    满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多,其实很好理解:

    1) 拉格朗日取得可行解的必要条件;

    2) 这就是以上分析的一个比较有意思的约束,称作松弛互补条件;

    34) 初始的约束条件;

    5) 不等式约束的 Lagrange Multiplier 需满足的条件

    (三)原最优化问题转对偶问题

    每个线性规划问题都有一个与之对应的对偶问题,对偶问题有非常良好的性质,以下列举几个:

    1)对偶问题的对偶是原问题;

    2)无论原始问题是否是凸的,对偶问题都是凸优化问题;

    3)对偶问题可以给出原始问题一个下界;

    4)当满足一定条件时,原始问题与对偶问题的解是完全等价的;

    任何满足强对偶性的优化问题,只要其目标函数与约束函数可微,任一对原始问题与对偶问题的解都是满足 KKT 条件的。即满足强对偶性的优化问题中,若x*为原始问题的最优解,α* ,β* 为对偶问题的最优解,则可得 x*,α*,β* 满足 KKT 条件。

    当原始问题是凸优化问题,且存在x*,α*,β*满足 KKT 条件,那么它们分别是原始问题和对偶问题的极值点并且强对偶性成立。

    当满足KKT条件时, f(x)是等价的。

     

    因此我们的目标函数可以写为:

    如果用对偶表达式: 由于我们的优化是满足强对偶的(满足KKT条件),强对偶就是说对偶式子的最优值是等于原问题的最优值的,所以在取得最优值 x 的条件下,它满足:

    我们来看看中间两个式子发生了什么事情:

    可以看到上式本质上是说 x 取得了最小值,对于函数 f(x)+ag(x)+bh(x),求取导数要等于零,即

    这就是KKT条件中第一个条件:

    所有上述说明,满足强对偶条件的优化问题的最优值都必须满足KKT条件,也就是说当满足KKT条件时原始问题与其对偶问题具有相同的最优解。

    参考网址:

    https://www.cnblogs.com/jason-wyf/p/6727524.html

    https://blog.csdn.net/Laurel1115/article/details/88238944

    https://blog.csdn.net/weixin_44273380/article/details/109016774

    展开全文
  • 在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。  我们这里提到的最优化问题...

    在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。

      我们这里提到的最优化问题通常是指对于给定的某一函数,求其在指定作用域上的全局最小值(因为最小值与最大值可以很容易转化,即最大值问题可以转化成最小值问题)提到KKT条件一般会附带的提一下拉格朗日乘子。对学过高等数学的人来说比较拉格朗日乘子应该会有些印象。二者均是求解最优化问题的方法,不同之处在于应用的情形不同。

          一般情况下,最优化问题会碰到一下三种情况:

    (1)无约束条件

      这是最简单的情况,解决方法通常是函数对变量求导,令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。

    (2)等式约束条件

          设目标函数为f(x),约束条件为h_k(x),形如:

            s.t. 表示subject to ,“受限于”的意思,l表示有l个约束条件。

            

       则解决方法是消元法或者拉格朗日法消元法比较简单不在赘述,这里主要讲拉格朗日法,因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。

       例如给定椭球:

                   

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

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

        首先定义拉格朗日函数F(x):

              ( 其中λk是各个约束条件的待定系数。)                                                           

            然后解变量的偏导方程:

              ......,

       如果有l个约束条件,就应该有l+1个方程。求出的方程组的解就可能是最优化值(高等数学中提到的极值),将结果带回原方程验证就可得到解。

       回到上面的题目,通过拉格朗日乘数法将问题转化为

             

       对求偏导得到

              

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

              

       带入解得最大体积为:

              

      

     

    (3)不等式约束条件

           设目标函数f(x),不等式约束为g(x),有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下:

            

            则我们定义不等式约束下的拉格朗日函数L,则L表达式为:

            

          其中f(x)是原目标函数,hj(x)是第j个等式约束条件,λj是对应的约束系数,gk是不等式约束,uk是对应的约束系数。

      常用的方法是KKT条件,同样地,把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a, b, x)= f(x) + a*g(x)+b*h(x),

      KKT条件是说最优值必须满足以下条件:

        1)L(a, b, x)对x求导为零;

        2)h(x) =0;

        3)a*g(x) = 0;

     

      求取这些等式之后就能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0. 这是SVM的很多重要性质的来源,如支持向量的概念。

      接下来主要介绍KKT条件,推导及应用。详细推导过程如下:

     

    ????从几何角度看拉格朗日乘子法的物理意义:

     


          该方法适用于约束条件下求极值的问题。对于没有约束的极值问题,显然,如果某一点是极值的必要条件是该点的各方向的偏导数皆为零,也就是说,如果偏导数不全为零,那么就不可能是极值。

    例如,一个三元函数w(x,y,z), 它是x,y,z的函数,且在一个约束条件下求它的极值。我们假设图中的曲面就是约束方程g(x,y,z)=0的图像,即约束面。之前没有约束面时,w取极值的必要条件是各个方向偏导数为零,而对于可微函数各个方向偏导为零的充分必要条件是沿x,y,z 方向的偏导为零。现在有了约束面,我们不再需要这么苛刻的必要条件,因为有了约束面,x,y,z在一定程度上被限制了,只能在约束面内移动,因此只需要沿约束面内的各个方向运动时的偏导数(变化化率)为零就可以了,此时自由度由三维下降到两维。满足在约束面内的各个方向偏导为零,也就是说,w取极值的必要条件减弱为待求函数的方向导数(梯度)垂直于约束面,从数学上看,也就是方向导数和约束面的法线方向同向(一个向量等于另一个向量的常数倍),而不需要梯度为零,因为和梯度垂直的方向偏导数一定为零,这样,沿约束面各个方向运动时w的偏导数也就为零了。这便是拉格朗日乘子法求极值的几何意义。

     

    个人总结:

    想象一下我们爬山(优化函数)找最高点(求最大值),要想最快的上,要找最陡的方向,陡峭的程度以坡度(方向导数)度量,最陡的方向即为最大坡度(梯度)决定的方向,理想情况下,当无法再上升,坡度(梯度)变成0时,找到最高点(求得最大值)。但是,当我们必须绕圆弧行盘山路爬行时,盘山路(约束条件)约束了我们的路径及方向,我们必须沿着盘山路最陡的方向(梯度,注意此时退化为一维,只有一个方向,为道路切向),当道路不再上升(及切向为0),即找到最高点。

    再想想一下我们是海水,从山底向上移动(集体作战),领袖沿着盘山路行进,每一步我们可以找到同海拔的海岸线(等高线),海岸线与盘山路想交,我们可以继续向上移动,直到海岸线与盘山路向切,此时,找到最高海拔,海岸线(等高线)同时与约束方程确定的边界相切。

    在极值点,优化函数的等高线、优化函数与约束方程的交线、约束方程的投影线(类似约束曲面的等高线,约束曲线)相切于一点。等高线与约束曲线法向相同(不考虑正负),而优化函数的梯度数值等于其等高线的法向数值约束方程的梯度数值等于约束曲线的法向数值。故∆f=λ∆g,λ!=0

    极值点的2个条件:

    1、极值点在优化函数及约束方程上;

    2、在极值点,优化函数的等高线、优化函数与约束方程交线、约束曲线相切,优化函数与约束方程交线的梯度(导数)为0

    可利用这2个条件求解:

    一、根据1将约束方程带入优化函数消元、降维变成无约束低维问题求解,根据2求梯度为0

    二、根据2构造似然函数L(X,λ),使在特殊条件下满足1和2,对L(X,λ)解特殊条件。

     

    展开全文
  • 1. 拉格朗日乘子法 这个问题我们之前涉及到过,在机器学习实战(基于scikit-learn和TensorFlow)学习心得(23)--逻辑回归 Logistic Regression的时候我们把带约束条件的方程通过拉格朗日乘子法合并为了一个方程. ...

    1. 拉格朗日乘子法

    这个问题我们之前涉及到过,在机器学习实战(基于scikit-learn和TensorFlow)学习心得(23)--逻辑回归 Logistic Regression的时候我们把带约束条件的方程通过拉格朗日乘子法合并为了一个方程.

    拉格朗日乘子法具体是什么样的呢?

    我们看这么一个式子

    在下面两个约束条件的情况下求得f的最小值.求最小值其实就是求偏导数等于0的点.如果只考虑上面的式子因为都是平方项所以最小值是0,而取得最小值的点是(0,0,0),但是显然(0,0,0)并不满足与下面两个约束条件.那如果我们想用梯度法求解极值问题我们就必须想办法把下面的约束条件揉到上面的f中,也就是我们要根据下面的约束条件重新构造一个f.

    这时候我们就要用拉格朗日乘子法了.

    具体做法是这样的首先我们把两个等式约束条件加一个系数加到f中

    f=2x_{1}^{2}+3x_{2}^{2}+7x_{3}^{2}+\alpha _{1}(2x_{1}+x_{2}-1)+\alpha _{2}(2x_{2}+3x_{3}-2)

    接着我们分别对x1,x2,x3求偏导数得到

    \\ \frac{\partial f}{\partial x_{1}}=4x_{1}+2\alpha_{1}\\ x_{1}=-0.5\alpha_{1}\\ \frac{\partial f}{\partial x_{2}}=6x_{2}+\alpha_{1}+2\alpha_{2}\\ x_{1}=\frac{-\alpha_{1}+2\alpha_{2}}{6}\\ \frac{\partial f}{\partial x_{3}}=14x_{3}+3\alpha_{2}\\ x_{1}=\frac{-3\alpha_{2}}{14}

    将x1,x2,x3带回到约束条件中

    \left\{\begin{matrix} 2x_{1}+x_{2}=1 \\ 2x_{2}+3x_{3}=2 \end{matrix}\right. \Rightarrow \left\{\begin{matrix} -\alpha_{1}+\frac{-\alpha_{1}+2\alpha_{2}}{6}=1 \\ \frac{-\alpha_{1}+2\alpha_{2}}{3}+\frac{-9\alpha_{2}}{14}=2 \end{matrix}\right.\Rightarrow \left\{\begin{matrix}\alpha_{1}=-\frac{54}{7}{}\\\alpha_{2}=-24\end{matrix}\right.

    我们求出了α1和α2,然后我们把α1和α2代到f=2x_{1}^{2}+3x_{2}^{2}+7x_{3}^{2}+\alpha _{1}(2x_{1}+x_{2}-1)+\alpha _{2}(2x_{2}+3x_{3}-2)这个式子中我们就可以求出来添加了约束项之后的f了

    换句话说

    f=2x_{1}^{2}+3x_{2}^{2}+7x_{3}^{2}+\alpha _{1}(2x_{1}+x_{2}-1)+\alpha _{2}(2x_{2}+3x_{3}-2)

    是等价的!

    接下来再说说这么做的物理意义. 

    我们先看这样一组约束问题

    min \quad f=x_{1}^2+ x_{2}^2 \\ s.t. \quad h_{1}(x_{1},x_{2}):x_{1}+x_{2}+1=0

    我们先来分析f这个函数,这个函数的等值线是如下图所示的同心圆.

    我们再看h1这个函数的图相,看这个函数的图相的时候我们先不要考虑h1=0这种情况,只是单纯的做出h1=x1+x2+1这个函数的等值线

    可以看出来,h1这个函数的等值线的情况如上图所以,其中绿色的直线是h1在h1=0的情况下的等值线,也就是我们的约束条件.

    现在这个问题就简单多了,我们为什么要求梯度?直线的梯度怎么求?这些问题迎刃而解.其实约束条件并不是代表一条简单的直线,他代表的是一个高维函数在0这个取值点上的等值线而已,只是这个等值面恰巧是一条直线,那么h1=x+y+1这个函数的三维图相是什么样的呢?

    好了,现在我们再研究一下等值线切线与梯度的方向关系

    如上图所示,等值线在某个点(x*,y*)的梯度与该等值线在此点处的导数相互垂直.

    知道了这个性质我们再看这个问题.

    我们再回忆一下相切的定义,一条直线与圆相切意味着在切点(x*,y*)处,圆的斜率等于直线的斜率.

    如上图所示,αᐁh与切线t互相垂直,ᐁf与切线t互相垂直,则αᐁh与ᐁf共线.再求梯度的方向,对于f(x1,x2)来说

    \bigtriangledown f(x_{1},x_{2})=2x_{1}+2x_{2}则在点(x,y)处其梯度方向为(x,y)[在这个具体问题中f(x)在点(-0.5,-0.5)处其梯度方向为(-0.5,-0.5)]

    对于h1(x1,x2)来说

    \bigtriangledown h_{1}(x_{1},x_{2})=(1,1)则在点(x,y)处其梯度方向为(1,1)

    可见两个梯度方向相反

    \bigtriangledown f(x_{1},x_{2})=-\alpha\bigtriangledown h_{1}(x_{1},x_{2})

    好,我们现在来回头说我们到底想用拉格朗日乘子法干什么?

    假设我们有一个带等式约束的方程想求极值点,但是我们不想要这个约束项,我们想通过f(x)与h(x)构建一个新的方程L(x),使得这个单一的不带约束条件的L(x)可以等价的替代原有的f(x),那么这个L的极值点就得在在原有约束条件下f(x)的极值点上.就如上图所示,上图中黑点是

    min \quad f=x_{1}^2+ x_{2}^2 \\ s.t. \quad h_{1}(x_{1},x_{2}):x_{1}+x_{2}+1=0

    该问题的极值点,我们新构建的函数L的极值点也得在这个黑点上!那么我们就要确保我们新构建的函数L在该黑点上的梯度是0.

    我们已证得

    \bigtriangledown f(x_{1},x_{2})=-\alpha\bigtriangledown h_{1}(x_{1},x_{2})

    那么

    \bigtriangledown f(x_{1},x_{2})+\alpha\bigtriangledown h_{1}(x_{1},x_{2})=0

    \bigtriangledown L(x_{1},x_{2})=\bigtriangledown f(x_{1},x_{2})+\alpha\bigtriangledown h_{1}(x_{1},x_{2})=0

    这个ᐁL是符合我们要求的在(x1,x2)这个点上梯度为0的其中一个式子

    反过来求解

    L(x_{1},x_{2})=f(x_{1},x_{2})+\alpha h_{1}(x_{1},x_{2})

    说明L(x)是符合我们要求的一个函数

    接下来我们来说说多项等式约束的情况

    .min \quad f=x_{1}^2+ x_{2}^2 \\ s.t. \quad h_{1}(x_{1},x_{2}):x_{1}+x_{2}+1=0\\ h_{2}(x_{1},x_{2}):x_{1}-x_{2}-1=0

    我们还是先看图是怎么样的

    因为有两个等式约束条件,所以说我们可能的取值点必须在两个等值线的焦点上.

    可以看到,这时极点的位置已经确定,那么经过这个极点的f(x)的等高线就确定了.但跟上面单约束的相比这次的圆等高线无法与两个约束函数的等高线相切了.但性质还是没有变,目的也没有变,我们还是要构建一个新的函数L(x)使这个函数在交点(极值点)处的导数为0.

    如上图所示,原则还是一样的,我们可以画出三个函数在交点(x1,x2)处的梯度方向,我们要想使新的函数L(x)在该交点处的梯度为0(该交点为L(x)的极值点)我们只需要将ᐁh1与ᐁh2进行线性结合使得他们的和向量α1ᐁh1+α2ᐁh2与ᐁf在(x1,x2)处的大小相等方向相反即可

     

    \triangledown f(x_{1},x_{2})=-(\alpha_{1} \triangledown h_{1}(x_{1},x_{2})+\alpha_{2} \triangledown h_{2}(x_{1},x_{2}))

     

    如同上面单约束一样

    那么

    \bigtriangledown f(x_{1},x_{2})+\alpha_{1}\bigtriangledown h_{1}(x_{1},x_{2})+\alpha_{2}\bigtriangledown h_{2}(x_{1},x_{2})=0

    \bigtriangledown L(x_{1},x_{2})=\bigtriangledown f(x_{1},x_{2})+\alpha_{1}\bigtriangledown h_{1}(x_{1},x_{2})+\alpha_{2}\bigtriangledown h_{2}(x_{1},x_{2})=0

    这个ᐁL是符合我们要求的在(x1,x2)这个点上梯度为0的其中一个式子

    反过来求解

    L(x_{1},x_{2})=f(x_{1},x_{2})++\alpha_{1} h_{1}(x_{1},x_{2})+\alpha_{2} h_{2}(x_{1},x_{2})

    说明L(x)是符合我们要求的一个函数

    对于更多等式约束条件也是一样的.

     

    2.KKT条件

    上面的过程只适用于等式的约束条件,如果碰到了不等式的约束条件怎么办?这时我们就要用KKT条件了

    那我们先讨论如果约束条件中有一个不等式的情况.

    当约束条件只有一个不等式的时候可能的情况有两种.f(x)的最优解在限制条件之内,如下图所以,也就是左边的灰色阴影部分的已经包含了最优解了,在这种情况下不等式g(x)的约束条件等同于没有.

     

      

    第二种情况就是f(x)的极值点不在等式g(x)的约束范围内,则不等式g(x)<0的约束条件等同于g(x)=0的约束条件,使用单纯的拉格朗日乘子法就可以求解了.

    根据上面这两种情况,我们可以总结出KKT条件

    对于

    \\min \quad f(x,y)\\ s.t. \quad g(x,y)<0 \\ \ h(x,y)=0

    的问题下

    其解的KKT条件为

     

    \left\{\begin{matrix} \bigtriangledown L=0 \\ g(x,y)< 0 \\ h(x,y)=0 \\ \alpha\geq 0 \\ \alpha g(x,y)=0 \end{matrix}\right.

    我们来一个一个讨论这些条件,

     

    条件1:\bigtriangledown L=0

    这个条件就跟等式约束一样,话句话说就是在极点位置原函数梯度与约束函数梯度的线性组合方向相反.

     

    条件2:g(x,y)< 0

    约束条件,得到的极值点一定要符合这个约束.关于小于零这点其实无所谓,我们只是为了统一写法,任何一个大于0的不等式都可以转换为小于0的不等式(x+y>0  === -x-y<0)

     

    条件3:h(x,y)=0

    同样是约束条件,得到的极值点也要符合这个约束.

     

    条件4:\alpha\geq 0

    这个条件可以说是十分关键的一个条件了.我们来说说为什么需要\alpha\geq 0,首先\alpha\geq 0意味着什么?我们来看我们公式的初始情况,假设

    首先我们先看g(x,y)< 0

    上图蓝色的阴影代表了g(x,y)< 0的区域,也就可行域,可以看到可行域已经包含了f(x)的极值点了(0,0),所以说此不等式约束应该不起作用.那么在这种不起作用的情况下如果我们还算切点就会出错.

    我们来看在这种情况下我们要是强行把切点当成我们要求的极值点会发生什么事情.

    首先我们先要明确,梯度的方向是函数增大的方向,由于我们之前已经把g(x)设置成小于0了(g(x)<0),那么其梯度一定是指向不可行域的.

    那由于g(x)已经包含了f(x)的极值点所以说f(x)在此点上的梯度方向一定也是指向不可行域的

    也就是说在可行域已经包含了f(x)极值的情况下,若想使下面的方程成立

    \bigtriangledown f(x_{1},x_{2})=-\alpha\bigtriangledown h_{1}(x_{1},x_{2})

    则α必须<0

    也就是说在α≥0的情况下要想使该等式成立则前提条件是f(x)的极值点不能在不等式约束g(x)的可行域内.

    下面我们来考虑两个不等式约束的情况

    根据上面单不等式约束的结果,如果说任意一个不等式的可行域包含了f(x)的极值点则在g(x)的边界上(g(x)=0的那条线上)ᐁg(x)与ᐁf(x)的夹角必定是锐角(按照上面的图来看,因为g(x)包含了f(x)的极值点(0,0),所以在两个点的切点上ᐁf(x)与ᐁg(x)一定是同一个方向的,换句话说它们之间的夹角一定是锐角)

     

    我们先从线性结合入手

    假设我们有v1,v2两个向量,我们想用这两个向量的线性组合a*v1+b*v2来组合出g1,g2,g3,g4,然后我们来讨论一下a与b的取值问题

    g1: a>0,b>0

    g2: a<0,b>0

    g3: a<0,b<0

    g4: a>0,b<0

    上面看了,如果我们想确认两个可行域都不包括f(x)的极值点的话我们就得保证每一个α都是正数,

    假设两个不等式约束g1(x),g2(x),其中g(1)的可行域包含f(x)的极值点,g2(x)的可行域不包含f(x)的极值点

    我们开始构建函数L

    L(x)=f(x)+\sum \alpha g(x)

    \triangledown L(x)=\triangledown f(x)+\sum \alpha \triangledown g(x)

    我们要使在交点处的梯度向量和为0

    \triangledown f(x)+\sum \alpha \triangledown g(x)=0

    \triangledown f(x)=-\sum \alpha \triangledown g(x)

    \triangledown f(x)=-\alpha_{1} \triangledown g_{1}(x)-\alpha_{2} \triangledown g_{2}(x)

    那根据上面的线性结合特性,α1>0,α2<0

    同理,如果g1(x)和g2(x)的可行域全都包含f(x)的极值点,则要想使新函数L在交点处的梯度为0的话 α1<0,α2<0

    所以说只有当α1>0,α2>0的时候我们才能保证g1(x),g2(x)的可行域都不包括f(x)的极值点.

    所以说扩展到高维度的话,我们就要保证\alpha\geq 0

     

    条件5:\alpha g(x,y)=0

    图一

    图二

    若g(x,y)起到了约束作用(如图一一样,可行域没有覆盖f(x,y)的极值点)则g(x,y)=0 但α≠0

    若g(x,y)没有起到约束作用(如图二,可行域覆盖到了f(x,y)的极值点)则g(x,y)≠0 但α=0

    所以不管怎么样,\alpha g(x,y)=0

     

    最后看一个例子

    我们想求当α取不同值的时候的情况

    则KKT方程组为

    解方程

    ,

    将x1,x2带入到约束中

    得出

    带回到x1,x2中得

    下面将x2带入到不等式约束中

    整理得

    最后通过μ≥0求解α的取值范围

    1. 若α>0.5则μ<0,说明不等式约束没有起作用,然后我们把μ置为0,按照等式拉格朗日乘子法求解λ的参数最后得出极值点在(0.5,0.5)

    2.若α=0.5则μ=0跟上面一样

    3.若α<0.5则μ>0,不等式约束条件起作用了,我们直接把g(x)置为0也就是x2-α=0,然后按照双等式约束的拉格朗日乘子法求解最优值得到点(1-α,α)

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 拉格朗日乘子法、罚函数法、乘子罚函数法

    万次阅读 多人点赞 2017-10-24 14:14:56
    拉格朗日乘子法 1 无约束问题 2 等式约束问题 3 不等式约束问题KTT条件 罚函数法 1 定义 2 内罚函数法 3 外罚函数法 增广拉格朗日乘子法 1 定义 2 求解 本文简单总结一些相关概念,具体证明以后再补充; 1. ...
  • 不等式拉格朗日乘子大于0 的解释

    千次阅读 2014-06-04 09:58:15
    一直郁闷与这点:在一本书上看到先关内容  是:《nonlinear programming》 ...就是说从边际价格的角度来看,随着active 约束的松弛,可行域增大,总得费用会减小,拉格朗日乘子代表的边际价格会增大。
  • 1. 拉格朗日乘子法用于最优化的原因 2. 最优化问题三种情况 2.1 无约束条件 2.2 等式约束条件:拉格朗日乘子法 2.3 不等式约束条件:KKT 3. Lagrange对偶函数 3.1对偶函数与原问题的关系 3.2 Lagrange对偶...
  • 拉格朗日乘子法的证明

    千次阅读 2017-06-19 09:02:34
    在学习支持向量机的时候,计算对偶问题时用到了拉格朗日乘子法((Lagrange multiplier method)),回想起高中时使用拉格朗日乘子法不等式约束条件下的最优化问题时的困惑,虽然一直知道用,但是却不知道为什么...
  • 拉格朗日乘子法和KKT条件 @(learning) 参考: 解密SVM系列(一):关于拉格朗日乘子法和KKT条件 深入理解拉格朗日乘子法(Lagrange Multiplier) 和KKT条件 拉格朗日乘子法 在求取有约束条件的优化问题时,拉格朗日...
  • 约束优化方法之拉格朗日乘子法与KKT条件

    千次阅读 多人点赞 2018-04-15 15:31:51
    PS:以下来自人工智能头条公众号,支持向量机部分约束问题分为等式约束和不等式约束,对于等式约束问题我们可以直接采用拉格朗日乘子法来解决,对于含有不等式约束的优化问题,可以转化为在满足 KKT 约束条件下应用...
  • 拉格朗日乘子法和KKT

    2018-09-22 10:42:18
    拉格朗日乘子法和KKT
  • 拉格朗日乘子法及KKT条件

    千次阅读 2017-03-26 20:00:51
    前言最近在学习SVM的时候发现想要了解SVM的前提是必须得了解拉格朗日乘子法和KKT条件。为此,在花时间了解了拉格朗日乘子法和KKT条件之后在此说说自己的理解,顺便记录下自己的学习过程。 第一次接触拉格朗日乘子法...
  • 遇到此类问题时,老师们往往告诉我们使用拉格朗日乘子法解决!它的应用十分广泛,如支持向量机,线性规划等。那么,拉格朗日乘子法到底是什么?它背后的数学原理又是怎样的?本篇博客将为您一一解答。注意,本篇博客...
  • 拉格朗日乘子法2.python --拉格朗日乘子法3.python sympy包 --拉格朗日乘子法 1.拉格朗日乘子法 题目如下:等式约束下的拉格朗日乘子法求解过程 2.python --拉格朗日乘子法 题目如上: from scipy.optimize ...
  • 本文主要对拉格朗日乘子法进行总结,具体原理可以参考这两篇文章: 友情链接 1 友情链接 2 如果你对这篇文章可感兴趣,可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」,查看完整博客分类与对应...

空空如也

空空如也

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

不等式拉格朗日乘子法