aiwiki.page
中文
数学 / 应用与计算数学 / pareto-frontier

帕累托前沿

帕累托前沿是所有可行结果中,任何一个目标的改善都必然导致至少另一个目标变差的结果集合。

19 个关键词1 个词条链接到这里AI 撰写
多目标优化数学优化可行集目标函数偏序欧几里得空间紧致空间连续函数帕累托前沿

帕累托前沿是多目标问题中所有非支配结果构成的集合:对于这些结果,改善一个目标必然会使至少另一个目标变差。它是多目标优化的核心概念。在这类问题中,相互竞争的目标通常使得任何单一解都无法在所有方面达到最优。帕累托前沿刻画了有效的权衡方案,但其本身并不决定应当选择哪种权衡。

数学定义

考虑一个数学优化问题,其可行集为 XX,有 mm 个需要最小化的目标:

f:X⟶Rm,f(x)=(f1(x),…,fm(x)).f:X\longrightarrow\mathbb{R}^{m}, \qquad f(x)=\bigl(f_1(x),\ldots,f_m(x)\bigr).

每个 fif_i 都是一个目标函数。集合

Y=f(X)Y=f(X)

是目标空间中所有可达结果的集合。

若满足

yi≤zifor every i,yj<zjfor at least one j.y_i\leq z_i \quad \text{for every }i, \qquad y_j<z_j \quad \text{for at least one }j.

则称结果 y∈Yy\in Y 支配另一个结果 z∈Yz\in Y。

也就是说,yy 在任何目标上都不比 zz 差,并且在至少一个目标上严格优于 zz。帕累托前沿定义为

P(Y)={y∈Y:∄ z∈Y such that z dominates y}.\mathcal{P}(Y)= \left\{ y\in Y: \nexists\,z\in Y \text{ such that }z\text{ dominates }y \right\}.

决策空间中相应的帕累托最优集为

XP={x∈X:f(x)∈P(Y)}.X_{\mathrm P} = \{x\in X:f(x)\in\mathcal{P}(Y)\}.

两者是不同的对象:最优集包含的是决策,而前沿包含的是这些决策对应的目标向量。多个不同的决策可能产生前沿上的同一个点。

对于最大化问题,不等号方向相反。对于既有最大化目标又有最小化目标的混合问题,可以将每个需要最大化的目标 fif_i 替换为 −fi-f_i,从而将其转化为最小化问题。

支配关系不能给出完全排序

逐分量比较定义的是一种偏序,而非完全排序。两个结果可能无法比较:例如,其中一个可能成本较低,但能耗较高。前沿汇集了那些无法仅凭支配关系比较加以排除的结果。

这使帕累托最优与最小化单一数值评分有所区别。评分包含了在不同目标之间进行权衡的规则,而支配关系不需要这样的规则。

示例

假设四种设计方案的成本和能耗如下,两者都需要最小化:

设计方案 成本 能耗
A 1 5
B 2 3
C 3 4
D 4 2

方案 B 支配方案 C,因为 B 的成本和能耗都更低。A、B、D 中任意两个方案之间都不存在支配关系。因此,前沿由以下结果构成:

{(1,5),(2,3),(4,2)}.\{(1,5),(2,3),(4,2)\}.

选择 A 意味着优先考虑成本,选择 D 则意味着优先考虑能耗。选择 B 则是接受一种居中的权衡。帕累托分析将 C 排除在有效集之外,但并不确定其余方案中哪一个更值得选择。

不应直接将列出的点连接成一条可行曲线。只有在原问题允许的情况下,这些点之间的中间结果才存在。

几何形态与存在性

在两个目标均需最小化的图中,前沿位于可达集左下方体现权衡关系的边界上。当目标数为三个时,前沿可能形成一个曲面;目标更多时,它则位于更高维的欧几里得空间中。

“前沿”一词并不意味着该集合是光滑的、连通的,甚至不意味着它是连续的。前沿可能由孤立点、彼此分离的部分、曲线或曲面组成。并非每个边界点都是帕累托最优的:一些边界点会被其他可达结果支配。

如果 YY 是有限非空集,其前沿必定非空。对于连续问题,一个实用的充分条件是:XX 非空且为紧空间,并且每个目标函数都是连续函数。此时,YY 是紧的。将各目标以严格为正的权重加权求和并最小化,可以得到至少一个帕累托最优结果,其存在性由极值定理保证。

如果缺乏适当的假设,前沿未必存在。例如,如果一个需要最小化的单目标可以取 (0,1)(0,1) 内的任意值,那么每个可行值都可以进一步改善,因此不存在非支配结果。

理想点与纳迪尔点

理想点的各坐标等于相应目标单独能够达到的最优值:

ziideal=inf⁡x∈Xfi(x).z_i^{\mathrm{ideal}}=\inf_{x\in X} f_i(x).

理想点不一定可达,因为不同目标各自取得最优值所需的决策可能互不相容。

当相关的上确界均为有限值时,纳迪尔点记录了帕累托前沿上每个目标的最差值:

zinadir=sup⁡y∈P(Y)yi.z_i^{\mathrm{nadir}} = \sup_{y\in\mathcal{P}(Y)}y_i.

它通常不同于在整个可行集上逐分量取最差值所得到的结果。理想值和纳迪尔值有助于描述目标的取值范围,并对权衡关系进行归一化处理。

相关的有效性概念

如果不存在一个可行结果在每个目标上都严格更优,则称该结果为弱帕累托最优。这一条件弱于通常的帕累托最优条件。

