1.5 约束优化和多目标优化

非线性优化 在无约束时可行域 D = R ⁿ ，但实际问题通常存在一些约束条件。例如，圆拟合中心角之和需要等于360°，每天工作时间不能超过24小时，等等，这些均构成约束优化。

约束非线性优化一般形式为

其中 x ∈ R ⁿ ， f ： R ⁿ → R ， g _i ： R ⁿ → R ， h _i ： R ⁿ → R 均为数量值函数。

矩阵形式为

其中， g ： R ⁿ → R ^m 和 h ： R ⁿ → R ^p 均为向量值函数。

1.5.1 等式约束

仅含等式约束的非线性优化为

其中， x ∈ R ⁿ ， f （·）： R ⁿ → R ， g （·）=（ g ₁ （·）， g ₂ （·），…， g _m （·）） ^T ： R ⁿ → R ^m ， m ≤ n ，向量值函数 g 连续可微。

任何类似式（1-68）中的等式约束，都可以等价地分解为两个不等式约束：

从而成为不等式约束，即可以使用1.5.2节不等式约束优化的通用方法，这是通用的解决方法。

当然单独处理约束问题也很常见。此时需要借助一些人为的技巧，尝试将等式约束优化转换为无约束优化，从而可以借用1.2节和1.3节的无约束优化方法。

例如，对于约束优化：

min（ x sin x ）

s.t.2≤ x ≤6

针对 x 的约束2≤ x ≤6，设计以下函数进行转换：

从而转换为无约束优化

min{ φ （ y ）sin（ φ （ y ））}

即

这样就可以使用1.3节的各种（无约束）非线性优化方法。

以下通过一个具体示例，演示求解约束型优化的拉格朗日乘子法。

简单起见，将向量值约束函数 g （ x ）=0简化为数量值约束函数 g （ x ）=0，即考虑仅存在一个约束的情况，例如：

此时，简单地将约束函数 代入目标函数，即成为无约束优化问题：

对目标函数求导，并令导数为0：

解得 x ₂ =1.165，从而 x ₁ =1.358，即得到优化解：

x ^∗ =（1.358，1.165）

此时 x ^∗ 的位置是目标函数 f （ x ）等高线与约束函数 g （ x ）相切的位置，即沿着 g （ x ）进行微小移动不改变 f （ x ）函数值。

由于 g （ x ）的梯度▽ g （ x ）垂直于 g （ x ）的等高线， f （ x ）的梯度▽ f （ x ）垂直于 f （ x ）的等高线，因此两者方向相同，仅幅度可能存在差异，假设幅度相差 λ 倍，即

▽ f （ x ）= λ ▽ g （ x ）

其中，系数 λ 称为拉格朗日乘子，其通过以下拉格朗日方程给出：

通过 ，可进行以下两种操作：

（1） ，可以解得乘子▽ f （ x ）= λ ▽ g （ x ）；

（2） ，可以得到约束 g （ x ）=0。

进一步，增加约束数量，假设存在两个约束：

可以将其压缩为一个约束：

依照前述拉格朗日乘子法 ，即

可见，当存在 m 个约束，即约束方程为向量值函数 g （ x ）=0时，拉格朗日方程为

不失一般性，以3个变元的目标函数和 N 个约束函数为例：

可以构造拉格朗日函数：

矩阵形式为

对 x _i 和 λ _i 求偏导，即可得到拉格朗日条件。

1.5.2 不等式约束

如1.5.1节所述，任何等式约束均可转换为不等式约束，不等式约束的优化具有如下形式：

对于拉格朗日乘子法当中的乘子 μ ，当解 x ^∗ 位于不等式约束的边界上时，目标函数的梯度被约束函数严格限制，拉格朗日方程▽ f （ x ）- μ ▽ h （ x ）=0成立。而当解 x ^∗ 不在边界上时，可以引入以下惩罚方案：

（1）如果解 x ^∗ 可行，即满足约束 h （ x ）≤0，目标函数依然为 f （ x ）；

（2）如果解不可行，即不能满足约束，则惩罚性地增大目标函数，例如 f （ x ）→∞，即

综合以上，原来不等式的约束优化成为新的优化：

这个重新构造的极小极大问题称为原始问题，原始问题解的极值点 x ^∗ 需要满足：

（1）解是可行的， h （ x ^∗ ）≤0；

（2）惩罚指明正确方向， μ ≥0；

（3） μh （ x ^∗ ）=0，即边界可行点 h （ x ）=0而 h （ x ）＜0的可行点 μ =0；

（4）▽ f （ x ^∗ ）- μ ▽ h （ x ^∗ ）=0。

以上四点要求扩展到含有等式和不等式约束的优化问题：

对应的要求就成为

（1）可行性， ；

（2）对偶可行性， μ ≥0；

（3）互补松弛， μ ☉ h （ x ^∗ ）=0，即 μ =0或 h （ x ）=0；

（4）平稳性，目标函数与每个积极约束相切。

上述要求称为KKT条件。此时拉格朗日方程为

矩阵形式为

其中， λ 为拉格朗日乘子， μ 为KKT乘子。由此得到新的优化问题：

然后，类似前述使用偏导条件，即可求得拉格朗日乘子向量和KKT乘子向量。

以上极小极大问题有时难以优化，可以证明，极小极大顺序能够交换，从而可以采用：

该极大极小问题称为原始问题的对偶问题。

可以通过解决对偶问题来解决原始问题，例如核方法的支持向量机。

1.5.3 多目标优化

前述各节的目标函数均为数量值函数 f （ x ），也就是单目标优化。向量值目标函数的优化问题min f （ x ）称为多目标优化，此时需要同时优化多个目标函数，从而达到帕累托最优。

在单目标优化时，解的优劣判别是不言自明的：给定两个候选解 x 和 ，如果 ，则 x 就优于 。在多目标优化中，目标函数 f （ x ）返回 m 维的向量值，每个维度对应了一个指标。帕累托最优是指改善一个指标必须以恶化其他指标作为代价。其等价描述是：只有当 x 在至少一个指标表现更好，而在其他指标都不差时，才可以比较向量 x 和 的优劣。也就是称 x 优于 ，如果

多目标优化可以根据对指标的偏好把偏好程度编码为权值向量 w ，从而将多目标转换为单目标优化：

这种加权和方法中的权值向量 w 可以解释为每个指标所关联的成本，满足：

例如对于双目标优化，通过设定 w ₂ =1- w ₁ ，然后将 w ₁ 从0到1遍历二维权重空间，即可得到双目标的优化解。 vKDX0VBlM/TV928byfrbGih+9k8bfG+ffDlaA1daZfE4m2edL7BV2Y/2Ak8Lknva