导语：拉格朗日乘子法是用于解决一类有约束的非线性规划问题的方法。它并不是一个计算结果的算法，而是把规划问题转化成一个更简便的格式，便于使用其他的算法进行计算。著名的马科维兹均值-方差问题就可以用拉格朗日乘子解决。

阅读本文前需要掌握线性代数、多元微积分以及非线性规划的基础知识。

要解决的问题

设 ff

f

和 gg

g

是 C1C1

\mathcal C^1

的 Rn→RRn→R

\mathbb R^n \to \mathbb R

函数，并且 c∈Rc∈R

c \in \mathbb R

是一个实数，我们考虑以下的数学规划问题：

max满足f(x)g(x)=cx∈Rnmaxf(x)满足g(x)=cx∈Rn

\begin{align}
\max & \qquad f(x)\
\text{满足} & \qquad g(x) = c\
& \qquad x \in \mathbb R^n
\end{align}

拉格朗日乘子是一个解决这类问题的方法。直接介绍拉格朗日乘子的话并不是很好理解，于是我们先把上述规划问题的解题思路捋一遍，文章最后再介绍拉格朗日乘子的时候，其中的原理就一目了然了。

ggg的水平集

首先我们要了解规划问题的的可行域，也就是所有满足 g(x)=cg(x)=c

g(x)= c

的 x∈Rnx∈Rn

x \in \mathbb R^n

。下面给这个集合一个定义：

定义. 设 g:Rn→Rg:Rn→R

g:\mathbb R^n \to \mathbb R

是一个函数，我们说 gg

g

在 c∈Rc∈R

c \in \mathbb R

的水平集 (level set)是

Lc={x∈Rn:g(x)=c}.Lc={x∈Rn:g(x)=c}.

L_c = { x \in \mathbb R^n : g(x) = c }.

举个一例子。考虑一个固定的 R2→RR2→R

\mathbb R^2 \to \mathbb R

函数 g?(x,y)=x2?y2g~(x,y)=x2?y2

\widetilde g(x,y)= x^2 - y^2

，它的图像如下

我们来选择一个水平集。嗯，cc

c

等于多少好呢... 就 c=?1c=?1

c = -1

吧。看一眼水平集 L??1={(x,y)∈R2:x2?y2=?1}L~?1={(x,y)∈R2:x2?y2=?1}

\widetilde L_{-1} = { (x,y) \in \mathbb R^2 : x^2 - y^2 = -1 }

，如下图红线所示

如果从上方向下看函数 g?g~

\widetilde g

的热力图，那么下图中的每一条线是 g?g~

\widetilde g

的一个水平集，根据颜色的从紫到黄，依次是 c=?23,?22,…,22,23c=?23,?22,…,22,23

c = -23,-22, \dots , 22, 23

的水平集。其中两条红线是我们的 c=?1c=?1

c = -1

水平集

机智的读者一定已经算出，组成水平集 L??1L~?1

\widetilde L_{-1}

的两条曲线在 (x,y)(x,y)

(x,y)

坐标系上可以分别用函数

y=x2 1?????√和y=?x2 1?????√y=x21和y=?x21

y= \sqrt{ x^2 1}\qquad \text{和}\qquad y=-\sqrt{x^2 1}

的图像表示。

我们来看水平集 L??1L~?1

\widetilde L_{-1}

一个重要的的几何性质。假设从前有座山，山里有座庙，庙前有片空地，地形和图二里的一模一样。你顺着上边的那条红线走呀走，发现自己的 xx

x

坐标和 yy

y

坐标都在变动，可是竖向的 zz

z

坐标一直不变，也就是说海拔不变。你摸着自己地良心问：“我走过了哪里，又将走向哪里？”良心答曰：“你在时间 tt

t

的 (x,y)(x,y)

(x,y)

坐标是 p(t)=(t,t2 1?????√)p(t)=(t,t21)

