拉格朗日乘子法（二）

Joseph Louis Lagrange

多个约束条件

引言

现在我们来看看，在一般情况下，当我们在 k个约束条件下： $g_i(x_1, …, x_n) = 0$ ，其中 $i$ 从 $1$ 到 $k$ ，求最小化 $n$ 个变量的函数 $f(x_1, …, x_n)$ 。拉格朗日函数和前文一样，除了每个约束有不同的 $\lambda$ 。
约束：

L (x_{1}, . . ., x_{n}, λ_{1}, . . ., λ_{k}) = f (x_{1}, . . ., x_{n}) - k \sum j = 1 λ_{j} g_{j} (x_{1}, . . ., x_{n})

$L(x_1, ..., x_n, \lambda_1, ..., \lambda_k) = f(x_1, ..., x_n) - \sum_{j=1}^k \lambda_j g_j(x_1, ..., x_n)$

(我们将 $j$ 用于 $k$ 作为约束索引，将 $i$ 用于 $n$ 作为变量的索引 $x_i$ 。)约束最小值出现在所有变量对 $L$ 的偏导数为零的点上。

简单例子

我们将使用一个相对简单的例子来说明方法：我们试图最小化 $x_1^2 + x_2^2 + x_3^2$
有两个约束条件： $x_1 = 1$ 和 $x_2 = 1$
Lagrangian: $x_1^2 + x_2^2 + x_3^2 - \lambda_1 (x_1 - 1) - \lambda_2 (x_2 - 1)$
它的偏导数是：

\begin{matrix} \partial L / \partial x_{1} & = & 2 x_{1} - λ_{1} \partial L / \partial x_{2} & = & 2 x_{2} - λ_{2} \partial L / \partial x_{3} & = & 2 x_{3} \partial L / \partial λ_{1} & = & - (x_{1} - 1) \partial L / \partial λ_{2} & = & - (x_{2} - 1) \end{matrix}

$\begin{array}{rcl} \partial L / \partial x_1 &=& 2 x_1 - \lambda_1 \\ \partial L / \partial x_2 &=& 2 x_2 - \lambda_2 \\ \partial L / \partial x_3 &=& 2 x_3 \\ \partial L / \partial \lambda_1 &=& -(x_1 - 1) \\ \partial L / \partial \lambda_2 &=& -(x_2 - 1) \end{array}$

解

将它们全部设置为零得到答案： $(x_1, x_2, x_3) = (1, 1, 0)$ 和 $\lambda_1 = \lambda_2 = 2$ .

在一个约束情形中，拉格朗日乘子方程等价于矢量方程 $\nabla f = \lambda \nabla g$
对于多个约束，相应的向量方程是：

\nabla f = k \sum j = 1 λ_{j} \nabla g_{j}

$\nabla f = \sum_{j = 1}^k \lambda_j \nabla g_j$

解释

上述等式将得出以下事实：对于变量 $i$ ，当 $\partial L / \partial x_i = \partial f / \partial x_i - \sum_{j=1}^k \lambda_j \partial g_j / \partial x_i$ 成立时有 $\partial f / \partial x_i = \sum_{j=1}^k \lambda_j \partial g_j / \partial x_i$ ，因此把 $\partial L / \partial x_i$ ( $i$ 从 $1$ 到 $n$ )偏导数置为零等效于上述向量方程。注意，将偏导数 $\partial L / \partial \lambda_j$ 等于零只会强化 $g_j(x_1, …, x_n) = 0$ 的约束。

如何相切

在一个约束情形中，找到点是有用的， $\nabla f = \lambda \nabla g$ 因为这意味着水平曲线 $f$ 与水平曲线 $g$ 相切。在多重约束的情况下，它并不那么简单。单个约束 $g_i$ 的水平表面不一定与 $f$ 约束最小值处的水平表面相切。（在上面的示例中，约束平面 $x_1 = 1$ 与 $f$ 球体的水平面 $x_1^2 + x_2^2 + x_3^2 = 2$ 在最佳点处相交 $(1, 1, 0)$ 。）相反，事实证明，所有 $g_i$ 水平面的交点都与 $f$ 水平面的相切。

