约束优化

此时，我们可以使用精确解、近似解或启发式方法解决几乎任何优化问题。但我们尚未学习如何处理约束。

请回忆优化问题的一般形式：

$$\min_x f(x) \\ \text{s.t.: } x \in C$$

其中，$x$ 可以是一个数、一个向量或一个矩阵。第二行是约束条件，它告诉我们 $x$ 必须满足某些性质。

约束

约束是对所有可能解的集合施加的限制。当存在约束时，我们不能再考虑所有的解；只能考虑满足约束的那些解。这些有效解构成的空间称为可行区域。与此相对，不满足约束的解构成的空间称为不可行区域。

人们很容易认为约束是有益的。毕竟，它们缩小了解空间，减少了需要探索的解的数量。然而实际情况恰恰相反。虽然在某些情况下约束会使问题更简单，但大多数时候它们反而使问题更加复杂。例如，获取可行区域并排除不可行区域往往非常困难。因此，我们必须额外检查一个解是否有效，这成为算法中的一个额外步骤，可能导致运行时间显著增加。

不过，我们也可以采用其他技术来处理约束。我们将学习如何通过修改目标函数来消除约束。在后续讨论具体问题的方法时，还会介绍针对特定问题处理约束的其他方式。

等式约束与不等式约束

尽管约束可以有多种形式，但主要有两类：等式约束和不等式约束。这两类是优化中最常见的类型。例如，考虑以下问题：

$$\min_{x, y} -3x + 12y \\ \text{s.t.: } 3x + 4y \leq 9 \\ \quad\quad\quad 3x + 3y \geq 3 \\ \quad\quad\quad 3x + 6y \geq 8$$

所有约束均为不等式约束。它们使用不等号比较运算符（$<$、$>$、$\leq$、$\geq$）。每一个这样的约束将平面划分为两个区域：可行与不可行。每个约束所定义的可行区域的交集，即为整个问题的可行区域。如下图所示：

图中浅蓝色区域即为可行区域。围成该区域的每一条直线，都是由前述各约束对原始平面进行划分的结果。因此，不等式约束所定义的可行区域是原解空间的一个子集。这个子集与原空间具有相同的维度——如果原空间是二维平面，则可行区域也是二维平面（尽管该区域可能是有界的）。

那么等式约束的情况如何？

让我们在前面的问题中加入一个等式约束：

$$\min_{x, y} -3x + 12y \\ \text{s.t.: } 3x + 4y \leq 9 \\ \quad\quad\quad 3x + 3y \geq 3 \\ \quad\quad\quad 3x + 6y \geq 8 \\ \quad\quad\quad 2x + 3y = 5$$

下图中加入了新的等式约束。

现在有一条红色直线穿过之前的可行区域。与不等式约束不同，等式约束不会生成与原空间同维的新区域，而是生成一个维度更低的新区域。在此例中，原本的二维区域退化为一维线段。新的可行区域是这条红线上位于浅蓝色区域内部的那一段。我们的最优解应位于这条线段上的某一点。

需要注意的是，整个问题的可行区域是每个约束所定义可行区域的交集。因此，如果这个交集为空，则称该问题为不可行，即无解。

例如，若等式约束对应的直线完全位于浅蓝色区域之外，则所有可行区域的交集为空，问题不可行。

接下来，我们将学习如何处理不同类型约束，并掌握如何运用已有技术来求解带约束的优化问题。