PaCcET: An Objective Space Transformation to Iteratively Convexify the Pareto Front


Abstract

In multi-objective problems, it is desirable to use a fast algorithm that gains coverage over large parts of the Pareto front. The simplest multi-objective method is a linear combination of objectives given to a single-objective optimizer. However, it is proven that this method cannot support solutions on the concave areas of the Pareto front: one of the points on the convex parts of the Pareto front or an extreme solution is always more desirable to an optimizer. This is a significant drawback of the linear combination. In this work we provide the Pareto Concavity Elimination Transformation (PaCcET), a novel, iterative objective space transformation that allows a linear combination (in this transformed objective space) to find solutions on concave areas of the Pareto front (in the original objective space). The transformation en- sures that an optimizer will always value a non-dominated solution over any dom- inated solution, and can be used by any single-objective optimizer. We demon- strate the efficacy of this method in two multi-objective benchmark problems with known concave Pareto fronts. Instead of the poor coverage created by a simple linear sum, PaCcET produces a superior spread across the Pareto front, including concave areas, similar to those discovered by more computationally-expensive multi-objective algorithms like SPEA2 and NSGA-II.