为了更好的理解，让我们直接看 $x$ 的小扰动对 $f$ 和约束方程 $g_j$ 的影响，有 $x = (x_1, …, x_n)$ ，同时使 $\Delta x = (\Delta x_1, …, \Delta x_n)$ 我们有：

f (x + Δ x) - f (x) \approx n \sum i = 1 Δ x_{i} \frac{\partial f}{\partial x_{i}}

$f(x + \Delta x) - f(x) \approx \sum_{i=1}^n \Delta x_i \frac{\partial f}{\partial x_i}$

条件

如果更改 $x$ ，有扰动 $\Delta x$ 能保持所有 $g_j$ 约束方程有相同的（一阶导），同时引起 $f(x)$ 的非零变化，则 $x$ 不可能是受约束的局部最小值。因为在某些方向上沿的交点移动所有的水平曲线 $g_j$ 都会导致 $f$ 减少（或增加）。所以我们想要的条件是：

对于所有可能使 $\nabla g_j(x) \perp \Delta x$ ,( $j$ 从 $1$ 到 $k$ ) 成立的 $\Delta x$ ，有 $\nabla f(x) \perp \Delta x\textrm{.}$

对每个 $j$ 有 $\nabla g_j(x) \perp \Delta x$ , $\Delta x$ 在与 $g_j$ 水平面相切的方向上。如果 $\Delta x$ 在与所有的 $g_j$ 水平面交点相切的方向上，那么每一个 $j$ 都成立。条件一表示任何此类 $\Delta x$ 也与水平面相切 $f$ 。另一方面，拉格朗日乘子法强制执行的条件是：

存在 $\lambda_1$ 到 $\lambda_k$ 使得 $\nabla f = \sum_{j = 1}^k \lambda_j \nabla g_j$ .

令人高兴的是，事实证明条件1和2等价。

定理：条件1和2等价

证明

