Efficient Approximation Quality Computation for Sandwiching Algorithms for Convex Multicriteria Optimization

Computing the approximation quality is a crucial step in every iteration of sandwiching algorithms (also called Benson-type algorithms) used for the approximation of convex Pareto fronts, sets or functions. Two quality indicators often used in these algorithms are polyhedral gauge and epsilon indicator. In this article, we develop an algorithm to compute the polyhedral gauge and epsilon indicator approximation quality more efficiently. We derive criteria that assess whether the distance between a vertex of the outer approximation and the inner approximation needs to be recalculated. We interpret these criteria geometrically and compare them to a criterion developed by Dörfler et al. for a different quality indicator using convex optimization theory. For the bi-criteria case, we show that only two linear programs need to be solved in each iteration. We show that for more than two objectives, no constant bound on the number of linear programs to be checked can be derived. Numerical examples illustrate that incorporating the developed criteria into the sandwiching algorithm leads to a reduction in the approximation time of up to 94 % and that the approximation time increases more slowly with the number of iterations and the number of objective space dimensions.