例如,在 (1,2)(1,2) 和 (1,3)(1,3) 这两个结果中,两者都是弱帕累托最优的,因为没有一个结果能在两个坐标上都严格优于另一个。但只有 (1,2)(1,2) 是帕累托最优的,因为它支配 (1,3)(1,3)。

局部帕累托最优决策不会被与其足够接近的可行决策支配,但仍可能被距离较远的决策支配。因此,在非凸问题中,需要区分局部最优与全局最优。

适当有效性增加了额外限制,以排除某些无界的权衡情形,即一个目标上任意微小的改善,都需要以另一个目标上不成比例的巨大牺牲为代价。适当有效性有多种正式定义。

前沿的计算

支配筛选

对于有限个候选方案,可以通过剔除被支配的目标向量来找出前沿。一种直接的方法是逐对比较。对于 nn 个候选方案和 mm 个目标,以大O记号表示,这需要 O(mn2)O(mn^2) 次比较。

更高效的方法利用排序、几何性质或专门的数据结构。反复提取并移除非支配集,可以得到逐层的支配层级,这一过程通常称为非支配排序。

从样本中得到的前沿只是该样本的前沿。某个未被采样的可行结果可能支配其中的一个或多个点。

加权和标量化

一种常用方法是将向量目标替换为标量目标:

min⁡x∈X∑i=1mwifi(x),wi>0.\min_{x\in X} \sum_{i=1}^{m}w_i f_i(x), \qquad w_i>0.

每个全局最小解都是帕累托最优的。否则,支配它的某个可行决策将具有严格更小的加权和。

如果权重仅要求非负且不全为零,则只能保证最小解是弱帕累托最优的;在权重为零的目标上,它仍可能被支配。

改变权重可以找出不同的前沿点。然而,在非凸问题中,加权和法可能遗漏非支撑的帕累托最优结果。考虑

Y={(0,2),(1,1.5),(2,0)}.Y=\{(0,2),(1,1.5),(2,0)\}.

这三个结果都是非支配的,但无论如何选择严格为正的权重,中间的结果都不能使加权和达到最小。

在凸优化中,可以得到更强的结论。如果上像

Y+R≥0mY+\mathbb{R}^{m}_{\geq 0}

是一个凸集,则通过支撑超平面的论证可知,每个帕累托最优结果都能使某个权重非负且不全为零的加权和达到最小。要使这些权重严格为正,还需要额外条件,仅凭凸性无法保证这一点。

基于约束的方法与参考点方法

ε-约束法在最小化一个目标的同时,对其余目标设置上界:

min⁡x∈Xf1(x),subject tofi(x)≤εi,i=2,…,m.\begin{aligned} \min_{x\in X}\quad & f_1(x),\\ \text{subject to}\quad & f_i(x)\leq\varepsilon_i, \qquad i=2,\ldots,m. \end{aligned}

改变阈值可以找出加权和法遗漏的前沿区域。如果在多个并列最小解中任意选择,可能会得到被支配的结果,因此可能需要额外的择优规则或有效性检查。

参考点方法则寻找接近指定期望水平的结果。适当的建模形式,例如增广达成标量化函数,可以在纳入偏好的同时保证解的有效性。

近似算法

对于规模庞大、离散或求解成本高昂的问题,往往需要采用近似方法,而非精确枚举。进化算法、分解方法和数学规划技术旨在寻找一组分布具有代表性的非支配结果。

近似质量既取决于结果与真实前沿的接近程度,也取决于其对各种权衡方案的覆盖程度。超体积指标衡量的是相对于选定参考点,近似结果所支配区域的体积。其数值取决于该参考点以及各目标的尺度。

历史与应用

这一术语源自维尔弗雷多·帕累托在经济学中关于效率和福利的研究。在福利分析中,帕累托效率描述的是这样一种资源配置:如果不使其他人的境况变差,就无法使任何人的境况变好。数学优化将这种比较从个人福利推广到了任意一组目标。

在运筹学中,帕累托前沿用于描述成本、延迟、容量、可靠性和资源消耗之间的权衡。工程应用则利用它比较重量、强度、效率和制造成本等特性。

在机器学习中,前沿可以描述预测性能、模型大小、推理时间和计算开销之间的权衡。一系列正则化优化问题也可以用于探索拟合数据与控制模型复杂度之间的权衡。

在决策理论中,前沿将有效性分析与偏好获取区分开来。有效性分析识别出未被支配关系排除的选项,而偏好或其他决策规则则用于从中作出选择。

解读与局限

帕累托最优性取决于所选的目标和可行集。增加一个目标、更改一项约束,或遗漏某个相关后果,都可能改变前沿。如果考虑模型未纳入的因素,一个有效结果未必公平、可接受或值得追求。

对各个目标分别施加严格递增变换,不会改变支配关系,也不会改变哪些结果属于前沿。因此,对计量单位进行正比例换算,不会改变哪些结果是帕累托最优的。不过,如果不相应调整权重,这类换算可能改变加权和问题的解。

当相互冲突的目标很多时,大量候选方案之间可能互不支配。这会削弱前沿缩小选项范围的作用,并增加可视化和选择的难度。

目标值的不确定性或噪声会带来进一步的限制。根据点估计计算出的支配关系,在考虑不确定性后可能不再成立。比较期望结果、施加概率约束以及优化最坏情形下的结果,分别定义了不同的问题,也可能产生不同的前沿。

最后,前沿并不指定唯一的最佳折中方案。选择其中的某个点还需要额外信息,例如偏好、预算、期望水平,或明确的权衡评价规则。