拉格朗日乘数是用于研究函数在约束条件下极值的辅助量。这种方法不消去受约束的变量,而是将约束纳入一个称为拉格朗日函数的新函数中,由此推导出同时包含原变量和乘数的方程。在满足正则性条件的约束最优点处,目标函数的梯度是各个起作用约束的梯度的线性组合。
拉格朗日乘数法是数学优化的基础方法,因为许多问题都包含不便通过代入消去的限制条件:机械系统中各部件之间的距离可能固定不变,统计模型可能要求各项概率之和为一,经济资源配置也可能受到预算限制。乘数既可用于找出候选驻点,也能反映约束所对应的力或边际价值,还能通过对偶性将局部微分条件与全局优化联系起来。
这一方法以约瑟夫·路易·拉格朗日的名字命名,其应用范围远远超出了初等多元微积分。它的现代形式包括处理不等式约束的最优性条件、求解大型约束系统的算法,以及未知量为函数而非有限个数值的变分表述。
等式约束问题与乘子定理
考虑如下问题:
x∈Rnminf(x)subject tohi(x)=0,i=1,…,m,
其中,f 和约束函数 hi 在候选解附近连续可微。函数 f 称为目标函数,满足所有约束的点构成可行集。定义拉格朗日函数为
L(x,λ)=f(x)+i=1∑mλihi(x),
其中 λ=(λ1,…,λm)∈Rm。等式约束的乘子没有符号限制。
经典乘子定理指出,若 x∗ 是约束条件下的局部极小点或局部极大点,且向量
∇h1(x∗),…,∇hm(x∗)
线性无关,则存在唯一的乘子向量 λ∗,使得
∇xL(x∗,λ∗)=0,h(x∗)=0.
用 Dh 表示以各约束梯度的转置为行的雅可比矩阵,上述方程可写成
∇f(x∗)+Dh(x∗)Tλ∗=0,h(x∗)=0.
这是一个包含 n+m 个标量方程、n+m 个未知数的方程组,但仅凭方程与未知数的数量相等,并不能断定解存在、解是孤立的,或能够显式求出。
在上述正则性假设下,这些方程是最优性的必要条件,而非完整的最优性判别准则。方程的解既可能是约束极小点、约束极大点,也可能是两者皆非的驻点。局部分析也不能证明全局最优解的存在。例如,极值定理保证:当可行集非空且紧、目标函数连续时,最优值一定能取到;此时,乘子方程可帮助确定最优值可能在哪些点取到。
对于等式约束,符号约定可以任意选取。有些表述将拉格朗日函数定义为 L=f−∑iλihi,这相当于将每个乘子替换为其相反数,而不改变候选点。约束的归一化方式也很重要:将 hi 替换为 cihi,其中 ci=0,就会将对应的乘子替换为 λi/ci。因此,只有结合乘子所对应的具体约束方程及符号约定,才能理解其意义。
几何、切方向与正则性
几何解释着眼于可行点能够沿哪些方向移动。当 Dh(x∗) 具有满行秩 m 时,隐函数定理表明,该点附近的可行集是一个维数为 n−m 的光滑流形。它在 x∗ 处的切空间为
Tx∗={d∈Rn:Dh(x∗)d=0}.
因此,切方向满足所有线性化后的约束。对于含三个变量、一个等式约束的问题,这个空间通常是与约束曲面相切的平面。
若 x(t) 是一条经过 x∗ 的可微可行曲线,则由链式法则可得
dtdf(x(t))t=0=∇f(x∗)Tx′(0).
在约束局部极值点处,沿每个可行切方向的这一导数都为零。因此,∇f(x∗) 属于切空间的正交补。根据线性代数中的一个结论,这个正交补就是各约束梯度张成的空间,由此便得到乘子方程。
对于平面上的单个正则约束,这意味着在极值点处,目标函数的等值曲线与约束曲线相切,且两者的法向量平行。常见的示意图会画出一组层层嵌套的目标等值线,其中一条与可行曲线相切。不过,一般定理比图示更为精确:目标函数的梯度本身也可能为零,而多个约束则可能提供相互独立的法向方向。
正则性至关重要。考虑
xminxsubject tox2=0.
唯一的可行点是 x=0,因此它既是约束极小值点,也是约束极大值点。然而,
1+λ(2x)=0
在该点不可能成立。问题出在约束梯度为零,而不是不存在可行的最优点。若将同一个可行集改写为 x=0,约束梯度便不再为零,也就能得到有效的乘子方程。
冗余约束会带来另一种问题。方程 x=0 和 2x=0 描述的是同一限制,但它们的梯度线性相关。此时乘子可能存在,却不唯一。更一般的弗里茨·约翰条件在目标梯度前引入系数 α:
α∇f(x∗)+i∑λi∇hi(x∗)=0,
其中各系数不全为零。正则性条件排除了 α=0 这一异常情形,从而可以通过归一化得到通常的拉格朗日方程。
典型计算示例
一个基本例子是求解以下优化问题:
f(x,y)=xysubject tox2+y2=1.
令
L(x,y,λ)=xy+λ(x2+y2−1),
由驻点条件得
y+2λx=0,x+2λy=0,x2+y2=1.
在满足驻点条件的解处,两个坐标都不可能为零:若其中一个为零,前两个方程就会迫使两者都为零。因此,消去 λ 可得 x2=y2。
四个候选点为
(x,y)=(21,21),(−21,−21),(21,−21),(−21,21).
它们对应的目标函数值分别为 1/2,1/2,−1/2,−1/2。由于该圆是紧集,且约束函数的梯度在圆上处处非零,所有全局极值点必定都在这些候选点之中。这一计算说明,解出乘数方程后,还必须对候选点进行分类或比较。
一个高维例子是在满足线性方程组的条件下,寻找距离给定向量 a 最近的点:
xmin21∥x−a∥2subject toAx=b,
其中矩阵 A∈Rm×n 为行满秩矩阵。相应的方程为
x−a+ATλ=0,Ax=b.
代入可得
AATλ=Aa−b,
因此
x∗=a−AT(AAT)−1(Aa−b).
在上述秩条件下,矩阵 AAT 可逆。从几何上看,x∗ 是 a 在仿射可行集上的正交投影;修正向量 a−x∗ 位于该可行集的法空间中。
乘数法还可以导出特征值与特征向量的变分刻画。对于实对称矩阵 Q,考虑
xminxTQxsubject toxTx=1.
由驻点条件得
2Qx+2λx=0,
因此,候选点是对应于特征值 −λ 的单位特征向量。最小特征值和最大特征值分别是目标函数在单位球面上的最小值和最大值。对应于中间特征值的特征向量可能是约束驻点,却不是极值点。这个例子将乘数法与谱定理以及基于二次型的降维方法联系起来。
二阶条件与驻点分类
一阶导数决定了目标函数沿可行集是否会发生一阶变化。要判定驻点的类型,还需要曲率信息。假设 f 和各约束函数都二阶连续可微,约束梯度在 x∗ 处线性无关,且 λ∗ 满足驻点方程。定义拉格朗日函数的海森矩阵
HL=∇2f(x∗)+i=1∑mλi∗∇2hi(x∗).
其中的约束项不可或缺:沿可行曲线计算目标函数的二阶导数时,可行集的曲率也会产生贡献。
局部极小值的一个二阶必要条件是
dTHLd≥0for every d∈Tx∗.
对于局部极大值,不等号方向相反。严格局部极小值的一个标准充分条件是
dTHLd>0for every nonzero d∈Tx∗.
因此,拉格朗日函数的海森矩阵不必在整个环境空间上都是正定矩阵。这一判别只考察满足线性化约束的方向。
为了便于计算,令 Z 的各列构成 Dh(x∗) 的零空间的一组基。每个切向量都可写成 d=Zp,且
dTHLd=pT(ZTHLZ)p.
矩阵 ZTHLZ 称为约化海森矩阵。在上述正则性假设下,它的正定性足以保证该点为严格局部极小值点。如果存在使相应二次型为负的方向,就可以排除局部极小值;而出现零特征值时,则可能仍无法确定驻点的类型。
例如,在约束
h(x,y)=y−x2=0.
下,求 f(x,y)=y 的最小值。在可行抛物线上,目标函数等于 x2,因此原点是严格极小值点。然而,目标函数的海森矩阵处处为零。在原点处,由驻点条件可得 λ=−1,并且
∇xx2L=(2000).
切向量的形式为 (dx,0);只要 dx=0,相应的二次型就严格为正。
如果约化海森矩阵只是半正定或半负定,结果可能取决于更高阶的性质。在约束 y=0 下,目标函数 x4、−x4 和 x3 在原点处的一阶、二阶导数都为零,但原点分别是极小值点、极大值点和非极值点。因此,即使所有函数都光滑,二阶判别法仍有明确的局限。
不等式与卡鲁什—库恩—塔克条件
对于含不等式约束的最小化问题,标准约定为
xminf(x)subject tohi(x)=0,gj(x)≤0.
其拉格朗日函数为
L(x,λ,μ)=f(x)+i∑λihi(x)+j∑μjgj(x).
卡鲁什—库恩—塔克条件通常简称为 KKT 条件,将平稳性条件、可行性条件和符号限制结合起来:
∇xL(x∗,λ∗,μ∗)hi(x∗)gj(x∗)μj∗μj∗gj(x∗)=0,=0,≤0,≥0,=0.
等式约束的乘子仍不受符号限制。最后一个条件称为互补松弛条件。
当 gj(x∗)=0 时,不等式约束是活跃的;当 gj(x∗)<0 时,则是非活跃的。互补松弛条件要求非活跃约束的乘子为零。活跃不等式约束的乘子可以为正,也可以为零。这一区别很重要,因为从几何上看,到达边界这一事实本身并不意味着该约束具有非零的一阶价值。
例如,在约束 x≤1 下最小化 f(x)=(x−2)2。此时 g(x)=x−1,最优解为 x∗=1。由平稳性条件可得
2(x∗−2)+μ∗=0,
因此 μ∗=2。若将约束改为 x≤3,无约束最小值点 x∗=2 就是可行的,相应的乘子为零。若约束改为 x≤2,最优解虽然位于边界上,但其乘子仍为零。
对于非凸问题,通常只有在满足适当的约束资格条件时,KKT 条件才是必要条件。一种足够的资格条件是:所有等式约束的梯度与所有活跃不等式约束的梯度共同构成线性无关组。更弱的条件还能涵盖其他情形。如果不满足任何资格条件,最优解处可能不存在通常意义下的 KKT 乘子,正如奇异等式约束也可能出现这种情况一样。
在凸优化中,这些方程的作用更强。若 f 和每个 gj 都是可微的凸函数,且等式约束均为仿射约束,那么任何满足 KKT 条件的可行点都是全局最优解。反过来,在标准的有限维假设下,若最优值能够取到,那么斯莱特条件等资格条件就能保证乘子存在;斯莱特条件要求存在一个点,既严格满足所有不等式约束,又满足所有仿射等式约束。这些都是全局性结论,仅凭初等的驻点定理无法得出。
对偶性、敏感性与约束的价值
乘子将微分形式的最优性条件与拉格朗日对偶联系起来。对于约束最小化问题,定义对偶函数
q(λ,μ)=xinfL(x,λ,μ),μ≥0.
这里的下确界在原变量的定义域上取,所列约束被纳入拉格朗日函数,而不再单独施加。对于任意可行的 x,都有
L(x,λ,μ)≤f(x),
因为等式约束项均为零,而每个不等式约束项均非正。因此,q(λ,μ) 是原问题最优值的一个下界。
对偶问题就是将这一下界最大化:
λ, μ≥0supq(λ,μ).
其最优值不可能超过原问题的下确界,这一性质称为弱对偶性。最优值相等则称为强对偶性。凸性与适当的约束资格条件通常可以保证强对偶性,而非凸问题则可能存在正的对偶间隙。因此,求解关于原变量的局部驻点方程,并不等同于求解对偶问题。
乘子还描述了最优值对约束水平变化的敏感性分析。考虑
v(b)=xminf(x)subject toh(x)=b,
其中
L(x,λ;b)=f(x)+λT(h(x)−b).
沿着一条可微的局部解分支,由驻点条件和对约束求导所得的关系可得
∇bv(b)=−λ∗(b).
对于全局值函数,这一公式还要求该分支始终对应全局最优解,并且满足相关的可微性条件。若改变 L 的符号约定,公式中乘子的符号也会相应改变。
一个直观的例子是
v(b)=xmin21x2subject tox=b.
其最优值为 v(b)=b2/2。驻点条件给出 x+λ=0,因此 λ∗=−b,恰好与 v′(b)=−λ∗=b 一致。在经济学和运筹学中,类似的边际价值通常称为影子价格。其单位是目标函数的单位除以相应约束的单位。
当最优解发生突变、乘子不唯一或值函数不光滑时,单一导数可能无法描述这种敏感性。在凸问题中,最优乘子则可以为值函数提供支撑性的线性界。这样,无须假设最优解唯一,也无须假设解对扰动的响应光滑,仍能保留精确的边际解释。
数值求解与约束优化算法
从计算角度看,乘子方程构成一个耦合的非线性方程组。将牛顿法应用于等式约束下的驻点条件,可得到如下形式的线性方程组:
(HLAAT0)(ΔxΔλ)=−(∇xLh),
其中 A=Dh(x),各导数均在当前迭代点处计算。上方的方程用于修正驻点条件的偏差,下方的方程则用于修正约束违反量。这类矩阵通常称为 KKT 矩阵。
即使在严格约束极小点附近,这些矩阵通常也是不定的。因此,求解器会采用适当的对称不定分解、零空间法或分块消元法,而不是假定矩阵正定。如果约束的雅可比矩阵具有满行秩,且约化海森矩阵正定,那么等式约束问题的 KKT 矩阵就是非奇异的。相反,如果约束梯度近似线性相关,乘子估计值就可能对微小的数值误差高度敏感。
序列二次规划构造一系列局部二次优化问题。其中,目标函数用二次函数近似,约束用线性函数近似,曲率信息则由拉格朗日函数的海森矩阵或其近似提供。求解每个子问题可得到原变量的迭代步以及乘子的估计值。对于不等式约束,活跃集方法会识别出在局部作为等式处理的约束;内点法则维持松弛变量和正的对偶变量,并逐步逼近互补松弛条件。
罚函数法提供了另一种联系。二次罚函数将等式约束问题替换为
xminf(x)+2ρ∥h(x)∥2.
在驻点处,
∇f(x)+Dh(x)T(ρh(x))=0,
因此,ρh(x) 起到了乘子估计值的作用。增大 ρ 可以使约束违反量趋于零,但过大的罚参数往往会增大数值问题的条件数。
增广拉格朗日法将显式乘子与二次罚项结合:
Lρ(x,λ)=f(x)+λTh(x)+2ρ∥h(x)∥2.
一种标准的迭代方式是先对 x 近似最小化这一表达式,然后更新
λk+1=λk+ρh(xk+1).
在适当的假设和精度要求下,乘子更新能够改善约束的满足程度,而无须像纯罚函数方案那样快速增大罚参数。在实际计算中,约束的尺度调整、导数精度以及数值稳定性,都会影响计算所得的解及其所报告乘子的可靠性。
在统计学、信息论和力学中的应用
在最大似然估计中,概率通常受到总和为一的约束。假设各类别结果的计数 n1,…,nk 均为正数,总计数为 N。为求解最大化问题
ℓ(p)=i=1∑knilogpisubject toi∑pi=1
引入拉格朗日函数
L(p,λ)=ℓ(p)+λ(i∑pi−1),
可得方程
pini+λ=0.
由归一化条件可得 λ=−N 和 pi=ni/N。计数均为正数保证了解位于内部;若存在零计数,则需要专门处理边界上的概率以及对数函数定义域的问题。
在信息论中,在给定均值的约束下最大化信息熵,会得到有限状态空间上的指数形式分布。对于取值为 Ei 的各个状态,施加约束
i∑pi=1,i∑piEi=U.
函数
−i∑pilogpi−α(i∑pi−1)−β(i∑piEi−U)
的内部驻点满足
pi=Z(β)e−βEi,Z(β)=j∑e−βEj.
乘子 β 的取值由给定均值确定。当存在可行的内部解时,熵的严格凹性保证了解的唯一性,因此上述计算得到的不只是一个尚待判定的驻点候选解。
在经典力学中,乘子表示广义约束力。设广义坐标为 q,力学拉格朗日函数为 Lmech(q,q˙,t),理想完整约束为 hi(q,t)=0,则按一种惯例,方程写为
dtd∂q˙a∂Lmech−∂qa∂Lmech=i∑λi∂qa∂hi.
右端与该瞬间允许的虚位移正交。对于被限制在球面上运动的质点,它描述的是径向约束反力。乘子与实际作用力之间的数值关系取决于约束方程的归一化方式。
乘子也能解释约束拟合与正则化之间的关系。在约束 R(x)≤c 下最小化损失函数的问题,其拉格朗日函数为
f(x)+μ(R(x)−c),μ≥0.
在满足适当条件的最优解处,μ 起到惩罚项 R(x) 的系数的作用。这就将岭回归和套索回归的约束形式与惩罚形式联系起来。不过,对于非光滑惩罚项,需要使用广义导数,而且约束上界与惩罚权重之间未必存在一一对应关系。
历史发展与变分推广
乘子法源于十八世纪分析力学和变分法的发展。拉格朗日于1788年出版的《分析力学》对受约束力学系统进行了系统的解析处理。未定乘子使人们能够保留便于使用的坐标,同时通过额外的未知量来计入约束。因此,历史上的这一方法与消去未知约束反力密切相关,使人们无须显式求解每一个几何约束,就能描述平衡或运动。
现代有限维定理通过可微函数、矩阵的秩和切空间来表述这一思想。二十世纪,不等式约束优化形成了更为广泛的理论框架。威廉·卡鲁什在1939年的硕士论文中建立了一些条件,如今这些条件被视为KKT理论的一部分;哈罗德·W. 库恩和阿尔伯特·W. 塔克于1951年提出了与之密切相关的条件。弗里茨·约翰在1948年的工作中给出了一种重要表述,能够在通常的约束品性条件不成立时容纳异常乘子。
在变分问题中,未知量是一个函数,而约束本身也可能是一个积分。考虑如下等周问题:
ymin∫abF(t,y(t),y′(t))dt
其约束为端点值固定,且满足
∫abG(t,y(t),y′(t))dt=c.
在适当的可微性和正则性假设下,可以用一个标量乘子 λ 将两个被积函数组合起来:
F=F+λG.
于是,驻定解满足欧拉—拉格朗日方程
∂y∂F−dtd∂y′∂F=0,
以及上述积分约束。即使优化变量是整个函数,单个标量约束所对应的仍是一个标量乘子。
对场施加的逐点约束通常需要乘子函数,而不是常数。例如,流体力学中的不可压缩条件要求在每一个空间点成立,而在变分表述和弱形式中,压强可以解释为乘子。类似的构造也出现在受约束弹性问题和偏微分方程的混合形式中;在这些情形下,乘子在施加物理约束的同时,也成为一个额外的未知场。
在泛函分析中,一般框架涉及巴拿赫空间之间的可微映射。乘子属于适当的对偶空间,而有限维情形中的满秩假设,则由涉及约束映射导数的满射性、值域闭性或其他性质的条件所取代。混合数值离散化还必须保持主变量空间与乘子空间之间的相容性。否则,即使连续乘子形式在形式上正确,也可能产生奇异或不稳定的离散系统。