拉格朗日乘数进行优化有着非常广泛的应用。

每当我们遇到约束的优化问题时，我们需要它们。这里有些例子：

1. 对冲基金希望决定在其投资组合中包含的股票比例，以便他们获得最大可能的预期回报，保持在一定的风险偏好范围内（风险可以根据回报的方差来衡量）。

2. 学区想要为他们的学生确定午餐菜单上各种项目的分配。他们希望尽量减少每顿午餐的成本，同时确保孩子们获得一定数量的所有必需营养素。

3. 货运公司希望将货物从源仓库运输到目的地城市。考虑到每个仓库 - 城市对的运输成本，每个仓库的总供应量和每个城市的总需求，决定从每个仓库到每个城市的运输量，以便最大限度地降低总体成本并满足需求（约束）。

我们可以看到，约束优化可以解决从物流到金融领域中出现的许多实际的现实问题。

本文将从没有约束的朴素优化开始。然后，我们将添加等式约束。然后，我们将描述具有相等和不等式约束的完全一般约束优化问题的解（KKT条件。最后，我们展示了这些条件对某些问题的影响力。

不受约束的优化

在这种情况下，我们在控制中有一些变量，并且取决于它们的目标函数。变量没有约束，目标函数最小化。

在任何时候，对于一维函数，函数的导数指向增加它的方向（至少对于小步骤）。意味着如果我们有一个函数f（x）并且导数f'（x）是正的，那么增加x将增加f（x）并且减小它将减小f（x）。如果我们最小化f（x），我们只需要与f'（x）的符号相反的一小步，以减小f（x）。如果我们处于f'（x） = 0的位置怎么办？这时候，我们可能达到f（x）的最佳值，因为没有其他地方可去。

如果有多个变量（比如x和y），我们可以得到每个变量。如果我们取这两个数并从它们构造一个二维向量，我们得到函数的梯度。现在，沿着梯度的方向移动将增加功能，而与其相反的移动将减小它（对于小步骤）。

这意味着只要梯度非零，我们就不能处于最小值，因为我们可以沿着与梯度相反的方向简单地迈出一小步，并进一步减小函数。这意味着对于使函数最小化的点的必要（但不充分）条件是该点处的梯度必须为零。

让我们举一个具体的例子，以便我们可以看到它的样子。考虑函数f（x，y）=x²+y²。这是抛物面并且当x = 0且y = 0时最小化。关于x和y的导数分别变为2x和2y。因此，梯度变为矢量∇f= [2x，2y]。我们可以看到，只有当x = 0且y = 0时，这才为零。否则，梯度指向f（x，y）将增加的方向。因此，与梯度相反的方向将减小f（x，y）。

如下图所示，粉红色曲线是目标函数f（x，y），其在绿点（0,0）处被最小化。紫色箭头是梯度，指向f（x，y）将增加的方向。因此，为了减少它，我们向相反的方向移动，直到我们达到绿点。

图1：具有梯度的抛物面

总而言之，在优化函数时，f在无约束优化问题中，处于局部最优的必要（但不充分）条件是：

∇f= 0

这就像你在山顶（这将是一个最大值）。你怎么知道你在顶端？无论你走哪个方向，最终都会降低你的高度。所以你肯定在局部的最佳位置。现在，旁边可能还有另一座山，甚至更高。所以，你可能不会处于全局最佳状态。

事实上，如果我们将地球的表面视为我们的领域（以及海拔高度作为我们的目标函数），如果你位于任何旧山（或建筑物）的顶部，那么你就处于当地的最佳状态。只有当这座山是珠穆朗玛峰时才具有全球最佳。在本文中，我们将满足于找到一个本地最优。

等式约束

对于无约束最小化/最大化问题，我们只需寻找梯度为零向量的点。如果梯度不是零，我们只需向与其指向相反的方向迈出一小步并继续这样做，直到我们到达它的某个点是零，因此，没有其他地方去，这种优化方法称为梯度下降。

请注意，我们不必完全沿着梯度移动。只要我们沿着梯度具有正投影（阴影）的方向移动，我们最终增加目标函数（如果我们沿负梯度具有正投影，则减小）。下图说明了这一点。绿色箭头是蓝色平面的梯度（因此垂直于它），红色箭头是负梯度。由于浅蓝色箭头位于平面上，如果我们沿着它们迈出一步，则平面方程将产生0。黄色箭头沿着绿色箭头具有正阴影（投影）。

所以，沿着它们移动将导致在插入平面方程时产生正数的点（"增加"它）。类似地，粉红色箭头沿着红色箭头具有正阴影（反向梯度）。因此，沿着它们移动将导致在插入平面方程时产生负数的点（"减小"它）。

