Efficient Approximation Quality Computation for Sandwiching Algorithms for Convex Multicriteria Optimization

Ina Lammel (), Karl-Heinz Küfer () and Philipp Süss ()
Additional contact information
Ina Lammel: Fraunhofer Institute for Industrial Mathematics (ITWM)
Karl-Heinz Küfer: Fraunhofer Institute for Industrial Mathematics (ITWM)
Philipp Süss: Fraunhofer Institute for Industrial Mathematics (ITWM)

Journal of Optimization Theory and Applications, 2025, vol. 204, issue 3, No 6, 21 pages

Abstract: Abstract 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.

Keywords: Multicriteria optimization; Multi-objective optimization; Polyhedral approximation; Algorithms; Quality indicator; 90C29; 90C59; 90C25; 90–08 (search for similar items in EconPapers)
Date: 2025
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-024-02570-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:204:y:2025:i:3:d:10.1007_s10957-024-02570-8

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-024-02570-8

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().