Question

有时候，在x的所有可能值下最大化或最小化一个函数f(x)不是我们所希望的。相反，我们可能希望在x的某些集合中找f(x)的最大值或最小值。这称为约束优化（constrained optimization）。在约束优化术语中，集合内的点x称为可行（feasible）点。

我们常常希望找到在某种意义上小的解。针对这种情况下的常见方法是强加一个范数约束，如。

约束优化的一个简单方法是将约束考虑在内后简单地对梯度下降进行修改。如果使用一个小的恒定步长，我们可以先取梯度下降的单步结果，然后将结果投影回。如果使用线搜索，我们只能在步长为范围内搜索可行的新x点，或者可以将线上的每个点投影到约束区域。如果可能，在梯度下降或线搜索前将梯度投影到可行域的切空间会更高效（Rosen，1960）。

一个更复杂的方法是设计一个不同的、无约束的优化问题，其解可以转化成原始约束优化问题的解。例如，我们要在中最小化f(x)，其中x约束为具有单位L²范数。我们可以关于θ最小化，最后返回［cosθ，sinθ］作为原问题的解。这种方法需要创造性；优化问题之间的转换必须专门根据我们遇到的每一种情况进行设计。

Karush-Kuhn-Tucker（KKT）方法⁽²⁾是针对约束优化非常通用的解决方案。为介绍KKT方法，我们引入一个称为广义Lagrangian（generalized Lagrangian）或广义Lagrange函数（generalized Lagrange function）的新函数。

为了定义Lagrangian，我们先要通过等式和不等式的形式描述。我们希望通过m个函数g⁽ⁱ⁾和n个函数h^(j)描述，那么可以表示为。其中涉及g⁽ⁱ⁾的等式称为等式约束（equality constraint），涉及h^(j)的不等式称为不等式约束（inequality constraint）。

我们为每个约束引入新的变量λ_i和α_j，这些新变量被称为KKT乘子。广义Lagrangian可以定义为

现在，我们可以通过优化无约束的广义Lagrangian解决约束最小化问题。只要存在至少一个可行点且f(x)不允许取∞，那么

与如下函数有相同的最优目标函数值和最优点集x

这是因为当约束满足时，

而违反任意约束时，

这些性质保证不可行点不会是最佳的，并且可行点范围内的最优点不变。

要解决约束最大化问题，我们可以构造−f(x)的广义Lagrange函数，从而导致以下优化问题：

我们也可将其转换为在外层最大化的问题：

等式约束对应项的符号并不重要，因为优化可以自由选择每个λ_i的符号，我们可以随意将其定义为加法或减法。

不等式约束特别有趣。如果，我们就说说这个约束h⁽ⁱ⁾(x)是活跃（active）的。如果约束不是活跃的，则有该约束的问题的解与去掉该约束的问题的解至少存在一个相同的局部解。一个不活跃约束有可能排除其他解。例如，整个区域（代价相等的宽平区域）都是全局最优点的的凸问题可能因约束消去其中的某个子区域，或在非凸问题的情况下，收敛时不活跃的约束可能排除了较好的局部驻点。然而，无论不活跃的约束是否被包括在内，收敛时找到的点仍然是一个驻点。因为一个不活跃的约束h⁽ⁱ⁾必有负值，那么中的α_i=0。因此，我们可以观察到在该解中。换句话说，对于所有的或在收敛时必有一个是活跃的。为了获得关于这个想法的一些直观解释，我们可以说这个解是由不等式强加的边界，我们必须通过对应的KKT乘子影响x的解，或者不等式对解没有影响，我们则归零KKT乘子。

我们可以使用一组简单的性质来描述约束优化问题的最优点。这些性质称为Karush-Kuhn-Tucker（KKT）条件（Karush，1939；Kuhn and Tucker，1951）。这些是确定一个点是最优点的必要条件，但不一定是充分条件。这些条件是：

广义Lagrangian的梯度为零。

所有关于x和KKT乘子的约束都满足。

不等式约束显示的“互补松弛性”：。

有关KKT方法的详细信息，请参阅Nocedal and Wright（2006）。