主要内容

课程: 多变量微积分 > 单元 3

课程 4: 受约束的优化 (文章)

拉格朗日乘数, 介绍

Google课堂

"拉格朗日乘数法" 是解决约束优化问题的一种方法。倍有用!

背景知识

我们要做的是什么:

拉格朗日乘数法使得当对于你能够被允许使用的输入值存在一些条件时，你能够找到一个多元函数 $f (x, y, \dots)$ ‍的最大值或最小值。
这种方法只适用于看起来像这样的限定条件:

$g (x, y, \dots) = c$ ‍

这里

g

是另外一个和

f

具有相同输入空间的多元函数，且

c

是常数。

和新想法就是找到 $f$ ‍和 $g$ ‍等高线彼此相切的点。
这就如同找到使得 $f$ ‍和 $g$ ‍的梯度向量彼此平行的点。
整个过程可以被归结为设置一个特定函数，被叫做拉格朗日，使得它的梯度等于零向量。
步骤 1: 引入一个新的变量 $λ$ ‍, 并定义一个新的函数 $L$ ‍ , 如下所示:
$L (x, y, \dots, λ) = f (x, y, \dots) - λ (g (x, y, \dots) - c)$ ‍
函数 $L$ ‍ 叫做 "拉格朗日函数", 新的变量 $λ$ ‍ 即所谓的 "拉格朗日乘数"
步骤 2: 将 $L$ ‍ 的梯度设置为零向量.
$\nabla L (x, y, \dots, λ) = 0 \leftarrow 零向量$ ‍
换句话说, 我们要求解 $L$ ‍ 的临界点 .
步骤 3: 考虑每个解 $(x_{0}, y_{0}, \dots, λ_{0})$ ‍. 将每个解代入 $f$ ‍. 或者, 先去掉 $λ_{0}$ ‍ 分量, 然后代入 $f$ ‍, 这是因为 $λ$ ‍ 不是 $f$ ‍ 的一个输入. 那个使函数值最大 (最小) 的解就是你要求的最大 (或最小) 的点.

激励的例子

假设你要最大化此函数:

$f (x, y) = 2 x + y$ ‍

但是, 让我们假设你将自己限制在满足以下公式的输入值

(x, y)

$x^{2} + y^{2} = 1$ ‍

换句话说，

单位圆

上，哪个点

(x, y)

的

2 x + y

值最大？

这就是所谓的约束优化问题。对与满足

x^{2} + y^{2} = 1

的点的限制被称为 "约束", 而

f (x, y) = 2 x + y

是需要优化的函数。

这里有一种可视化的方法: 首先绘制

f (x, y)

的图像, 它看起来像一个倾斜得平面，因为

f

是线性的。接下来，将圆

x^{2} + y^{2} = 1

从

x y

平面垂直投影在

f

的图像上。我们寻找的最大值对应于图像上投影的圆的最高点。

可汗学院视频播放器

查看视频字幕

更一般的形式

通常, 约束优化问题涉及最大化最小化一个多变量函数, 该函数的输入具有任意数量的维度:

$f (x, y, z, \dots)$ ‍

不过, 它的输出将始终是一维的, 因为向量值结果没有一个明确的 "最大" 概念。

拉格朗日乘数法所使用的约束类型必须采取其他多元函数

g (x, y, z, \dots)

的形式使其被设定等于常数

c

$g (x, y, z, \dots) = c$ ‍

由于这意味着对

f

输入值的约束,

g

的输入值的纬数和 i

f

一样. 比如，上面概述的例子符合此一般形式，如下所示：

$f (x, y) = 2 x + y$ ‍

$g (x, y) = x^{2} + y^{2}$ ‍

$c = 1$ ‍

使用等高线图

如果我们不使用图像，而是用等高线可视化

f

，关于这个问题的推理将变得更容易。

作为提醒，

f (x, y)

的等高线是满足对于常数

k

，

f (x, y) = k