证明:(为什么现在我们一整天挥手都有严格的证据？有时最直观的论证就是证明;也许就是这种情况。）首先我们将证明2、1等价.假设对于每一个 $j$ 从 $1$ 到 $k$ ，有 $\nabla f = \sum_{j = 1}^k \lambda_j \nabla g_j$ , $\nabla g_j(x) \perp \Delta x$ 。因为 $\nabla g_j(x) \perp \Delta x$, $\nabla g_j(x) \cdot \Delta x = 0$ 。所以 $\nabla f \cdot \Delta x = (\sum_{j = 1}^k \lambda_j \nabla g_j) \cdot \Delta x = \sum_{j = 1}^k \lambda_j \nabla g_j \cdot \Delta x = 0.$ 。这意味着 $\nabla f \perp \Delta x$ 。

接下来我们将证明1意味着2，或等效地，不是2意味着不是1.否定2表示 $\nabla f$ 不在向量的跨度内。让我们用 $z$ 来表示 $\nabla f$ 在 $\nabla g_j$ 跨度内的投影，并设置 $\Delta x = \nabla f - z$ 。我们将证明这是建立否定条件1的反例。

证否

我们知道 $\nabla f \neq z$ 所以有 $\Delta x \neq 0$ ，通过投影的定义，对每个 $j$ 有 $\Delta x \perp g_j$ 。此外， $\nabla f \cdot \Delta x = (z + \Delta x) \cdot \Delta x = z \cdot \Delta x + \Delta x \cdot \Delta x$ ，因为 $z$ 是在 $g_j$ 域上垂直于 $\Delta x$ ，同样的有 $z \perp \Delta x$ 。
新增 $z \cdot \Delta x = 0$ 和 $\Delta x \cdot \Delta x \neq 0$ ，我们得到 $(z + \Delta x) \cdot \Delta x \neq 0$ 。也就是说 $\nabla f \cdot \Delta x \neq 0$ ，所以 $\nabla f$ 不垂直 $\Delta x$ 。由于 $\Delta x$ 垂直于所有 $\nabla g_j$ ，但不垂直 $\nabla f$ ，所以条件一也被证否。我们假设条件2的否定，因此这表明不是2意味着不是1，或者等效地，1意味着2。

小结

现在我们已经看到拉格朗日乘子法通过找到 $x$ 一组 $\lambda_j$ 这样 $\nabla f = \sum_{j = 1}^k \lambda_j \nabla g_j$ 的东西而发挥作用。这个等式意味着不存在局部变化，使一阶导数，符合所有约束但改变目标函数 $f$ 的值。因此满足该等式的值 $x$ 是受约束的局部最小值或最大值的候选值。求解该向量方程等效于将拉格朗日函数的偏导数设置为零。

我希望能够说明拉格朗日乘子法的工作方式和原因，并稍使它们看起来不这么像魔术。

后记

感觉原文作者描述的非常严谨，有很多地方我没法跟上作者的思路。
就我个人较感性的理解

单约束的表达式中：

L (x, y, λ) = f (x ， y) - λ g (x, y)

$L(x, y, \lambda)= f(x，y) - \lambda g(x, y)$

拉格朗日函数偏导为零，表明梯度 $\nabla f=(\frac{\partial f}{\partial x}, \frac{\partial f}{ \partial y})$ ，和梯度 $\nabla g=(\frac{\partial g}{\partial x}, \frac{\partial g}{ \partial y})$ 成比例。
只有在切点处才有梯度重叠，才可以向量互相线性表示；
在切点处是局部的极值点，任何符合 $g$ 的微小扰动 $(\Delta x, \Delta y)$ 会导致函数 $f$ 的增大或减小。
所以解 $L$ 偏导等于零的方程组(2+1)，可以得到候选极值点。

在多约束表达式中：

L (x_{1}, . . ., x_{n}, λ_{1}, . . ., λ_{k}) = f (x_{1}, . . ., x_{n}) - k \sum j = 1 λ_{j} g_{j} (x_{1}, . . ., x_{n})

$L(x_1, ..., x_n, \lambda_1, ..., \lambda_k) = f(x_1, ..., x_n) - \sum_{j=1}^k \lambda_j g_j(x_1, ..., x_n)$

有多变量，多约束条件；可以认为是求解极值向量的问题
多约束的条件下，单条件相切并不一定是局部极值；
需要做到 $f$ 与所有 $g_i$ 的相交处相切，即在约束面上各方向目标函数偏导数为零处。
梯度的原理同单约束，梯度向量在各方向上成比例。

{⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} λ_{1} λ_{2} . . . λ_{k} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠}^{T} . ⎛ ⎜ ⎜ ⎜ ⎝ \begin{matrix} \nabla g_{1} \nabla g_{2} . . . \nabla g_{k} \end{matrix} ⎞ ⎟ ⎟ ⎟ ⎠ = \nabla y

$\begin{pmatrix} \lambda_1 \\ \lambda_2 \\ ...\\ \lambda_k \\ \end{pmatrix}^T .\begin{pmatrix} \nabla g_1\\ \nabla g_2 \\ ...\\ \nabla g_k \\ \end{pmatrix}=\nabla y$

在局部最优解的向量上，符合所有约束 $g$ 的微小扰动向量 $(\Delta x_1, \Delta x_2, …\Delta x_n)$ 都会导致函数 $f$ 的增大或减小。
所以解 $L$ 偏导等于零的方程组(n+1)，可以得到候选极值向量。

g (x_{1}, x_{2}, z_{3}) = x_{1}^{2} + x_{2}^{2} + x_{3}^{2} x_{1}^{2} + x_{2}^{2} + x_{3}^{2} = 2 x_{1} = 1 x_{2} = 1

$g(x_1, x_2, z_3) = x_1^2 + x_2^2 + x_3^2 \\ x_1^2 + x_2^2 + x_3^2 = 2 \\ x_1 = 1 \\ x_2 = 1$

将目标函数约束到三维空间，超平面中的球体半径为所求目标函数的值。

在 $(1, 1, 0)$ 处球体与约束平面相切，取到极值2。

https://danstronger.wordpress.com/2015/08/08/lagrange-multipliers/
https://jermmy.github.io/2017/07/27/2017-7-27-understand-lagrange-multiplier/
https://www.svm-tutorial.com/2016/09/duality-lagrange-multipliers/