p(t) = ( t , \sqrt{t^2 1} )

。”如梦初醒的你掏出小木棍在土地上一阵划拉，计算出自己在时间 tt

t

的行走方向是 p′(t)=(1,t/t2 1?????√)p′(t)=(1,t/t21)

p(t) = (1, t/\sqrt{t^2 1})

。

“谢谢你，我的良心。”

“嗯，别烦我了。”

无视了来自良心的蔑视，你又不禁遐想，这片大地的梯度又是多少呢？经过十三年的艰苦钻研，你最终算出了地形的梯度函数 ?g?(x,y)=(2x,?2y)?g~(x,y)=(2x,?2y)

\nabla \widetilde g(x,y) = (2x, -2y)

。代入函数 p(t)p(t)

p(t)

，你得知在时间 tt

t

的时候你的所在地的地形梯度是 ?g?(p(t))=(2t,?2t2 1?????√)?g~(p(t))=(2t,?2t21)

\nabla \widetilde g(p(t)) = ( 2t, -2\sqrt{t^2 1} )

。

于是你一边走一边向 ?g??g~

\nabla \widetilde g

的方向死死盯着不放，最终得了颈椎病。你扶着已经转不回来的脖子，恍然大悟：原来 ?g?(p(t))?g~(p(t))

\nabla \widetilde g(p(t))

和 p′(t)p′(t)

p(t)

是垂直的。是哪，

?g?(p(t))?p′(t)=2t?2t=0,?g~(p(t))?p′(t)=2t?2t=0,

\nabla \widetilde g(p(t)) \cdot p(t) = 2t - 2t = 0,

也就是说 g?g~

\widetilde g

的水平集的切线和 g?g~

\widetilde g

的梯度是永远垂直的！

仔细想一想的话这也是当然。根据线搜索方法文章中所讲，函数 g?g~

\widetilde g

在 (x,y)(x,y)

(x,y)

的梯度 ?g?(x,y)?g~(x,y)

\nabla \widetilde g(x,y)

是 g?g~

\widetilde g

的取值上升最快的方向，而 ??g?(x,y)??g~(x,y)

-\nabla \widetilde g(x,y)

则是 g?g~

\widetilde g

的取值下降最快的方向。水平集是 g?g~

\widetilde g

取值不变的集合，那么在水平集上行走的话，行走方向应该和上升方向 ?g??g~

\nabla \widetilde g

之间保持一定角度，这样就不会上升，当然也要和下降方向 ??g???g~

-\nabla \widetilde g

保持一定角度，这样就不会下降。用脚趾头一想，既然 ?g??g~

\nabla \widetilde g

和 ??g???g~

-\nabla \widetilde g

之间的角度是 180180

180

度，那么折中的不上不下的角度应该就是那个的一半吧，也就是说行走方向应该是和 ?g??g~

\nabla \widetilde g

垂直的。

以上的现象用直白的话说，就是梯度和水平集是垂直关系的，这也是多元微积分里的一个基础定理：

定理. 设 g:Rn→Rg:Rn→R

g: \mathbb R ^n \to \mathbb R

是一个 C1C1

\mathcal C^1

函数，c∈Rc∈R

c \in \mathbb R

是一个实数，而 Lc?RnLc?Rn

L_c\subseteq \mathbb R^n

是 gg

g

取值为 cc

c

的水平集。对于任何一个 a>0a>0

a>0

和 C1C1

\mathcal C^1

曲线 α:(?a,a)→Lcα:(?a,a)→Lc

\alpha : (-a , a) \to L_c

，都有 ?g(α(t))?α′(t)=0?g(α(t))?α′(t)=0

\nabla g(\alpha (t))\cdot \alpha (t) = 0

。

证明. 因为对于所有 t∈(?a,a)t∈(?a,a)

t\in (-a , a)

都有 α(t)∈Lcα(t)∈Lc

\alpha(t) \in L_c

