帕累托前沿

帕累托前沿（Pareto front）是多目标优化中所有非支配可达目标向量的集合。它呈现不同目标之间不能同时改善的取舍，通常包含多个点；从中选一个方案还需要偏好、约束或其他决策规则。

五个方案的逐项比较

假设两个目标都要越小越好，教学候选的目标向量为 $A = (1, 5)$ 、 $B = (2, 3)$ 、 $C = (3, 2)$ 、 $D = (5, 1)$ 、 $E = (2, 4)$ 。B的第一目标与E相同，第二目标更低，所以B支配E。A、B、C、D彼此各有长短，没有谁能在不损失某项目标的情况下改进另一个，因此这四个向量构成该有限问题的前沿。

图中B到E的竖直方向说明，“至少一项目标严格改进”就足以支配，不要求每项都严格改进。横纵尺度分别代表两个目标，连线只帮助看取舍，并不表示候选之间存在可行连续混合。

决策集合、目标像与量词

设可行决策集为非空X，目标映射 $F = (f_{1}, \dots, f_{k}) : X \to ℝ^{k}$ ，各目标都最小化。称u支配v，当 $u_{i} \leq v_{i}$ 对所有i成立，且至少一个i严格小于。决策 $x^{*} \in X$ 帕累托有效，当且仅当 $∄ x \in X : [\forall i, f_{i} (x) \leq f_{i} (x^{*})] 且 [\exists i, f_{i} (x) < f_{i} (x^{*})] .$ 有效决策的集合记作P，前沿为 $F (P)$ ，属于目标空间。不同决策可以对应相同前沿向量，不能由前沿图倒推出决策唯一。^[1]

“弱帕累托有效”只排除所有目标都严格更小的其他点。主例E虽然被B支配，但没有其他候选同时严格改善它的两坐标，所以E是弱有效而非有效。用严格号替代上式所有非严格号，会改变前沿定义。

正权重保证存在的一条证明

取全部严格为正的权重 $w_{i} > 0$ ，若 $x^{*}$ 最小化 $\sum_{i} w_{i} f_{i} (x)$ ，它必有效。否则存在支配者x，各差值非正、至少一个为负，乘正权重相加便严格降低加权目标，与最小化矛盾。有限非空候选集总有加权最小点；更一般地，X紧、各目标连续时，标量目标达到最小值，也因此保证有效点存在。

这只说明加权解一定有效，不说明改变正权重必能得到全部前沿，非凸目标像可能有无法被支持直线接触的非支配点，详见加权和法。若X不紧、最小值不达到，前沿甚至可以为空：在 $X = (0, 1)$ 上令两目标都为x，任一点都被更小的正数支配。

变式、单位与有限枚举

新增方案 $H = (2, 2)$ 后，它支配B、C、E，新的前沿只剩A、D、H。主例没有这样的H时，不能根据连接B、C的线段想象出它；可行方案由模型给定。

对每个目标分别施加严格递增变换，会保持逐项大小关系，故保持支配和有效性。例如把成本从元改成分不改变前沿成员。但加权和、距离和“最接近理想点”的数值会受单位影响，需要另外说明尺度处理。前沿也不表达某一目标的概率、风险或因果效应，除非目标模型本来就定义了这些量。

下例输入目标向量列表，返回非支配点的索引，亦可检查弱有效点；复制输入不作改写。M个方案、k个目标的直接两两比较需 $O (M^{2} k)$ 时间，输入副本 $O (M k)$ ，结果至多M个。重复的相同向量互不严格支配，所以都会保留；若只需前沿的不同向量，可在返回后去重。

Python 3

def pareto_indices(points,weak=False):
    rows = [tuple(map(float,row)) for row in points]
    if not rows:
        return []
    k = len(rows[0])
    if k == 0 or any(len(row) != k for row in rows):
        raise ValueError("equal positive objective dimensions required")
    result = []
    for i,x in enumerate(rows):
        dominated = False
        for j,y in enumerate(rows):
            if i == j:
                continue
            test = all(a < b for a,b in zip(y,x)) if weak else all(a <= b for a,b in zip(y,x)) and any(a < b for a,b in zip(y,x))
            if test:
                dominated = True
                break
        if not dominated:
            result.append(i)
    return result

points = [(1,5),(2,3),(3,2),(5,1),(2,4)]
print("front",pareto_indices(points))
print("weak",pareto_indices(points,weak=True))
print("variant",pareto_indices(points+[(2,2)]))
assert pareto_indices([(1,1),(1,1)]) == [0,1]

参考文献

↑ Boyd and Vandenberghe, Convex Optimization，§4.7.3—4.7.4。

[1] Boyd and Vandenberghe, Convex Optimization，§4.7.3—4.7.4。

[1]