图2：平面相对侧的矢量

对于非约束最小化，我们寻找梯度为零的点。这是因为如果不是，我们可以通过与梯度相反来减少目标函数。

同样的想法可以扩展到我们有等式约束的情况。像以前一样，我们需要找到一个我们无法找到任何可能的方向来移动目标函数减少的点。对于无约束优化，这仅仅意味着不存在这样的方向。当我们有约束时，还有另一种可能性。如果存在降低目标函数的方向，但是约束条件禁止我们采取任何步骤。

这意味着等式约束的存在实际上降低了条件对梯度的严格性。虽然对于没有等式约束的局部最优值需要为零，但现在可以为非零，只要沿着具有正阴影的任何方向移动都会导致我们违反约束。这只能在约束平面垂直于梯度时发生（如图2中的平面和绿色箭头）。

让我们回到目标函数f（x，y）=x²+y²。让我们添加一个等式约束，y = 1。这是一架飞机。在下面的图3中，目标函数为粉红色，平面为蓝色。由于我们被限制留在飞机上，我们无法沿着平面的梯度（下图中的蓝色箭头）向任何方向移动，因为这会增加或减少方程。约束，而我们希望保持不变。该平面与我们的目标函数（粉红色抛物面）的方程相交，曲线是抛物线。

下图中的粉红色箭头是沿该抛物线的各个点处的目标函数的梯度。如果粉红色箭头沿蓝色平面有投影，我们可以沿与该投影对应的矢量相反的方向移动。这将使我们保持在飞机上，确保我们不会违反约束，同时仍然减少目标函数。但是，在下图3中的绿点处，粉红色箭头（目标函数的梯度）沿蓝色平面无任何投影。换句话说，粉红色箭头平行于蓝色箭头（它是约束平面的梯度）。

图3：约束梯度与最佳的目标函数梯度对齐

为了减小目标函数，我们需要沿着负梯度具有阴影的方向移动。但是一旦我们这样做，我们最终会离开约束的平面。因此，约束使得不可能在绿点处进一步降低目标函数。这意味着它必须是当地的最小值。检查这种情况的简单方法是要求目标函数的粉红色梯度平行于约束平面的蓝色梯度。如果两个向量是并行的，我们可以将其中一个作为另一个的倍数。我们称之为多个λ。如果目标函数的梯度是∇f而约束的梯度是∇c，则上述条件是：

∇f=λ∇c

上面的λ称为拉格朗日乘数。因此，我们现在有一个具体的条件来检查何时寻找约束优化问题的局部最优。

不等式约束

不等式约束意味着您必须停留在定义约束函数的边界的一侧而不是它（对于等式约束的情况）。例如，呆在围栏的边界内。如果我们知道如何处理不等式约束，我们就可以解决任何约束优化问题。这是因为等式约束可以转换为不等式约束。假设我们需要：c（x）= 0.另一种表达方式是：c（x）≥0且c（x）≤0。因此，每个等式约束总是可以用两个不等式约束代替。

正如具有等式约束的约束优化可以使用上一节中描述的拉格朗日乘数来处理，因此可以使用不等式约束来约束优化。将不等式约束条件与等式约束区分开来的是，不等式约束的拉格朗日乘数必须是正的。要了解原因，请再次考虑朝着梯度上具有正分量的方向迈出一小步。如果我们可以沿着这个方向迈出一步（如果我们正在最大化;如果我们正在最小化的话，则与之相反）; 我们不能达到最大值/最小值。对于不等式约束，这转化为拉格朗日乘数为正。为了了解原因，让我们回到我们之前考虑的约束优化问题（图3）。

min：f（x，y）=x²+y²

subject：c（x，y）= y-1 = 0

现在，让我们将等式约束改为不等式。这可以通过两种方式完成，但结果完全不同。我们可以要求：

c（x，y）= y-1≥0。

在这种情况下，约束允许图3中蓝色平面前面的任何东西。很容易看出图3中的绿点仍然是局部最优点。此外，由于蓝色箭头表示约束梯度，粉红色箭头表示目标函数的梯度点在同一方向，我们有：

∇f=λ∇c

λ> 0。

另一种可能性是，c（x，y）= y-1≤0。现在，可行区域成为蓝色平面背后的一切。约束梯度将翻转。所以，图3最终看起来像这样：

图4：从图3中翻转不等式约束的符号

1. 绿点不再是当地的最佳点，因为我们可以自由移动到（0,0）; 这是上图4中的黄点。

2. 在绿点，我们仍然有∇f=λ∇c。由于蓝色矢量指向粉红色矢量，我们有λ<0。

