Multi-objective optimization — 多目标优化

多目标优化（也称为多目标规划，英语：multi-objective optimization, multi-criteria optimization）是数学优化的一个分支，研究同时优化两个或多个目标函数（准则）的问题，这些目标函数通常相互冲突。从形式上看，该问题被表述为在可行解集上最小化一个向量目标函数。

定义与术语

多目标优化问题的一般形式如下： $\underset{x\in S}{\min }\{f_1(x),f_2(x),\dots ,f_k(x)\}$ 其中 $S\subseteq {\mathbb{ℝ}}^n$ 是非空可行解集，而 $f_i:S\to \mathbb{ℝ}$ 是目标函数（$k\ge 2$）。向量 $f(x)=(f_1(x),\dots ,f_k(x))$ 称为目标向量。

与标量优化不同，在多目标问题中通常不存在能够同时改善所有准则值的单一解。因此，经典的最优概念通过帕累托最优性概念得到推广。

• 帕累托解（帕累托最优解或有效解）：一个可行解 $x^{*}\in S$，不存在另一个解 $x\in S$ 使得对于所有的 $i=1,\dots ,k$ 都有 $f_i(x)\le f_i(x^{*})$，并且至少存在一个索引 $j$ 使得 $f_j(x)<f_j(x^{*})$。换言之，如果一个解的任何一个目标值都无法在不使其他至少一个目标值变差的情况下得到改善，那么这个解就是帕累托最优的。
• 帕累托前沿（或帕累托集）：所有与帕累托最优解对应的目标向量的集合。
• 弱帕累托最优解：一个解 $x^{*}\in S$，不存在另一个解 $x\in S$ 使得对于所有的 $i$ 都有 $f_i(x)<f_i(x^{*})$。

关键性质与定理

• 加权和定理：在凸问题（其中所有函数 $f_i(x)$ 和集合 $S$ 均为凸）中，任何帕累托最优解 $x^{*}$ 都是某个标量加权和最小化问题 $\underset{x\in S}{\min }\sum _{i=1}^k{w}_i{f}_i(x)$ 的解，其中权重 $w_i\ge 0$ 为非负数。然而，在非凸问题中，该方法可能无法找到帕累托前沿的某些部分。

• 卡罗需-库恩-塔克（KKT）最优性条件：光滑问题的必要最优性条件可推广到多目标情况。在帕累托最优点，存在一个非零的非负乘子（权重）集合，使得目标函数的梯度和活跃约束的梯度是线性相关的。

• 解集的性质：帕累托前沿具有一系列重要的定性特征。其边界由理想点（由所有目标函数的逐元素最小值构成）和天底点（由前沿上的逐元素最大值构成）限定。

示例

• 线性问题：在约束 $x_1+x_2\le 1$，$x_1,x_2\ge 0$ 下，最小化 $f_1(x)=-x_1$ 和 $f_2(x)=-x_2$。在这里，改善一个目标（例如，增加 $x_1$）必然导致另一个目标（$x_2$ 减少）的恶化。帕累托最优解集是线段 $x_1+x_2=1$。
• 非凸问题：在区间 $[0,2]$ 上最小化 $f_1(x)=x^2$ 和 $f_2(x)=(x-2{)}^2$。帕累托前沿是非凸的。使用正权重的加权和方法无法找到该区间内的解（例如，在点 $x=1$ 处），因为目标的线性组合只会在端点 $x=0$ 或 $x=2$ 处达到最小值。

相关概念与应用

多目标优化与多准则决策（MCDM）密切相关，后者研究如何根据决策者的偏好选择最佳备选方案。将多目标问题转化为标量问题（标量化）的主要方法包括：

• 加权和法。
• $\epsilon$-约束法：优化一个目标，而将其余目标转化为 $f_i(x)\le {\epsilon }_i$ 形式的约束。该方法能够找到前沿非凸部分上的解。

多目标优化在工程设计、经济学（例如，投资组合优化）、管理和生态学中有着广泛的应用。

参见

• 帕累托最优
• 向量优化
• 决策理论
• 决策支持系统
• 运筹学

注释

Category:Decision analysis