的所有点的集合。后面的交互工具展现的这条线（以蓝色绘制）是怎样随着常数

k

的变化而改变。圆

g (x, y) = 1

也显示出来 (红色). 在一直允许

f

的等高线和圆相交的情况下尝试让

k

尽可能大／小。

概念检查：如果对于一个特定的

k

值，表示

f (x, y) = k

的蓝线不和表示

g (x, y) = 1

的圆相交，那意味着什么?

请注意，该圆圈中

g (x, y) = 1

可以被认为是函数

g

的等高线。因此，有了这些，下面是考虑约束优化问题的巧妙方法：

关键观察:

f

的最大值和最小值, 受约束条件

g (x, y) = 1

, 对应于和

g (x, y) = 1

相切的

f

的等高线。

如果

f

是不同的函数,它的轮廓可能并不总是直线。我们的例子是独特的，因为

f

是线性的。比如，请看一下这个函数：

$f (x, y) = 2 x^{2} + \sqrt{5 y}$ ‍,

其等高线如下所示:

尽管入此, 关键观察仍然有效，并且值的重复：当

k

是受约束的

f

的最大值或最小值,

f (x, y) = k

的等高线会和

g (x, y) = 1

表示的轮廓相切。

梯度起作用的地方

如何将两条等高线相切的想法构成一个可以求解的公式？

为了回答这个问题, 我们转向我们的忠实朋友-- gradient。有许多方法来解释

\nabla f

: 最陡峭的上升方向, 一个计算方向导数的工具, 等等。但就我们这里的目的而言, 我们关心的属性是 在点 $(x_{0}, y_{0})$ ‍上计算出的 $f$ ‍的梯度总是给出一个垂直于通过该点的等高线的矢量。

这就意味着当两个函数

f

和

g

的等高线相切的时候, 它们的梯度向量是平行的。以下是对于任意函数

f

和

g

可能看起来的样子：

等高线是切线的事实并不能告诉我们每个梯度向量的大小, 但这没关系。当两个向量指向同一方向时, 这意味着我们可以将一个向量乘以某个常数来得到另一个向量。具体而言, 让

(x_{0}, y_{0})

表示一个特定的点, 其中

f

和

g

的等高线相切 (用

0

下标写

x_{0}

和

y_{0}

, 只是表示我们正在考虑常数, 因此也就是一个具体的点)。由于这种相切意味着它们的梯度向量对齐, 下面是你可以写下的内容:

$\begin{array}{r} \nabla f (x_{0}, y_{0}) = λ_{0} \nabla g (x_{0}, y_{0}) \end{array}$ ‍

这里,

λ_{0}

代表某个常数。一些作者使用负常数,

- λ_{0}

, 但是我个人更喜欢正常数, 因为它在之后给出了

λ_{0}

的更清晰的解释。

让我们看看在我们的例子中，当

f (x, y) = 2 x + y

和

g (x, y) = x^{2} + y^{2}

时是什么样子的。

f

的梯度是

$\begin{array}{r} \nabla f (x, y) = [\begin{array}{c} \frac{\partial}{\partial x} (2 x + y) \\ \frac{\partial}{\partial y} (2 x + y) \end{array}] = [\begin{array}{c} 2 \\ 1 \end{array}] \end{array}$ ‍

g

的梯度为

$\begin{array}{r} \nabla g (x, y) = [\begin{array}{c} \frac{\partial}{\partial x} (x^{2} + y^{2} - 1) \\ \frac{\partial}{\partial y} (x^{2} + y^{2} - 1) \end{array}] = [\begin{array}{c} 2 x \\ 2 y \end{array}] \end{array}$ ‍

因此, 相切条件的结果如下所示:

$\begin{array}{r} [\begin{array}{c} 2 \\ 1 \end{array}] = λ_{0} [\begin{array}{c} 2 x_{0} \\ 2 y_{0} \end{array}] \end{array}$ ‍

在特定情况下解决问题

总之, 我们目前的情况是, 我们正在寻找具有以下属性的输入点