，所以也有 g(α(t))=cg(α(t))=c

g(\alpha (t)) = c

。微分，并且使用链式法则可得

0=ddtc=ddtg(α(t))=?g(α(t))?α′(t).0=ddtc=ddtg(α(t))=?g(α(t))?α′(t).

\begin{align}
0 & = \frac{d}{dt} c\
& = \frac{d}{dt} g(\alpha (t)) \
& = \nabla g(\alpha (t)) \cdot \alpha(t).
\end{align}

是想要的等式。 □?

\square

用红色箭头表示函数 g?g~

\widetilde g

的梯度的话，它会是像下图中这样，和水平集相垂直。

当然，这个现象不只是针对于例子中这个特定的 gg

\mathcal g

，上面的定理适用于任何一个函数 gg

g

，它们的梯度和它们的水平集都是相互垂直的。

有请目标函数 fff

我们回顾一下最初要解决的问题

max满足f(x)g(x)=cx∈Rnmaxf(x)满足g(x)=cx∈Rn

\begin{align}
\max & \qquad f(x)\
\text{满足} & \qquad g(x) = c\
& \qquad x \in \mathbb R^n
\end{align}

在上一节中我们对这个规划问题的可行区域 LcLc

L_c

有了一个初步的认识。那么接下来，当然是要在可行域上寻找目标函数 ff

f

的最大值了。

好，我们就设一个目标函数

f?(x,y)=203 x2 2y2,f~(x,y)=203x22y2,

\widetilde f(x,y) = \frac{20}{3 x^2 2y^2},

它长得像这样，中间是一个小山丘。

在规划问题中，我们想要的是在 gg

g

的水平集 LcLc

Lc

上找到 ff

f

的最大值，那么把上一章节计算出的水平集 L??1L~?1

\widetilde L{-1}

画在 f?f~

\widetilde f

的图像上，是这样的。

现在就假设你又来了一座山，又发现了一座庙，庙前有个小山坡，长得这个样。站在山脚下，你回想起了以前沿着 g?g~

\widetilde g

的水平集走过的路径，也就是 p(t)=(t,t2 1?????√)p(t)=(t,t21)

p(t) = (t, \sqrt{t^2 1})

，你决定还沿着这条路来走这个山坡。

不过这次可和上一次不一样了，虽然走的同样的路径，但是地形不一样，所以海拔不再是一成不变，而是时高时低。你不禁好奇，在这条路上海拔最高的点在哪里？

你摸了摸自己的良心，“良心良心告诉我，...... ”

“请你不要摸我了好吗？好恶心的。”

“好，”你乖乖地把手拿开，“良心良心告诉我，我的海拔是多少？”

“你在时间 tt

t

的海拔是 f?(p(t))=20/(32 3t2)f~(p(t))=20/(323t2)

\widetilde f(p(t)) = 20/(32 3t^2)

。”

啊！你再次恍然大悟，算出了 f?(p(t))f~(p(t))

\widetilde f(p(t))

的导数并且设它等于零，不就知道海拔高度出现极值的地方了吗？事不宜迟，你掏出了小木棍，又开始在地上胡乱划拉起来。

这一晃又过去了二十三年，你终于长叹一口气，得到了一个如此简练的公式：

0=ddtf?(p(t))=?f?(p(t))?p′(t).0=ddtf~(p(t))=?f~(p(t))?p′(t).

0 = \frac{d}{dt} \widetilde f(p(t)) = \nabla \widetilde f (p(t)) \cdot p (t).

具体的数值什么的，已经都无所谓了（其实是因为你到最后也没搞清楚怎么微分 1/(32 3t2)1/(323t2)

1/(32 3t^2)

，不过这种事就让它过去吧）。如果在时间 tt

t

的海拔高度是最高的，那么上面的这条公式必定被满足。也就是说，对于一个点 x0∈L?cx0∈L~c

