跳至主要内容

拉格朗日乘数 - 维基百科，自由的百科全书


2013年维基媒体国际会议正式会议于8月11日在香港闭幕。
[关闭]



拉格朗日乘数[编辑]
维基百科，自由的百科全书

微积分学
\text{e} = \lim_{n\to\infty} \left(1+\frac{1}{n}\right)^n
函数 · 导数 · 微分 · 积分
显示▼基础概念
显示▼一元微分
显示▼一元积分
显示▼多元微积分
显示▼微分方程
显示▼数学家
图1：绿线标出的是约束g(x,y) = c的点的轨迹。蓝线是f的等高线。箭头表示斜率，和等高线的法线平行。
在数学最优化问题中，拉格朗日乘数法（以数学家约瑟夫·拉格朗日命名）是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k个变量的方程组的极值问题，其变量不受任何约束。这种方法引入了一种新的标量未知数，即拉格朗日乘数：约束方程的梯度（gradient）的线性组合里每个向量的系数。
简单举例：
最大化 f(x, y) \,
受限于 g(x, y) = c.\,
引入新变量拉格朗日乘数\lambda，即可求解下列拉格朗日方程
\Lambda(x,y,\lambda) = f(x,y) + \lambda \cdot \Big(g(x,y)-c\Big),
此方法的证明牵涉到偏微分，全微分或链法，从而找到能让设出的隐函数的微分为零的未知数的值。

介绍[编辑]

微积分中最常见的问题之一是求一个函数的极大极小值（极值）。但是很多时候找到极值函数的显式表达是很困难的，特别是当函数有先决条件或约束时。拉格朗日乘数则提供了一个非常便利方法来解决这类问题，而避开显式地引入约束和求解外部变量。
先看一个二维的例子：假设有函数：f(x, y)，要求其极值（最大值/最小值），且满足条件
g\left( x,y \right) = c,
c 为常数。对不同d_n的值，不难想像出
f \left( x, y \right)=d_n
的等高线。而方程 g 的等高线正好是 g ( x, y ) = c 。想像我们沿着 g = c 的等高线走；因为大部分情况下 f 和 g 的等高线不会重合，但在有解的情况下，这两条线会相交。想像此时我们移动 g = c 上的点，因为 f 是连续的方程，我们因此能走到f \left( x, y \right)=d_n更高或更低的等高线上，也就是说d_n可以变大或变小。只有当 g = c 和f \left( x, y \right)=d_n相切，也就是说，此时，我们正同时沿着 g = c 和f \left( x, y \right)=d_n走。这种情况下，会出现极值或鞍点。
气象图中就很常出现这样的例子，当温度和气压两列等高线同时出现的时候，切点就意味着约束极值的存在。
用向量的形式来表达的话，我们说相切的性质在此意味着 f 和 g 的斜率在某点上平行。此时引入一个未知标量λ，并求解：
\nabla \Big[f \left(x, y \right) + \lambda \left(g \left(x, y \right) - c \right) \Big] = 0
且λ ≠ 0.
一旦求出λ的值，将其套入下式，易求在无约束极值和极值所对应的点。
F \left( x , y \right)  =  f \left( x , y \right) + \lambda \left( g \left( x , y \right) - c \right)
新方程F(x,y)在达到极值时与f(x,y)相等，因为F(x,y)达到极值时g(x,y)-c总等于零。

拉格朗日乘数的运用方法[编辑]

如f定义为在Rn上的方程，约束为gk（x）= ck（或将约束左移得到gk(x) − ck = 0）。定义拉格朗日Λ为
\Lambda(\mathbf x, \boldsymbol \lambda) = f + \sum_k \lambda_k(g_k-c_k).
注意极值的条件和约束现在就都被记录到一个式子里了：
\nabla \Lambda = 0 \Leftrightarrow \nabla f = - \sum_k \lambda_k \nabla\ g_k,
和
\nabla_{\mathbf \lambda} \Lambda = 0 \Leftrightarrow g_k = c_k.
拉格朗日乘数常被用作表达最大增长值。原因是从式子：
-\frac{\partial \Lambda}{\partial {c_k}} = \lambda_k.
中我们可以看出λk是当方程在被约束条件下，能够达到的最大增长率。拉格朗日力学就使用到这个原理。
拉格朗日乘数法在Karush-Kuhn-Tucker最优化条件被推广。

