拉格朗⽇数乘法
拉格朗⽇乘数法（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 f x=λ*g x，
f y=λ*
g y，
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的斜率平⾏。
▽[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)+▽∑λi g i(x)=0，也就是说f(x)和g(x)的梯度共线。
题⽬1：
给定椭球
求这个椭球的内接长⽅体的最⼤体积。这个问题实际上就是条件极值问题，即在条件
下，求的最⼤值。
当然这个问题实际可以先根据条件消去，然后带⼊转化为⽆条件极值问题来处理。但是有时候这样做很困难，甚⾄是做不到的，这时候就需要⽤拉格朗⽇乘数法了。通过拉格朗⽇乘数法将问题转化为
对求偏导得到
联⽴前⾯三个⽅程得到和，带⼊第四个⽅程解之
带⼊解得最⼤体积为
拉格朗⽇乘数法对⼀般多元函数在多个附加条件下的条件极值问题也适⽤。
题⽬2：
题⽬：求离散分布的最⼤熵。
分析：因为离散分布的熵表⽰如下
⽽约束条件为
要求函数的最⼤值，根据拉格朗⽇乘数法，设
对所有的求偏导数，得到
计算出这个等式的微分，得到
这说明所有的都相等，最终解得
因此，使⽤均匀分布可得到最⼤熵的值。
4. 拉格朗⽇乘数法与KKT条件
我们上述讨论的问题均为等式约束优化问题，但等式约束并不⾜以描述⼈们⾯临的问题，不等式约束⽐等式约束更为常见，⼤部分实际问题的约束都是不超过多少时间，不超过多少⼈⼒，不超过多少成本等等。所以有⼏个科学家拓展了拉格朗⽇乘数法，增加了KKT条件之后便可以⽤拉格朗⽇乘数法来求解不等式约束的优化问题了。
⾸先，我们先介绍⼀下什么是KKT条件。
KKT条件是指在满⾜⼀些有规则的条件下, ⼀个⾮线性规划(Nonlinear Programming)问题能有最优化解法的⼀个必要和充分条件. 这是⼀个⼴义化拉格朗⽇乘数的成果. ⼀般地, ⼀个最优化数学模型的列标准形式参考开头的式⼦, 所谓 Karush-Kuhn-Tucker 最优化条件，就是指上式的最优点x∗必须满⾜下⾯的条件:
1). 约束条件满⾜g i(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q
2). ∇f(x∗)+∑i=1μi∇g i(x∗)+∑j=1λj∇h j(x∗)=0, 其中∇为梯度算⼦;
3). λj≠0且不等式约束条件满⾜μi≥0,μi g i(x∗)=0,i=1,2,…,p。
KKT条件第⼀项是说最优点x∗必须满⾜所有等式及不等式限制条件, 也就是说最优点必须是⼀个可⾏解, 这⼀点⾃然是⽏庸置疑的. 第⼆项表明在最优点x∗, ∇f必须是∇g i和∇h j的线性組合, μi和λj都叫作拉格朗⽇乘⼦. 所不同的是不等式限制条件有⽅向性, 所以每⼀个μi都必须⼤于或等于零, ⽽等式限制条件没有⽅向性，所以λj没有符号的限制, 其符号要视等式限制条件的写法⽽定.
为了更容易理解，我们先举⼀个例⼦来说明⼀下KKT条件的由来。
∵μk≥0 g k(x)≤0 => μg(x)≤0
∴maxμL(x,μ)=f(x) (2)
∴min x f(x)=min x maxμL(x,μ) (3)
⼜
麻省理工申请条件 此时
联合(3),(4)我们得到min x maxμL(x,μ)=maxμmin x L(x,μ), 亦即
min x maxμL(x,μ)=maxμmin x L(x,μ)=min x f(x)
我们把maxμmin x L(x,μ)称为原问题min x maxμL(x,μ)的对偶问题，上式表明当满⾜⼀定条件时原问题、对偶的解、以及min x f(x)是相同的，且在最优解x∗处μ=0 or g(x∗)=0。把x∗代⼊(2)得maxμL(x∗,μ)=f(x∗)，由(4)得maxμmin x L(x,μ)=f(x∗)，所以
L(x∗,μ)=min x L(x,μ)，这说明x∗也是L(x,μ)的极值点，即
最后总结⼀下：
KKT条件是拉格朗⽇乘⼦法的泛化，如果我们把等式约束和不等式约束⼀并纳⼊进来则表现为：
注：x,λ,μ都是向量。
表明f(x)在极值点x∗处的梯度是各个h i(x∗)和g k(x∗)梯度的线性组合。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论