x_0 \in \widetilde L_c

，如果 x0x0

x_0

是 f?f~

\widetilde f

在 L?cL~c

\widetilde L_c

上的一个极大点，那么梯度 ?f?(x0)?f~(x0)

\nabla \widetilde f(x_0)

和 L?cL~c

\widetilde L_c

在 x0x0

x_0

的切线一定是垂直的。

“谢谢你，我的良心。”

“你好烦呐。”

可是，这个公式看着真的是好眼熟啊，眼熟到好像刚刚看过... 是吧，

?g?(p(t))?p′(t)=0 ?t∈R,?g~(p(t))?p′(t)=0 ?t∈R,

\nabla \widetilde g(p(t)) \cdot p(t) = 0\ \forall t \in \mathbb R,

g?g~

\widetilde g

的梯度和它的水平集永远是垂直的。那么，在极大点上，?g??g~

\nabla \widetilde g

和水平集垂直，?f??f~

\nabla \widetilde f

也和水平集垂直，也就是说... ?g??g~

\nabla \widetilde g

和 ?f??f~

\nabla \widetilde f

是平行的！！

事实上，这个现象不只是针对于例子中的 f?f~

\widetilde f

和 g?g~

\widetilde g

，对于任何 C1C1

\mathcal C^1

函数 ff

f

和 gg

g

都是这样的。我们有定理如下：

定理. 设 f,g:Rn→Rf,g:Rn→R

f,g:\mathbb R^n \to \mathbb R

是 C1C1

\mathcal C^1

函数，c∈Rc∈R

c \in \mathbb R

并且 Lc={x∈Rn:g(x)=c}Lc={x∈Rn:g(x)=c}

L_c = { x \in \mathbb R^n : g(x)=c }

。如果 x0∈Lcx0∈Lc

x_0 \in L_c

满足对于所有 x∈Lcx∈Lc

x \in L_c

都有 f(x0)≥f(x)f(x0)≥f(x)

f(x_0) \geq f(x)

或者 f(x0)≤f(x)f(x0)≤f(x)

f(x_0) \leq f(x)

，那么存在某个 λ∈Rλ∈R

\lambda \in \mathbb R

满足 ?f(x0)=λ?g(x0)?f(x0)=λ?g(x0)

\nabla f(x_0) = \lambda \nabla g(x_0)

，满足这个条件的点叫做一个驻点 (critical point)。

这个定理在 n=2n=2

n=2

情况下的证明正如本文中对 ff

\mathcal f

和 gg

\mathcal g

的推导一样，但是在更高的维度里有一些细节会增加证明的难度。不过，你只要坚定地相信这个定理是对的，就一定没有问题了！

那么，对于在上边例子中的函数，如果俯视观看 ff

\mathcal f

的水平集和行走的路径 p(t)p(t)

p(t)

，是如下图：

图中红色箭头是 gg

\mathcal g

的梯度方向，蓝色箭头是 ff

\mathcal f

的梯度方向，在红线上 ff

\mathcal f

取值极大点的地方，两者的梯度方向是重叠的，标为紫色。

当应用于更一般性的 ff

f

和 gg

g

的规划问题中，定理告诉我们如果有 x0∈Rnx0∈Rn

x0\in \mathbb R^n

是 maxg(x)=cf(x)maxg(x)=cf(x)

\max{g(x)= c} f(x)

问题的极大点的话，那么它不仅要满足 g(x0)=cg(x0)=c

g(x_0) =c

，还要存在一个 λ∈Rλ∈R

\lambda \in \mathbb R

以至于 ?f(x0)=λ?g(x0)?f(x0)=λ?g(x0)

\nabla f(x_0) = \lambda \nabla g(x_0)

。所以如果我们能找出满足这些条件的点，那就可以更简单地找到 x0x0

x_0