例子[编辑]

很简单的例子[编辑]

求此方程的最小值：
f(x, y) = x^2 y
同时未知数满足
x^2 + y^2 = 1
因为只有一个未知数的限制条件，我们只需要用一个乘数\lambda.
g (x, y) = x^2 +y^2 -1
\Phi (x, y, \lambda) = f(x,y) + \lambda g(x, y) = x^2 y + \lambda (x^2 + y^2 - 1)
将所有\Phi方程的偏微分设为零，得到一个方程组，最大值是以下方程组的解中的一个：
2 x y + 2 \lambda x = 0
x^2 + 2 \lambda y = 0
x^2 + y^2 -1 = 0
求解方程组，结果如下：
lambda =
           0
           0
-1/3*3^(1/2)
-1/3*3^(1/2)
 1/3*3^(1/2)
 1/3*3^(1/2)
x =
           0
           0
 1/3*6^(1/2)
-1/3*6^(1/2)
 1/3*6^(1/2)
-1/3*6^(1/2)
y =
           1
          -1
 1/3*3^(1/2)
 1/3*3^(1/2)
-1/3*3^(1/2)
-1/3*3^(1/2)
因此，f(x,y)的最小值为-0.3849

另一个例子[编辑]

求此离散分布的最大熵：
f(p_1,p_2,\ldots,p_n) = -\sum_{k=1}^n p_k\log_2 p_k.
所有概率的总和是1，因此我们得到的约束是g（p）= 1即
g(p_1,p_2,\ldots,p_n)=\sum_{k=1}^n p_k=1.
可以使用拉格朗日乘数找到最高熵（概率的函数）。对于所有的k 从1到n，要求
\frac{\partial}{\partial p_k}(f+\lambda (g-1))=0,
由此得到
\frac{\partial}{\partial p_k}\left(-\sum_{k=1}^n p_k \log_2 p_k + \lambda (\sum_{k=1}^n p_k - 1) \right) = 0.
计算出这n个等式的微分，我们得到：
-\left(\frac{1}{\ln 2}+\log_2 p_k \right) + \lambda = 0.
这说明pi都相等 (因为它们都只是λ的函数). 解出约束∑k pk = 1，得到
p_k = \frac{1}{n}.
因此，使用均匀分布可得到最大熵的值。

经济学[编辑]

约束最优化在经济学占有很重要的地位。例如一个消费者的选择问题可以被视为一个求效用方程在预算约束下的最大值问题。拉格朗日乘数在经济学中被解释为影子价格，设定在某种约束下，在这里即收入的边际效用。
拉格朗日乘数就是效用函数在最优解出对收入的偏导数，也就是在最优解处增加一个单位收入带来的效用增加，或者说在最优解处有效用衡量收入的价值，称之为收入的边际效用。
在企业生产问题中，拉格朗日乘数用来衡量要素投入变动所带来的收入变动，du/dm=λ,u表示效用函数或生产函数，m表示收入或要素投入。
在具体数学推导中还可以运用包络定理的内容。

参考[编辑]

对外链接[编辑]

参考拉格朗日原作或方法的命名：
更深入的介绍和互动applet：

标签：

评论

发表评论

此博客中的热门博文

Spark 矩阵相乘实现

矩阵相乘计算的意义十分重要，比如我们做数据分析经常使用到的join操作就可以理解成为矩阵相乘的一个部分，矩阵相乘在很多分布式计算框架都有自己的实现，这些实现也可以根据不同大小的矩阵做不同的优化，比如在MapReduce上就有两种基本的实现： 大矩阵乘小矩阵 我可以把小矩阵放到DistrubutedCache，让每个mapper读取，这就是hive的MapJoin的实现。 两个大矩阵相乘 相乘中两个矩阵都是超大矩阵的话，为了减少MapReduce过程中产生的巨大数据，使用的带宽。都会采用矩阵分块的做法，以下会详细介绍这种实现方法。 Spark介绍 官网介绍 超大矩阵拆分计算方法 单机（单线程）矩阵相乘 假设有矩阵 A ， B ，相乘的结果为 C ，那么相乘的伪代码： C = 0 for(i <- 0 to A.lenght) for(k <- 0 to A[i].lenght) if(A[i][k]!=0) for(j <- B[k].lenght) { C[i][j] += A[i][k] * B[k][j] } 单机的计算中，时间复杂度是 O(n^3)，如果 n 增长到一定程度的时候，那么计算用时就会非常大，所以下面会说一下并行计算方法。 并行矩阵相乘 在计算的过程中，我们很容易发现每个 A[i][k] * B[k][j] 都可以单独计算，因此我也可以单独计算这些组合，最后做一个累计就可以获得 C 矩阵了，相乘伪代码如下： A = ((row, column), value) => (column, (row, value)) B = ((row, column), value) => (row, (column, value)) Temp = A.join(B) => (k, (rowA, valueA), (columnB, valueB)) => ((rowA, columnB), valueA * valueB) => ((rowC, columnC), valueC) C = Temp.reduceByKey =...
发表评论
阅读全文

