最优化⽅法：拉格朗⽇乘数法
解决约束优化问题——拉格朗⽇乘数法
拉格朗⽇乘数法（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]

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。