拉格朗日乘子法

拉格朗日乘子法 拉格朗日乘子法几何意义？

谢邀：今晚太累了，先整理这么多，后期我会对其修改，在求解最优化问题中，拉格朗日乘子法（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个方程。

求出的方程组的解就可能是最优化值（高等数学中提到的极值），将结果带回原方程验证就可得到解。

回到上面的题目，通过拉格朗日乘数法将问题转化为 对求偏导得到 联立前面三个方程得到和，带入第四个方程解之 带入解得最大体积为： 至于为什么这么做可以求解最优化？维基百科上给出了一个比较好的直观解释。

举个二维最优化的例子： min f(x,y) s.t. g(x,y) = c 这里画出z=f(x,y)的等高线（函数登高线定义见百度百科）： 绿线标出的是约束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)的最优化解。

（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条件，推导及应用。

详细推导过程如下：参考： 【1】拉格朗日乘数法 【2】KKT条件介绍 【3】深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT条件 【4】拉格朗日乘子法和KKT条件

如果是求定义域内约束在某个区域内函数的极值, 可以用 Lagrange乘子法求约束最大值和最小值. 几何直观理解如果从几何上来理解拉格朗日乘子法呢? 咱们一个约束函数的情况吧. 先来观察下面函数 f(x,y)=49-x^2−y^2 受约束 g(x,y)=x+3y-10=0 的图形吧. f(x,y)为下面的抛物面, g(x,y) 实际为一个平面, 再次约束下求最大值就在图形中红点处; 如果没有此约束最大值就是黄点处. 再来看下面的例子, 求双曲柱面 x^2−z^2-1=0 上到原点最近的点的一个方法是设想中心在原点的球面不断膨胀, 直到刚刚接触到柱面. 此时柱面和球面有同样的切平面和法线.也来看下这个动画的过程:Lagrange 乘子法定义下面也是书中的拉格朗日乘子法的定义. 若函数 f(x,y,z) 的变量受约束 g(x,y,z)=0限制, 函数的极值可以用下面Lagrange乘子法求出.再来根据上面的定义, 看个例子. 比如求函数 f(x,y)= x y 在椭圆 x^2/8+y^2/2=1 上的最大值和最小值, 下解图形是几何解释. f(x,y)=x y 的等高线图在最下面, 也就是双曲线 x y=c(c是相应的函数值), 椭圆 x^2/8+y^2/2=1 在 f 函数曲面上为蓝色曲线. 从上图可是双曲线离开原点越远, f 的绝对值越大. 需要在约束条件下 - 椭圆 x^2+4y^2=8 上使 f(x,y) 取极值点. 也就是刚刚与椭圆相切的双曲线会距离原点最远, 在这四个切点中, 双曲线的法线也是椭圆的法线. 观察下图动画, 可以看到黑色 "▽f"是 "▽g"的数值倍数. 最大值处两个梯度向量方向相同, 最小值处方向相反. 带两个约束条件的 Lagrange 乘子法如果是两个约束限制的可微函数求极值, 这里 g1(x,y,z)=0 和 g2(x,y,z)=0, 可微且梯度向量不平行. 可以通过引进两个 Lagrange乘子 λ 和 μ, 通过求解下面方程中的 x,y,z,λ,μ 值来求出极值点的位置:曲面 g1=0 和 g2=0 通常会相交于一条曲线 C. 沿着这条曲线寻找 f 相对于曲线上其他值的极大值和极小值的点.例如下面例子中平面 x+y+z=1 (g1)相交于圆柱 x^2+y^2=1 (g2) 为一个椭圆, 求这个椭圆上离原点最远的点. 观察 ▽g1 正交于平面 x+y+z=1, 而 ▽g2 正交于曲面 x^2+y^2=1, 向量 ▽g1 和 ▽g2 位于垂直与椭圆曲线的 C (下图红色)的平面内. 并且 ▽f 也正交于 C, 且在 ▽g1 和 ▽g2 决定的平面内, 这意味这对于某个 λ 和 μ 有 ▽f = λ ▽g1 + μ ▽g2. 观察下图来更好理解:[遇见数学] 制作这几幅图片, 希望有助于各位朋友更好地理解拉格朗日乘子法. 如果感觉多少有些帮助, 还请点赞支持下, 关注今日头条[遇见数学]!