拉格朗日乘子，KKT条件和对偶性-直观解释
拉格朗日乘子、KKT条件与对偶性：直观解释掌握支持向量机、正则化、主成分分析等机器学习概念的关键
在本文中，我们将深入探讨数学优化中的三个相关概念。对于我来说，理解这些概念需要耗费大量的时间和精力，因此我希望以直观的方式向所有读者呈现。我们的旅程将从无约束优化开始，接着考虑受限优化，我们将利用拉格朗日乘子和KKT条件。我们还将探讨这些观念之间的相互作用以及它们与对偶概念之间的联系。
无约束优化
在无约束优化中，我们给定一个多变量函数f(u)，我们想找到向量u*的值，使得函数f(u*)的值是最优的（最大或最小）。
如上所示，一般情况下一个函数可以有多个最大值和最小值。在经典机器学习和本文中，我们主要关注凸函数（也要求满足充分平滑性）。凸函数意味着该函数最多具有一个最优值（当函数是损失函数时是一个最小值），如下图所示：
处理凸函数要容易得多，因为否则很难确定找到的最小值是否是所有最低的（即全局最小值），而不仅仅是某个局部最小值。一般而言，即使只有一个最小值，也可能有许多满足它的点（例如，如果函数是平坦的），我们将假设这种情况不会发生以简化说明；假设这种情况发生不会改变我们得出的任何内容。
对于给定的多变量函数f(u)执行无约束优化是可能的，方法是求解∇ᵤf(u) = 0。如果f(u)是n个变量（u₁、u₂、…、uₙ）的函数，则这是一个包含n个方程的系统：
解决这个系统方程后，会返回最优解u*=(u*₁,u*₂，…，u*ₙ)，其中发生最优值（例如，最小值）。
要了解这个来自哪里，回想一下:
- 在任意点 u 处的切平面的法向量采用以下形式 (∂f(u)/∂u₁, ∂f(u)/∂u₂, …, ∂f(u)/∂uₙ, f(u))
- 任何极小值或极大值的切平面是水平的（直观显而易见）
- 因此，只要∇ᵤf(u) = 0 成立，那个点就有一个水平的切平面，因此必须是我们要找的极小值。
另一个解释这一点，并且即将有用的方法是观察到梯度指向最大增加的方向（以及相反的最大减少的方向）。因此，当∇ᵤf(u) = 0 成立时，要么不可能从该点开始增加函数（即，在极大值），要么是不可能从该点开始减少函数（即，在极小值）。
无约束优化总结
给定: f(u)求解: 使 f(u) 最小的 u方法: 求解 ∇ᵤf(u) = 0，因为它在极小值处成立
约束优化
在这种类型的优化中，我们给定一个形式为 g(u)=0 或 g(u)≤0 的等式约束（如果需要，我们可以通过重新排列项或乘以一个负数来将其转化为这种形式），并且我们想要在仅限于满足约束的所有点上进行优化。
我们通常假设等式约束 g(u)=0 是仿射的（线性的推广），而不等式约束 g(u)≤0 包含凸函数，以便整个优化问题是凸优化问题（否则，仅仅 f(u) 是凸的可能不足以保证一个最优值）。
带等式约束的约束优化
在这种情况下，我们给定一个多变量函数 f(u) 和一个约束 g(u)=0，我们想要找到点 u*，其中 g(u*)=0 并且 f(u*) 是最小值（即，在满足约束的情况下的最低可能点）。
例如，在所示的例子中，目标函数为 f(u₁,u₂) = u₁+ u₂（3D 平面），约束为 u²₁+ u²₂=1（2D 圆）。目标是找到平面上满足 u²₁+ u²₂=1 的最低点对应的点（即，在平面上的圆投影的最低点发生的 (u₁, u₂)）。
解决这种类型的约束优化问题的一种方法是使用拉格朗日乘数法。简单来说，拉格朗日乘数定理指出，对于形式为：
最小化 f(u) 满足 g(u)=0
的优化问题的任何解 u*，必须满足方程∇ᵤL(u*,λ)=0，其中 λ∈R（自然地，g(u*)=0），其中 L 是拉格朗日函数，它由 L(u,λ)=f(u)+λg(u) 给出。它假设 ∇ᵤg(u*)≠0。
由此可见，我们可以通过以下方法解决具有等式约束的约束优化问题（假设∇ᵤg(u*)≠0）：
- 编写拉格朗日函数 L(u,λ) = f(u) + λg(u)。
- 求解 n+1 个方程 ∇ᵤL(u,λ) = 0（n个方程），其中 g(u)=0，以找到 n+1 个未知数 u*₁，u*₂，…，u*ₙ，λ。
- 解为 u* = (u*₁，u*₂，…，u*ₙ)
λ称为拉格朗日乘子。我们只需要找到它，因为它是产生解 u* 的系统的一部分。
您可以在此处计算上图中对应的示例。在此示例中，问题不是凸问题，解的结果可能不是最小值或最大值。请注意，步骤（1）和（2）等同于对函数 L(u,λ) = f(u) + λg(u) 进行无约束优化。也就是说，设定：
∇ L(u,λ) = (∂L(u)/∂u₁, ∂L(u)/∂u₂, …, ∂L(u)/∂uₙ, ∂L(u)/∂λ) = 0
从这个意义上说，拉格朗日乘子的方法非常强大，因为它将约束优化问题转化为一个我们可以通过将梯度设置为零来解决的无约束优化问题。
原理
用直观解释这背后的原理并不难。有效区域是满足问题约束条件的点集（如上图中的圆上的点）；我们希望在这些点中找到目标函数最优的那个点。
我们知道，∇ f(u) 指向最大减小的方向（以及最大增加的方向的相反方向）。然而，在我们的情况下，我们只能在有效区域内移动（满足约束的点）；因此，为了在约束下最小化该函数，我们应该想要沿着约束曲线的最大减小方向移动（这样我们永远不会离开有效区域并达到最小值的点）。
假设约束曲线上点 u 处的切线方向由 r(u) 给出，根据向量投影的公式，我们希望朝着以下方向移动（∇ f(u) 在 r(u) 上的投影）的相反方向：
与上面的无约束情况类似，您应该意识到，当此值为0时，我们无法沿着约束的任何方向进一步增加 f(u)（如果处于最大值时）或减小它（如果处于最小值时）。
显然，要使此值为零，我们需要 r(u)≠0（因此分母不为零）且∇ f(u) ⋅ r(u)=0。对于后者，我们知道约束曲线∇ g(u)上的法向量与切线 r(u) 垂直。因此，我们只需要∇ f(u) 与 ∇ g(u) 平行即可。
因此，最优点 u* 必须满足以下条件：
- 约束的法向量不为零：∇ g(u*)≠0（以便 r(u*)≠0）
- 满足约束：g(u*)=0（平凡的要求）
- ∇ f(u*) ∥∇ g(u*)：存在某个实数 β，使得∇ f(u*) = β∇ g(u*)
请注意通过重新排列项并重命名-β，（3）等价于“存在某个实 λ，使得∇ f(u)+λ∇ g(u)=0”。换句话说，∇ᵤL(u,λ) = 0，并通过这样的方式，我们直观地推导出了一个约束条件的拉格朗日乘数定理（需要往上滚动以查看）。
请注意，第一个条件被称为约束条件限制。如果在满足（2）和（3）的点上不满足约束条件，那么无法保证该点是最优点，因为此时投影未定义。
多个等式约束
当存在多个约束条件 g₁(u), g₂(u),…,gₖ(u) 时，该方法可以顺利地推广为以下形式：
- 编写拉格朗日函数 L(u,λ₁,λ₂,…,λₖ) = f(u) + λ₁g₁(u) + λ₂g₂(u) +…+λₖgₖ(u)
- 通过设置∇ᵤL(u,λ₁,λ₂,…,λₖ) = 0（n个方程）和 g₁(u)=0, g₂(u)=0, …, gₖ(u)=0（k个方程），解一组由 n+k 个方程组成的方程，找到 n+k 个未知数 u*₁,u*₂,…,u*ₙ, λ₁,λ₂,…,λₖ 的值
- 解为 u* = (u*₁,u*₂,…,u*ₙ)
假设∇ g(u*)≠0 推广为∇ g₁(u), ∇ g₂(u),…,∇ gₖ(u) 必须线性无关。这被称为LICQ（线性独立约束条件限制）。
带不等式约束的约束优化
当我们处理形式为 g(u)≤0 的不等式约束时，问题不会变得更加复杂。在这种情况下，我们希望找到满足 g(u)≤0 的 f(u) 的最优点。
对于上述问题，这意味着可行区域不仅是圆上的点，还包括其中的点。显然，对于该特定问题（而不是普遍情况），这不会改变解。
我们不再解决拉格朗日乘数的两个条件（2, 3），而是解决一组称为 KKT 条件的四个条件，它们推广了拉格朗日乘数情况。我们可以按照以下方式导出它们：
观察到对于任意的超曲面 f(u) 和约束 g(u)≤0，假设具有一个最优值的凸平滑函数，有以下两种可能性：
- 最优点 uᴾ 在可行区域内。
- 在这种情况下，最优化问题u*的解必须是uᴾ，并且g(u*)<0必须成立（左图）。
- 在可行区域中找不到更优点，因为uᴾ是整个f(u)定义域中最优（最小）点。
2. 最优点uᴾ位于可行区域之外。
- 在这种情况下，如果该点是最大值，则f(u)在可行区域中必须只能减少（否则会产生另一个最优点）
- 在这种情况下，如果该点是最小值，则f(u)在可行区域中必须只能增加（否则会产生另一个最优点）
- 因此，最优点u*必须位于可行区域的边缘，因为在其内部它永远不会变得更好（g(u*) = 0必须成立）。
在第一种情况下，解决最优化问题与解决无约束版本是等价的。
∇ᵤf(u) = 0
我们说约束是“非活跃的”，因为它在最优化问题中没有任何影响。
在第二种情况下，解决最优化问题与解决等式约束版本是等价的（拉格朗日乘子法）。
该情况的唯一注意点是，对于最小化，λ必须≥0，而对于最大化，λ必须≤0。对于最小化，这意味着∇ᵤf(u)和∇ᵤg(u)指向相反的方向（即，在∇ᵤf(u) = β∇ ᵤg(u)中，β≤0），这必须成立，因为∇ᵤg(u)指向约束g(u)≥0的正面（基本属性）；同时，∇ᵤf(u)指向约束的负面，因为那里是f(u)增加的地方。对于最大化，可以轻松地构造类似的论证。
但是，我们事先不知道哪种情况适用。我们可以将它们的方法合并如下（假设最小化）：
- 编写Lagrangian函数L(u,λ)=f(u)+λg(u)
- 设置∇ᵤL(u,λ) = 0（n个方程）和g(u)≤0
- 求解解（u*₁,u*₂,…,u*ₙ,λ）其中适应上述情况之一：
- λ=0和g(u*)<0（当λ=0时，意味着∇ᵤL(u,λ) = ∇ᵤf(u) = 0，所以步骤1,2等价于解决∇ᵤf(u) = 0）
- g(u*)=0和λ≥0（当g(u)=0时，应用Lagrange是正确的，这就是我们所做的）
我们可以总结这两个情况为g(u*)≤0和λ≥0必须成立，且λg(u*)=0必须成立（λ或g(u*)中的一个必须为零）。这意味着给定形式的最优化问题：
最小化 f(u) 满足 g(u)≤0
我们预计最优点u*必须满足以下四个条件：
- 稳定点：∇ᵤL(u*,λ) = 0
- 原始可行性：g(u*)≤0
- 对偶可行性：λ≥0
- 互补松弛性：λg(u*)=0
解决这些条件，一起产生最优点u*。实际上，对于凸问题，这些条件足以但不必要地满足最优性。
- 如果一个点满足这些条件（例如通过一起解决它们找到），那就足以证明该点是最优的（不需要进一步寻找凸问题）。
- 与此同时，这些条件对于点的最优性并非必要。可能这些条件没有解，而实际上存在一个不满足条件的最优点。例如，考虑f(x) = x和约束x² ≤ 0（此文档中已解决这个和另一个KKT示例）
一旦我们强制执行类似于之前提到的LICQ（限制条件充分且必要），我们可以保证KKT条件既是充分又是必要的。作为一个更容易检查的替代限制条件，Slater条件确保了对于凸问题KKT是必要且充分的。
Slater条件简单地表示可行域必须具有内部点。也就是说，对于约束g(u)≤0，函数必须具有在f(u)定义域内满足g(u)<0的点。这是一个基本条件，在现实生活问题中几乎总是满足的（但不是上面的反例），这意味着KKT很少会错过找到最优解。
多个约束条件
当存在多个等式约束h₁(u), h₂(u),…,hₖ(u)以及多个不等式约束g₁(u), g₂(u),…,gₚ(u)时，该方法通过编写完整的Lagrange函数并仅对不等式约束及其乘子（我们将其称为α）检查KKT条件来顺利推广：
0. 编写Lagrange函数
- 设置∇ᵤL(u,λ₁,λ₂,…,λₖ, α₁, α₂, …, αₚ) = 0（n个方程）
2. 设置h₁(u)=0, h₂(u)=0, …, hₖ(u)=0（k个方程），并设置g₁(u)≤0, g₂(u)≤0, …, gₚ(u)≤0（p个不等式）
3. 设置α₁≥0, α₂≥0, …, αₚ≥0（p个不等式）
4. 设置α₁g₁(u) = α₂g₂(u) = αₚgₖ(u) = 0（p个方程）
总共，您将有n+k+p个方程和2p个不等式，您将同时解决它们以找到n+k+p个变量（u*₁,u*₂,…,u*ₙ,λ₁,λ₂,…,λₖ,α₁, α₂, …, αₚ），从而得到满足k+p个约束的最小化函数的解u*=(u*₁,u*₂,…,u*ₙ)。
对偶原理
对偶原理简单地表示对于任何优化问题，我们可以编写一个对偶优化问题，当解决它时，会告诉我们关于原始问题（称为原始问题）的一些信息或者解决它。
对于任何形式的优化问题：
对偶优化问题的形式为：
如果为最大化，则反之成立。
示例
例如，我们之前讨论的约束优化问题：
对应的对偶问题为：
根据基本微积分的推断，为了进行最小化，我们首先进行下面这个步骤：
这暗示着
因此，优化问题变为
现在只需对其进行微分，并令其等于零，即可得到 λ = 1/√2 ，暗示着 (x*, y*) = (−1/√2, −1/√2) 这是通过解决原始问题而得到的相同解，即使通过 KKT 。
推导对偶
最初的原问题为
假设我们定义一个函数，当 u 不在可行区域内（不满足约束条件）时返回无穷大，否则返回零：
在这种情况下，原问题等效于
这是有意义的，因为 f(u)+P(u) 将超出可行区域的任何值设置为无穷大，而将可行区域保持不变。即使约束条件是明确强制执行的，该总和的最小值仍必须出现在可行区域中，因为无穷大大于任何值。
观察到我们可以宣称：
因为如果：
- g(u)<0 ，那么根据之前定义的 P(u)=0，因为 λ=0 必须保持以最大化 λg(u) 的数量（否则由于 g(u)<0 因此为负）
- g(u)=0 ，那么根据之前定义的 P(u)=0，因为λg(u) 将为零（λ可以是任何值）
- g(u)>0 ，那么根据之前定义的 P(u)=∞，因为 λ=∞ 是使 λg(u) 最大化的值
因此，原问题等效于
与对偶问题的不同之处在于对偶中的 Max 和 Min 是交换的。
因此，因为通常情况下 MinMax(…) ≥ MaxMin(…) ，对偶的解将是原始问题的下界。这被称为弱对偶性。
更有趣的情况是当 MinMax(…) = MaxMin(…) 时，对偶的解将完全等于原始问题的解（如示例所示）。这被称为强对偶性。你可以相对容易地证明当 KKT 是必要且充分的时，等式成立（因此是强对偶性）。换句话说，只有在 Slater 条件成立时，凸问题才满足强对偶性！
那又怎样？
如果你仔细思考一下，解决对偶问题就像在原始问题上只应用KKT的稳定性和对偶可行性条件一样。你不再需要应用原始可行性和互补松弛条件，而是要处理额外的对偶变量的最小化。在许多情况下，这比在原始问题上解决KKT要容易得多。这个额外的最小化可以用线性或二次规划来处理。
多个约束条件？
当推广到多个约束条件时，Lagrange乘子的变化就如你所料（类似于我们所看到的那样），我们只需要在最大化中添加α≥0的条件与不等式约束相关的乘子。
希望这个故事能帮助你真正理解无约束优化、Lagrange乘子、KKT和对偶性。下次再见，再见！