因此，很明显，对于不等式约束，条件∇f=λ∇c表示仅当λ> 0时我们才处于局部最优。

将所有这些放在一起，以解决一般优化问题：

min f（x）

subject：

对于i∈Equality，c_i（x） = 0

对于i∈Inequality，c_i（x）≥0

我们获得了当地最佳所需的全套条件：

拉格朗日乘数条件：

∇f=Σ_iλ_i∇c_i（x）+Σ_jλ_j∇c_j（x）; 公式（1）

其中i∈Equality和j∈Inequality约束。

所有i的c_i（x）= 0; 公式（2）

所有j的c_j（x）≥0; 公式（3）

λ_j≥0; 公式（4）

还要注意，对于我们考虑的两个不等式约束问题，当我们得到y-1≥0时，图3中的绿点就是解。此时，我们在约束平面上（y-1 = 0）。所以，我们实际上有c（x）= 0和λ> 0。

另一方面，当我们考虑y-1≤0时，图4中的黄点（x = 0，y = 0）成为局部最小值。这一点也是解决非约束问题的方法。所以，我们这里只是∇f= 0。由于拉格朗日条件需要∇f=λ∇c，我们得到λ∇c= 0.现在，此时∇c≠0，这意味着我们必须得到：λ= 0。

这意味着如果约束是活动的（c（x）= 0），我们应该有λ≥0而如果它不是（c（x）≠0）我们应该有λ= 0。因此，在所有情况下，其中一个应为零。这导致了最终条件（互补条件）：

对于所有j∈不等式，λ_jc_j（x）= 0; 公式（5）

等式（1）到（5）被称为KKT条件。请注意，我们并没有真正为它们提供严格的证明，只是根据简单的例子构建它们。

代码示例

然而，对于具有更易管理的约束条件的更简单的问题，我们可以利用可以解决大多数（更一般的）多项式约束多项式程序的算法。这意味着目标函数和约束可以是任意多项式函数。这是因为存在用于求解称为"Buchberger算法"的多项式方程组的一般框架，并且上述KKT条件可以简化为多项式方程组。让我们构建我们的第一个约束优化问题。

等式约束

最小化：x³+y³取决于：x²+y²= 1

请注意，约束（x²+y²= 1）意味着我们位于具有单位半径的圆的边界上。所以，我们可以说：x = cos（t），y = sin（t）。然后目标函数变为：sin³（t）+cos³（t）。如果我们用t绘制它，我们得到如下图：

图5：目标函数sin³（t）+cos³（t）用约束边界处的t绘制

我们可以看到t = 0，π/ 2和5π/ 4对应于局部最大值，而t =π/ 4，π和3π/ 2对应于局部最大值。现在我们事先知道了答案，让我们看看上面描述的KKT条件是否也可以找到它们。

等式（1）给出（取目标函数和约束的导数）：

[3x²，3y²] =λ[2x，2y]

将两边的矢量的两个分量等同，得出两个等式：

3x²-2λx= 0

3y²-2λy= 0

等式（2）只需要满足等式约束：

X 2 + Y 2 = 1

由于没有不等式约束，我们不需要等式（3）至（6）。

不等式约束

现在，让我们将平等约束从上面的问题转变为不等式约束，看看它如何改变我们的解决方案。

最小化：x³+y³取决于：x²+y²≤1

如果约束暗示我们只能在前一种情况下位于单位圆的边界上，我们现在可以在其中的任何位置。

约束磁盘内目标函数的完整热图如下图所示（看起来像是在右上角附近有星的行星）。红色箭头是约束边界的渐变，而黑色箭头是目标函数的渐变。

图6：在磁盘x²+y²≤1内绘制的x³+y³

虽然等式约束问题是一维问题，但这种不等式约束优化问题是二维的。虽然只有两种方法可以在一个维度（从左或右）接近一个点; 在两个维度上有无数种方法可以接近它。这意味着我们需要提防马鞍点。这些是有资格成为最佳点的点，但不是真正的最佳点，因为当你从一个方向接近它们时它们是最大值，而当你从另一个方向接近它们时它们是最小值。下图显示了鞍点的样子。

图7：鞍点

Maxima从一个方向接近它，但是当你从另一个方向接近它时最小。

因此，在等式约束的情况下，我们需要重新评估局部最小值或最大值的所有点，并确保它们都不会成为鞍点。

图5告诉我们t = 0（x = 1，y = 0）是沿边界逼近时的局部最大值。

类似地，我们可以认为t =π和t =3π/ 2是局部最小值，无论我们从可行区域内部接近它们。

现在，让我们看看KKT条件对我们的问题所说的话。将目标函数和约束插入到KKT方程（1）到（5）中，我们得到：

式6（a）到（e）