iphone 自动打包脚本

最近做ios开发，经常需要给老大打ipa包，这个虽然在xcode中编译并打包是很简单的事，不过每次都得花几分钟的时间做一些手动的放入Payload并压缩成zip包的操作。比较麻烦的是，在开发过程中，突然就说要一个可以执行的包做测试。那么，思路断了，正在写的代码要注释掉，这样持续下去浪费的时间会很多，所以还是需要写一个打包脚本。 打包具体用到的命令是这些： xcodebuild: 主要用于编译项目 xcrun: 主要用于打ipa包 具体打包流程就是编译，然后打一个发布包，一个ipa包，其实用脚本来说话就好了。另外，我用一个conf.dat来存放target和configuration,这些都在xcode里面指定好了，用xxx:xxx这样的格式来存放，xcodebuild在编译的时候会自动找到对应的配置。 打包脚本如下: #!/bin/sh basePath=`pwd` distDir="target" distDir="${basePath}/${distDir}" rm -rdf "$distDir" mkdir -p "$distDir" baseName="xxx" #.app 的名字 projectDir=$(cd ../mobile/xxx; pwd) # 进入xcode工程目录 cd $projectDir for line in $(cat ${basePath}/conf.dat) do targetName=`echo $line | cut -f1 -d':'` conf=`echo $line | cut -f2 -d':'` releaseDir="${projectDir}/build/${conf}-iphoneos" rm -rdf "$releaseDir" echo "======build ${baseName}.app start..." echo "======clean ${conf}..." xcodebuild clean -configuration "$...
发表评论
阅读全文

【转】ELO-对弈与排名（有触感的排名）

原文： https://www.cnblogs.com/leoin2012/p/4854442.html ELO介绍 ELO等级分制度 是指由 匈牙利 裔 美国 物理学家 Elo创建的一个衡量各类对弈活动水平的评价方法，是当今对弈水平评估的公认的权威方法。被广泛用于 国际象棋 、 围棋 、 足球 、 篮球 等运动。网络游戏 英雄联盟 、 魔兽世界 内的竞技对战系统也采用此分级制度。 历史 ELO等级分制度是基于 统计学 的一个评估棋手水平的方法。 美国 国际象棋 协会在1960年首先使用这种计分方法。由于它比先前的方法更公平客观，这种方法很快流行开来。1970年国际棋联正式开始使用等级分制度。 Elo模型原先采用 正态分布 。但是实践显明棋手的表现并非呈正态分布，所以现在的等级分计分系统通常使用的是 Logistic distribution 。 计分方法 假设棋手A和B的当前等级分分别为 和 ，则按Logistic distribution A对B的胜率期望值当为 类似B对A的胜率为 假如一位棋手在比赛中的真实得分 （胜=1分，和=0.5分，负=0分）和他的胜率期望值 不同，则他的等级分要作相应的调整。具体的数学公式为 公式中 和 分别为棋手调整前后的等级分。在大师级比赛中 通常为16。 例如，棋手A等级分为1613，与等级分为1573的棋手B战平。若K取32，则A的胜率期望值为 ，约为0.5573，因而A的新等级分为1613 + 32 · (0.5 − 0.5573) = 1611.166 国际象棋中的等级分 国际象棋中，等级分和棋联称号的大致对应为 2500分以上：国际特级大师 2400-2499分：国际大师 2300-2399分：棋联大师  
发表评论
阅读全文