(x_{0}, y_{0})

$g (x_{0}, y_{0}) = 1$ ‍, 这对于我们的示例意味着
$x_{0}^{2} + y_{0}^{2} = 1$ ‍
对于某常数 $λ_{0}$ ‍， $\nabla f (x_{0}, y_{0}) = λ_{0} \nabla g (x_{0}, y_{0})$ ‍ , 这对于我们的示例意味着
$\begin{aligned} 2 & = 2 λ_{0} x_{0} \\ 1 & = 2 λ_{0} y_{0} \end{aligned}$ ‍

有

3

个方程和

3

个未知数, 所以这是一个完全可以解决的情况。

该方法将首先解出

λ_{0}

，然后使用解来找到

x_{0}

和

y_{0}

。

使用上面的最后两个方程, 用

λ_{0}

来表示

x_{0}

和

y_{0}

。

$\begin{aligned} 2 & = 2 λ_{0} x_{0} \Rightarrow x_{0} = \frac{1}{λ_{0}} \\ 1 & = 2 λ_{0} y_{0} \Rightarrow y_{0} = \frac{1}{2 λ_{0}} \end{aligned}$ ‍

现在要引入第三个方程, 请将这些结果代入方程

x_{0}^{2} + y_{0}^{2} = 1

。

\begin{aligned} {x_{0}}^{2} + {y_{0}}^{2} & = 1 \\ {(\frac{1}{λ_{0}})}^{2} + {(\frac{1}{2 λ_{0}})}^{2} & = 1 \\ \frac{1}{λ_{0}^{2}} + \frac{1}{4 λ_{0}^{2}} & = 1 \end{aligned}

为了从分母中获得

λ_{0}

, 我们将所有量乘以

4 λ_{0}^{2}

并简化。

\begin{aligned} 4 + 1 & = 4 λ_{0}^{2} \\ \frac{5}{4} & = λ_{0}^{2} \\ \pm \sqrt{\frac{5}{4}} & = λ_{0} \\ \frac{\pm \sqrt{5}}{2} & = λ_{0} \end{aligned}

使用我们上面找到的

x_{0}

和

y_{0}

关于

λ_{0}

的表达式，这两个解对应两对答案

$\begin{aligned} (x_{0}, y_{0}) & = (\frac{1}{λ_{0}}, \frac{1}{2 λ_{0}}) \\ = (\frac{2}{\sqrt{5}}, \frac{1}{\sqrt{5}}) or (\frac{- 2}{\sqrt{5}}, \frac{- 1}{\sqrt{5}}) \end{aligned}$ ‍

我们可以通过将这些解代入

f (x, y)

并查看哪个更大, 来决定其中哪一个是最大点, 哪一个是最小点。

\begin{aligned} f (\frac{2}{\sqrt{5}}, \frac{1}{\sqrt{5}}) & = 2 \frac{2}{\sqrt{5}} + \frac{1}{\sqrt{5}} \\ = \frac{5}{\sqrt{5}} \\ = \sqrt{5} \leftarrow Maximum \\ f (- \frac{2}{\sqrt{5}}, - \frac{1}{\sqrt{5}}) & = 2 \frac{- 2}{\sqrt{5}} + \frac{- 1}{\sqrt{5}} \\ = \frac{- 5}{\sqrt{5}} \\ = - \sqrt{5} \leftarrow Minimum \end{aligned}

拉格朗日函数

在1700代, 我们的哥们约瑟夫·路易斯·拉格朗日研究了这种约束优化问题, 他找到了一个巧妙的方法来用单一方程表达我们所有的条件。

你可以写出这些条件并且通常指明我们是要寻找常数

x_{0}

y_{0}

和

λ_{0}

来满足以下条件:

约束 :
$g (x_{0}, y_{0}) = c$ ‍
相切条件:
$\nabla f (x_{0}, y_{0}) = λ_{0} \nabla g (x_{0}, y_{0})$ ‍.
这可以分解成以下几个部分:
$f_{x} (x_{0}, y_{0}) = λ_{0} g_{x} (x_{0}, y_{0})$ ‍
$f_{y} (x_{0}, y_{0}) = λ_{0} g_{y} (x_{0}, y_{0})$ ‍

lagrange写下了一个特殊的新函数, 它包括了所有跟

f

和

g

相同的输入变量, 以及镇上的新孩子

λ

，这里它被认为是一个变量, 而不是一个常数。

$L (x, y, λ) = f (x, y) - λ (g (x, y) - c)$ ‍

比如，考虑我们上面的例子。

\begin{aligned} f (x, y) & = 2 x + y \\ g (x, y) & = x^{2} + y^{2} \\ c & = 1 \end{aligned}

这就是这个新函数看起来的样子

$L (x, y, λ) = 2 x + y - λ (x^{2} + y^{2} - 1) .$ ‍

注意，

L

关于

λ

的偏导数是

- (g (x, y) - c)

：

\begin{aligned} L_{λ} (x, y, λ) & = \frac{\partial}{\partial λ} (f (x, y) - λ (g (x, y) - c) \\ = 0 - (g (x, y) - c) \end{aligned}

所以我们把条件

g (x, y) = c

转化为

\begin{array}{r} L_{λ} (x, y, λ) = - g (x, y) + c = 0 \end{array}

并且，看一下当我们把其中一个偏导数设为

0

时我们得到了什么：

\begin{aligned} L_{x} (x, y, λ) & = 0 \\ \frac{\partial}{\partial x} (f (x, y) - λ (g (x, y) - c)) & = 0 \\ f_{x} (x, y) - λ g_{x} (x, y) & = 0 \\ f_{x} (x, y) & = λ g_{x} (x, y) \end{aligned}

那刚好是我们的条件中的另一个！几乎完全一样，条件

L_{y} (x, y, λ) = 0

转化为

\begin{array}{r} f_{y} (x, y) = λ g_{y} (x, y) \end{array}

总之, 这些条件和以下表达是一致的。

\begin{array}{r} \nabla f (x, y) = λ \nabla g (x, y) \end{array}

因此, 我们需要解决的三个条件，以找到

x, y

和

λ

简化为了各种偏导数

L

等于

0

。这可以通过将

L

的梯度设置为零向量来编写的非常紧凑：

\begin{array}{r} \nabla L = 0 \end{array}

例如, 使用上面的特定函数, 我们可以看到这是如何构建我们需要解决的方程组的：

\begin{array}{r} \nabla L = [\begin{array}{c} \frac{\partial}{\partial x} (2 x + y - λ (x^{2} + y^{2} - 1)) \\ \frac{\partial}{\partial y} (2 x + y - λ (x^{2} + y^{2} - 1)) \\ \frac{\partial}{\partial λ} (2 x + y - λ (x^{2} + y^{2} - 1)) \end{array}] = [\begin{array}{c} 2 - 2 λ x \\ 1 - 2 λ y \\ - x^{2} - y^{2} + 1 \end{array}] = [\begin{array}{c} 0 \\ 0 \\ 0 \end{array}] \end{array}

作为对ol' Joey Lou的赞扬, 我们将这个函数

L

叫做 "拉格朗日", 并且将我们引入的新变量

λ

叫做"拉格朗日乘数"。想象如果有某个人在你的姓氏后面加上“的”，然后让它成为每个人使用的函数的名字。那真贴心！

警告: 一些作者习惯将

λ

符号反过来：

\begin{array}{r} L (x, y, λ) = f (x, y) + λ (g (x, y) - c) \end{array}

这在解决问题方面没有任何区别, 但你应该记住它, 以防你正在学习的课程或你正在阅读的文本遵循这个惯例。

旁白: 如果约束不是那么约束呢？

这就需要一点调整, 最好用一个例子来说明。

假设我们需要最大化函数

\begin{array}{r} f (x, y) = e^{- (x^{2} + y^{2})} \end{array}

受到约束

\begin{array}{r} g (x, y) = x - y = 0 \end{array}

f (x, y) = e - (x^{2} + y^{2})

的图形是 “钟形曲线”, 在点

(x_{0}, y_{0}) = (0, 0)

上方有一个圆凸起, 如上图所示。

此约束可以在

x y

平面上显示为对角线 (以红色显示)。

让这个问题有点傻的是,

f

的(无约束)最大点

(0, 0)

已经满足约束

g (x, y) = 0

, 因为

\begin{array}{r} g (0, 0) = 0 + 0 = 0 \end{array}

可能会觉得这让我们的事情变得更容易。毕竟, 不用担心约束应该比担心约束更直接, 对吧？但是, 如果你(或更现实的是计算机) 正在解决给定的约束优化问题, 则不是首先找到不受约束的最大值, 检查它是否符合约束, 然后转向拉格朗日乘数法。你会只从拉格朗日乘数法开始, 因为几乎从来没有不受约束的最大值也是受约束的最大值。

事实证明，当受约束的最大值也是无约束的最大值时，拉格朗日乘数法仍然有效。原因有点微妙，因为我们上面的轮廓相切论证并不十分适用。

例如, 让我们研究

e^{- (x^{2} + y^{2})} = k

所表示的轮廓随

k

在

0.5

和

1

之间的变化的情形:

表示

e^{- (x^{2} + y^{2})} = k

的轮廓总是穿过

x + y = 0

这条线，并且在

k

最大的时候这个轮廓会收缩到一个点。之前，我们说当

f

达到有约束的最大值时等高线会相切，但是说一个点和一条线相切听起来很奇怪。

那为什么这不是个问题呢？

如果

f

在某个点

(x_{0}, y_{0})

处达到不受约束的本地最大值, 则其在该点的梯度将为

0

。

\begin{array}{r} \nabla f (x_{0}, y_{0}) = 0 \end{array}

你可以把这看作是说在局部最大处的切平面是水平的。

在这种情况下,如下性质

\begin{array}{r} \nabla f (x_{0}, y_{0}) = λ \nabla g (x_{0}, y_{0}) \end{array}

仍然成立, 因为我们可以设置

λ = 0

。

一个有趣的思考方式是说一个点与通过它的所有线 "相切", 这与零向量与所有其他向量是 "成比例" 的异曲同工。

因此, 拉格朗日乘数法不仅巧妙地将许多条件整合到一个方程中

\begin{array}{r} \nabla L = 0, \end{array}

它也会自动考虑到这个特殊的边缘情况!

总结

多元函数

f (x, y, \dots)

的约束条件是, 另一个多元函数

g (x, y, \dots) = c

等于一个常数. 如果你想最大化(或最小化)这个多元函数f, 你可以遵照下面的步骤进行:

步骤 1: 引入一个新的变量 $λ$ ‍, 并定义一个新的函数 $L$ ‍ , 如下所示:

$L (x, y, \dots, λ) = f (x, y, \dots) - λ (g (x, y, \dots) - c)$ ‍

函数

L

叫做 "拉格朗日函数", 新的变量

λ

即所谓的 "拉格朗日乘数"

步骤 2: 将 $L$ ‍ 的梯度设置为零向量.
$\nabla L (x, y, \dots, λ) = 0 \leftarrow 零向量$ ‍

换句话说, 我们要求解

L

的临界点 .

步骤 3: 考虑每个解 $(x_{0}, y_{0}, \dots, λ_{0})$ ‍。将每个解代入 $f$ ‍。或者, 先去掉 $λ_{0}$ ‍ 分量, 然后代入 $f$ ‍, 这是因为 $λ$ ‍ 不是 $f$ ‍ 的一个输入. 那个使函数值最大 (最小) 的解就是你要求的最大 (或最小) 的点.

想加入讨论吗？

排序方式:

尚无帖子。

你会英语吗？单击此处查看更多可汗学院英文版的讨论.