。 当然，用这个方法算出的点不一定是极大点。它也有可能是极小点或者反射点，这就要用其他的办法来验证了，或者干脆把所有的驻点都算出来，然后比一比哪个大哪个小就知道了。

我们还要拉格朗日乘子干什么？

在以上的计算中，我们没用什么特殊的方法就解决了在 L??1L~?1

\widetilde L_{-1}

上优化 f?f~

\widetilde f

的问题，那么为什么还要需要拉格朗日乘子？

上面的例子的一个特点就是，它太简单了，或者说维度太低了，只用两条曲线就完全描述了水平集 L??1L~?1

\widetilde L{-1}

，在此之上只需要微积分就可以算出答案。但在更高的维度中，LcLc

L{c}

是不能用曲线描述的，所以也不会有这么简单的计算方法。但是，前面得出的两个定理在高维中同样适用，并且根据定理，我们知道要找的极大点必须满足

(?){g(x)=c，也就是说 x 在 g 的水平集里;存在一个 λ∈R 满足 ?f(x)=λ?g(x).(?){g(x)=c，也就是说 x 在 g 的水平集里;存在一个 λ∈R 满足 ?f(x)=λ?g(x).

(*) \begin{cases} g(x) = c \text{，也就是说 $x$ 在 $g$ 的水平集里}; \ \text{存在一个 }\lambda \in \mathbb R \text{ 满足 }\nabla f(x)= \lambda \nabla g(x). \end{cases}

这时，拉格朗日就来了，他给我们一个可以同时囊括上面两个条件的函数。什么函数这么神奇呢？那就是

L(x,λ)=f(x)?λ(g(x)?c),L(x,λ)=f(x)?λ(g(x)?c),

\mathcal L(x,\lambda) = f(x) - \lambda (g(x)-c),

这里 x∈Rnx∈Rn

x \in \mathbb R^n

并且 λ∈Rλ∈R

\lambda \in \mathbb R

，所以 LL

\mathcal L

是一个 Rn 1→RRn1→R

\mathbb R^{n 1} \to \mathbb R

的函数。严格来讲，这个函数中的 λλ

\lambda

被称为拉格朗日乘子 (Lagrange multiplier)，但我们一般说“拉格朗日乘子”的时候指的是这里介绍的方法。

计算 LL

\mathcal L

的导数，分别得到

ddxiL(x,λ)=ddxif(x)?λddxig(x), ?i=1,…,n,ddxiL(x,λ)=ddxif(x)?λddxig(x), ?i=1,…,n,

\frac{d}{dx_i} \mathcal L(x,\lambda) = \frac{d}{dx_i} f(x) - \lambda \frac{d}{dx_i} g(x),\ \forall i= 1,\dots, n,

ddλL(x,λ)=?g(x) c.ddλL(x,λ)=?g(x)c.

\frac{d}{d\lambda} \mathcal L(x, \lambda ) = -g(x) c.

或者写作

?L(x,λ)=[?f(x)?λ?g(x)?g(x) c].?L(x,λ)=[?f(x)?λ?g(x)?g(x)c].

\nabla \mathcal L(x,\lambda) = \begin{bmatrix} \nabla f(x)- \lambda \nabla g(x)\-g(x) c \end{bmatrix}.

那么，

?L(x,λ)=0?{g(x)=c?f(x)=λ?g?x 满足(?).?L(x,λ)=0?{g(x)=c?f(x)=λ?g?x 满足(?).

\nabla \mathcal L(x,\lambda) = 0 \iff \begin{cases} g(x)= c \ \nabla f(x) = \lambda \nabla g \end{cases} \iff x \text{ 满足}(*).

因此，在 gg

g

的水平集上优化 ff

f

的取值时，只需要计算 ?L(x,λ)?L(x,λ)

\nabla \mathcal L(x,\lambda)

的零点就可以了。

拉格朗日乘子完全版

拉格朗日乘子的功力还不止于此，它可以应用于有多于一个约束函数的规划问题。

定理. 设 m∈Nm∈N

m \in \mathbb N

。对于 i∈{1,2,…,m}i∈{1,2,…,m}

i \in {1,2,\dots, m}

，gigi

g_i

和 ff

f

都是 Rn→RRn→R

\mathbb R^n \to \mathbb R

的 C1C1

\mathcal C^1

函数，并且设 ci∈Rci∈R

c_i \in \mathbb R

。考虑规划问题

最大化满足f(x)gi(x)=ci,i=1,2,…,mx∈Rn.最大化f(x)满足gi(x)=ci,i=1,2,…,mx∈Rn.

\begin{align}
\text{最大化} & \qquad f(x)\
\text{满足} &\qquad g_i(x)= c_i, i = 1,2 , \dots ,m\
& \qquad x \in \mathbb R^n.
\end{align}

定义函数

L(x,λ)=f(x)?λ1(g1(x)?c1)???λm(gm(x)?cm),L(x,λ)=f(x)?λ1(g1(x)?c1)???λm(gm(x)?cm),

\mathcal L(x,\lambda) = f(x) - \lambda _1 ( g_1(x)- c_1) - \dots - \lambda _m (g_m(x)- c_m),

这里 λ=(λ1,λ2,…,λm)∈Rmλ=(λ1,λ2,…,λm)∈Rm

\lambda = (\lambda _1 , \lambda _2, \dots , \lambda _m) \in \mathbb R ^m

。那么如果 x?∈Rnx~∈Rn

\widetilde x \in \mathbb R^n

是上述规划问题的极值点，必定存在某个 λ?∈Rmλ~∈Rm

\widetilde \lambda \in \mathbb R ^m

满足

?L(x?,λ?)=0.?L(x~,λ~)=0.

\nabla \mathcal L(\widetilde x , \widetilde \lambda )= 0.

如果想要理解或者证明这个完整版的定理，我们需要更多的线性代数和微积分的工具，本文中则不进行更深入的讨论。

到此为止我们找到了算出极值点的条件，但是把它算出来终究是个问题。如果 ff

f

和 gigi

g_i

都是很丑的函数，那么 LL

\mathcal L

必定是其丑无比，计算 ?L?L

\nabla \mathcal L

的零点的准确值也是不可能的，所以一般会采取一些数值优化的方法进行估算。一个可行的思路是解决 Rn mRnm

\mathbb R^{n m}

上的无约束的非线性规划问题

最小化满足∥?L(x,λ)∥x∈Rn,λ∈Rm最小化∥?L(x,λ)∥满足x∈Rn,λ∈Rm

\begin{align}
\text{最小化} & \qquad |\nabla \mathcal L(x,\lambda) |\
\text{满足} & \qquad x \in \mathbb R^n,\, \lambda \in \mathbb R^m
\end{align}

而它使用线搜索方法的算法就可以计算。将有约束的规划问题简化成无约束的规划问题，这已经足以体现拉格朗日乘子的价值了。

结语

当然，ff

f

和 gigi

g_i

并不一定都非常丑。如果目标函数和约束函数都是二次多项式，求得 ?L?L

\nabla \mathcal L

零点的准确值还不是绝望的难，而且很多重要的应用场景都在这个范畴之内，比如... 在量化课堂的下一篇文章中，我们就将针对马科维兹的均值-方差问题使用拉格朗日乘子进行优化，并计算出有效前沿的解析解。

后记

一个白发苍苍的老人独自蹲在荒凉的山脊上，攥着一根细小的木棍，胡乱在土地上划拉着。不论风吹雨打还是春去秋来，他日日都在，一写就是几十载。他书写的的看似是疯狂，又像是真理，模糊、混沌、捉摸不清。一条蜿蜒的红线记载了老人的路程，一头连着彼生，一头连着来世。我们知道，他是一个有良心的人，因为他的良心会说话，你听...

“...艹。”