pith. sign in

arxiv: 2604.09131 · v1 · submitted 2026-04-10 · 🧮 math.OC

Pareto Set Characterization in Constrained Multiobjective Optimization and the COBI Problem Generator *

Anne Auger (RANDOPT) , Dimo Brockhoff (RANDOPT) , Luka Oprav\v{s} (JSI Ljubljana) , Tea Tu\v{s}ar (JSI Ljubljana) This is my paper

Pith reviewed 2026-05-10 17:24 UTC · model grok-4.3

classification 🧮 math.OC
keywords constrained multiobjective optimizationPareto set characterizationbenchmark problem generatormultipeak functionsconvex quadraticderivative-free optimizationCOBI
0
0 comments X

The pith

Constrained multiobjective problems built from multipeak convex quadratics have formally characterizable Pareto sets.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper constructs a family of constrained multiobjective optimization test problems whose Pareto sets admit exact analytical description. Each objective is formed as the minimum over several convex quadratic functions with positive definite Hessians, which introduces multimodality, ill-conditioning and non-separability while retaining closed-form properties. Constraints are realized as sublevel sets of analogous multipeak functions, permitting disconnected feasible regions. The construction yields the COBI generator for scalable bi-objective instances together with a reference Python implementation intended for derivative-free algorithm benchmarking.

Core claim

The paper establishes that a class of analytically tractable constrained multiobjective problems can be obtained by defining objectives via the minimum over multiple convex-quadratic components with positive definite Hessians and constraints via sublevel sets of similar multipeak functions, thereby preserving sufficient structure for formal Pareto-set characterization even when multimodality and disconnected feasible regions appear.

What carries the argument

The multipeak formulation (minimum over several convex-quadratic components with positive definite Hessians) that defines each objective and each constraint function, thereby carrying the argument by maintaining analytical tractability under added multimodality.

Load-bearing premise

The minimum-over-quadratics operation and the sublevel-set constraints continue to permit closed-form Pareto-set characterization after non-convexity and possible disconnections are introduced.

What would settle it

A concrete COBI instance in which the analytically predicted Pareto set fails to coincide with the set recovered by exhaustive enumeration or high-precision numerical optimization would refute the claimed characterization.

Figures

Figures reproduced from arXiv: 2604.09131 by Anne Auger (RANDOPT), Dimo Brockhoff (RANDOPT), Luka Oprav\v{s} (JSI Ljubljana), Tea Tu\v{s}ar (JSI Ljubljana).

Figure 2
Figure 2. Figure 2: The leftmost three plots show the Pareto set in the search space for three problems with two 1 [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Illustration of Theorem 3.5. Left: Search space with unconstrained (gray) and constrained [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Four constrained problem types. Type I (first row): The constraints do not change the front. [PITH_FULL_IMAGE:figures/full_fig_p017_4.png] view at source ↗
read the original abstract

Benchmark problems play a central role in assessing the performance of numerical optimization algorithms. However, many existing constrained multiobjective optimization benchmark problems rely on overly restricted constructions or lack formal analysis of their optimal solution sets, limiting their relevance for systematic algorithm evaluation. In this work, we introduce a class of analytically tractable constrained multiobjective optimization problems whose Pareto sets can be formally characterized. The construction is based on convex-quadratic functions with positive definite Hessians, combined through multipeak formulations in which each objective is defined as the minimum over several convex-quadratic components. This approach preserves analytical structure while enabling multimodality (non-convexity), ill-conditioning and non-separability. The constraints are built as sublevel sets of multipeak functions giving rise to problems with potentially disconnected feasible regions. Building on these results, we propose COBI, a scalable generator of constrained bi-objective test problems designed for benchmarking derivative-free optimization algorithms. We provide a reference Python implementation that enables straightforward integration of COBI instances into benchmarking workflows.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a class of constrained multiobjective optimization problems constructed from convex quadratic functions with positive definite Hessians, combined via multipeak (min-over-components) formulations for the objectives and sublevel sets for the constraints. This is claimed to yield analytically tractable problems whose Pareto sets admit formal characterization, while supporting multimodality, ill-conditioning, non-separability, and disconnected feasible regions. The work proposes the COBI generator for scalable constrained bi-objective benchmark problems and supplies a reference Python implementation.

Significance. If the claimed formal Pareto-set characterizations hold in general, the contribution would be significant for benchmarking derivative-free multiobjective algorithms. Analytically tractable benchmarks with known Pareto sets are scarce once multimodality or disconnected feasible sets are introduced; a generator that systematically produces such instances with explicit characterizations would enable more rigorous algorithm evaluation than current ad-hoc or numerically solved test suites. The accompanying code directly supports reproducibility.

major comments (2)
  1. [Pareto Set Characterization (likely §3)] The central claim of formal Pareto-set characterization for multipeak objectives f_j(x) = min_i q_{j,i}(x) (q convex quadratic) rests on the min operator preserving closed-form tractability. At switching surfaces where the active quadratic component changes, the functions are only C^0. Standard first-order Pareto optimality conditions therefore do not apply uniformly. The manuscript must supply an explicit piecewise construction (domain partitioning plus union of local Pareto sets) and prove that the non-dominated union remains analytically describable without case-by-case numerical checks.
  2. [Constraint Construction and Feasible-Set Analysis] Constraints defined as sublevel sets of multipeak functions induce potentially disconnected feasible regions. The paper asserts that the Pareto-set characterization extends to these cases, yet provides no concrete argument showing how the non-dominated points are identified across disconnected components or at the boundaries of the sublevel sets. This step is load-bearing for the claim that the problems remain analytically tractable.
minor comments (2)
  1. [Introduction / Construction] The abstract states that the construction 'preserves analytical structure'; an early illustrative example (e.g., a two-peak bi-objective instance with explicit Pareto curve) would help readers verify the claimed tractability before the general theory.
  2. [Notation and Preliminaries] Notation for the multipeak functions and their active-set partitions should be introduced with a small table or diagram to avoid ambiguity when the characterization is later assembled from local convex subproblems.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the detailed and constructive report. The comments highlight important points regarding the rigor of the Pareto-set characterization under the multipeak construction. We address each major comment below and will incorporate the requested clarifications and proofs into a revised manuscript.

read point-by-point responses

  1. Referee: [Pareto Set Characterization (likely §3)] The central claim of formal Pareto-set characterization for multipeak objectives f_j(x) = min_i q_{j,i}(x) (q convex quadratic) rests on the min operator preserving closed-form tractability. At switching surfaces where the active quadratic component changes, the functions are only C^0. Standard first-order Pareto optimality conditions therefore do not apply uniformly. The manuscript must supply an explicit piecewise construction (domain partitioning plus union of local Pareto sets) and prove that the non-dominated union remains analytically describable without case-by-case numerical checks.

    Authors: We agree that the non-differentiability at switching surfaces requires careful handling. In the revised version we will add an explicit piecewise construction: the domain is partitioned into regions where a fixed set of quadratic components is active for each objective. Within each such region the problem reduces to a standard convex quadratic multiobjective problem whose Pareto set is given by the solution of a linear system derived from the stationarity conditions. We then prove that the global Pareto set is exactly the non-dominated subset of the union of these local Pareto sets. Because each local set is the image of an affine map (from the positive-definite quadratic structure) and dominance is checked by comparing the quadratic values, the overall characterization remains closed-form and does not rely on numerical verification for each instance. revision: yes

  2. Referee: [Constraint Construction and Feasible-Set Analysis] Constraints defined as sublevel sets of multipeak functions induce potentially disconnected feasible regions. The paper asserts that the Pareto-set characterization extends to these cases, yet provides no concrete argument showing how the non-dominated points are identified across disconnected components or at the boundaries of the sublevel sets. This step is load-bearing for the claim that the problems remain analytically tractable.

    Authors: We acknowledge that the current manuscript does not spell out the extension to disconnected feasible sets in sufficient detail. In the revision we will add a dedicated subsection that proceeds as follows: (i) each connected component of the feasible set is treated separately by restricting the piecewise construction to that component; (ii) the Pareto set of the whole problem is the non-dominated union across all such component-wise Pareto sets; (iii) boundary points are included by solving the corresponding equality-constrained quadratic problems on the active sublevel-set boundaries, which remain analytically solvable because the active constraints are quadratic. This argument preserves the closed-form character of the characterization. revision: yes

Circularity Check

0 steps flagged

No circularity: Pareto characterization follows directly from convex quadratic properties and sublevel sets

full rationale

The paper's derivation constructs objectives as min over convex-quadratic components (positive definite Hessians) and constraints as sublevel sets of similar multipeak functions. These are standard mathematical objects whose Pareto sets are characterized via well-known first-order conditions on the active pieces, without any parameter fitting, self-referential definitions, or load-bearing self-citations. The abstract and construction explicitly invoke only the preservation of analytical tractability from convexity and the min/sublevel operators; no step reduces the claimed formal characterization back to the inputs by construction. This is the common case of an honest, self-contained construction.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The construction depends on standard mathematical properties of convex quadratics and sublevel sets; no new entities are postulated and free parameters are limited to generator choices such as number of peaks and conditioning factors.

free parameters (2)
  • number of peaks per objective
    Chosen by the user to control multimodality; not fitted to data but part of problem definition.
  • Hessian conditioning parameters
    User-specified to introduce ill-conditioning while preserving positive-definiteness.
axioms (2)
  • domain assumption Each component is a convex quadratic with positive definite Hessian
    Invoked to guarantee convexity of individual pieces and overall analytical tractability.
  • domain assumption Objectives and constraints are defined via min and sublevel sets of these components
    Used to introduce multimodality and possible disconnection while retaining structure.

pith-pipeline@v0.9.0 · 5499 in / 1311 out tokens · 48744 ms · 2026-05-10T17:24:51.350552+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

46 extracted references · 46 canonical work pages

  1. [1]

    A rewriting system for convex optimization problems

    Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision , 5(1):42–60, 2018

    work page 2018

  2. [2]

    A dual active-set solver for embed- ded quadratic programming using recursive LDL T updates

    Daniel Arnstr¨ om, Alberto Bemporad, and Daniel Axehill. A dual active-set solver for embed- ded quadratic programming using recursive LDL T updates. IEEE Trans. on Automatic Control , 67(8):4362–4369, 2022

    work page 2022

  3. [3]

    A dynamic gradient approach to Pareto optimization with nonsmooth convex objective functions

    Hedy Attouch, Guillaume Garrigos, and Xavier Goudou. A dynamic gradient approach to Pareto optimization with nonsmooth convex objective functions. Journal of Mathematical Analysis and Applications, 422(1):741–771, 2015

    work page 2015

  4. [4]

    Cork, and Tea Tuˇ sar

    Anne Auger, Dimo Brockhoff, Jordan N. Cork, and Tea Tuˇ sar. On the Pareto set and front of multiobjective spherical functions with convex constraints. InGenetic and Evolutionary Computation Conference (GECCO 2025), pages 527–535, 2025

    work page 2025

  5. [5]

    pymoo: Multi-objective optimization in Python

    Julian Blank and Kalyanmoy Deb. pymoo: Multi-objective optimization in Python. IEEE Access, 8:89497–89509, 2020

    work page 2020

  6. [6]

    Convex Optimization

    Stephen Boyd and Lieven Vandenberghe. Convex Optimization . Cambridge University Press, The Edinburgh Building, Cambridge, CB2 8RU, UK, 2004

    work page 2004

  7. [7]

    Using well-understood single- objective functions in multiobjective black-box optimization test suites

    Dimo Brockhoff, Anne Auger, Nikolaus Hansen, and Tea Tuˇ sar. Using well-understood single- objective functions in multiobjective black-box optimization test suites. Evolutionary Computation, 30(2):165–193, 2022

    work page 2022

  8. [8]

    qpsolvers: Quadratic programming solvers in Python, 2025

    St´ ephane Caron, Daniel Arnstr¨ om, Suraj Bonagiri, Antoine Dechaume, Nikolai Flowers, Adam Heins, et al. qpsolvers: Quadratic programming solvers in Python, 2025

    work page 2025

  9. [9]

    Direct multisearch for multiobjective optimization

    Ana Lu´ ısa Cust´ odio, Jose Firmino Aguilar Madeira, A Ismael F Vaz, and Lu´ ıs Nunes Vicente. Direct multisearch for multiobjective optimization. SIAM Journal on Optimization , 21(3):1109–1140, 2011

    work page 2011

  10. [10]

    Meyarivan

    Kalyanmoy Deb, Samir Agrawal, Amrit Pratap, and T. Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. on Evolutionary Computation , 6(2):182–197, 2002

    work page 2002

  11. [11]

    Scalable test problems for evolutionary multiobjective optimization

    Kalyanmoy Deb, Lothar Thiele, Marco Laumanns, and Eckart Zitzler. Scalable test problems for evolutionary multiobjective optimization. In Evolutionary Multiobjective Optimization: Theoretical Advances and Applications, pages 105–145. Springer, 2005

    work page 2005

  12. [12]

    CVXPY: A Python-embedded modeling language for convex optimization

    Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research , 17(83):1–5, 2016

    work page 2016

  13. [13]

    Difficulty adjustable and scalable constrained multiobjective test problem toolkit.Evolutionary Computation, 28(3):339–378, 2020

    Zhun Fan, Wenji Li, Xinye Cai, Hui Li, Caimin Wei, Qingfu Zhang, Kalyanmoy Deb, and Erik Good- man. Difficulty adjustable and scalable constrained multiobjective test problem toolkit.Evolutionary Computation, 28(3):339–378, 2020

    work page 2020

  14. [14]

    A visualizable test problem generator for many-objective optimization

    Jonathan E Fieldsend, Tinkle Chugh, Richard Allmendinger, and Kaisa Miettinen. A visualizable test problem generator for many-objective optimization. IEEE Trans. on Evolutionary Computation, 26(1):1–11, 2021

    work page 2021

  15. [15]

    A general-purpose tunable landscape generator

    Marcus Gallagher and Bo Yuan. A general-purpose tunable landscape generator. IEEE Trans. on Evolutionary Computation, 10(5):590–603, 2006

    work page 2006

  16. [16]

    Classification-based linear surrogate modeling of constraints for AL-CMA-ES

    Oskar Girardin, Nikolaus Hansen, Dimo Brockhoff, and Anne Auger. Classification-based linear surrogate modeling of constraints for AL-CMA-ES. In Genetic and Evolutionary Computation Con- ference (GECCO 2025), pages 728–736, 2025

    work page 2025

  17. [17]

    Challenges of convex quadratic bi-objective benchmark problems

    Tobias Glasmachers. Challenges of convex quadratic bi-objective benchmark problems. In Genetic and Evolutionary Computation Conference (GECCO 2019) , pages 559–567, 2019

    work page 2019

  18. [18]

    The hypervolume indicator: Computa- tional problems and algorithms

    Andreia P Guerreiro, Carlos M Fonseca, and Lu´ ıs Paquete. The hypervolume indicator: Computa- tional problems and algorithms. ACM Computing Surveys (CSUR) , 54(6):1–42, 2021. Pareto Set Characterization and the COBI Problem Generator 21

    work page 2021

  19. [19]

    COCO: A platform for comparing continuous optimizers in a black-box setting.Optimization Methods and Software, 36(1):114–144, 2021

    Nikolaus Hansen, Anne Auger, Raymond Ros, Olaf Mersmann, Tea Tuˇ sar, and Dimo Brockhoff. COCO: A platform for comparing continuous optimizers in a black-box setting.Optimization Methods and Software, 36(1):114–144, 2021

    work page 2021

  20. [20]

    Springer, Berlin, Heidelberg, 2004

    Jean-Baptiste Hiriart-Urruty and Claude Lemar´ echal.Fundamentals of Convex Analysis . Springer, Berlin, Heidelberg, 2004

    work page 2004

  21. [21]

    A scalable multi-objective test problem toolkit

    Simon Huband, Luigi Barone, Lyndon While, and Phil Hingston. A scalable multi-objective test problem toolkit. In Evolutionary Multi-Criterion Optimization (EMO 2005) , pages 280–295, 2005

    work page 2005

  22. [22]

    Pareto fronts of many-objective degenerate test problems

    Hisao Ishibuchi, Hiroyuki Masuda, and Yusuke Nojima. Pareto fronts of many-objective degenerate test problems. IEEE Trans. on Evolutionary Computation , 20(5):807–813, 2015

    work page 2015

  23. [23]

    Modified distance calcula- tion in generational distance and inverted generational distance

    Hisao Ishibuchi, Hiroyuki Masuda, Yuki Tanigaki, and Yusuke Nojima. Modified distance calcula- tion in generational distance and inverted generational distance. In Evolutionary Multi-Criterion Optimization (EMO 2015) , pages 110–125. Springer, 2015

    work page 2015

  24. [24]

    Performance evaluation of multi-objective evolution- ary algorithms using artificial and real-world problems

    Hisao Ishibuchi, Yang Nan, and Lie Meng Pang. Performance evaluation of multi-objective evolution- ary algorithms using artificial and real-world problems. InEvolutionary Multi-Criterion Optimization (EMO 2023), pages 333–347, 2023

    work page 2023

  25. [25]

    Vector Optimization

    Johannes Jahn. Vector Optimization. Springer, Berlin, Heidelberg, 2009

    work page 2009

  26. [26]

    Improved dominance filtering for unions and Minkowski sums of Pareto sets

    Konstantinos Karathanasis, Spyros Kontogiannis, and Christos Zaroliagis. Improved dominance filtering for unions and Minkowski sums of Pareto sets. arXiv:2508.20689, 2025

    work page arXiv 2025

  27. [27]

    Multi-objective L-shaped test functions

    Angus Kenny, Tapabrata Ray, and Hemant Singh. Multi-objective L-shaped test functions. In Genetic and Evolutionary Comp. Conference (GECCO 2025) , pages 22–29. ACM, 2025

    work page 2025

  28. [28]

    Deutz, Heike Trautmann, and Michael T.M

    Pascal Kerschke, Hao Wang, Mike Preuss, Christian Grimme, Andr´ e H. Deutz, Heike Trautmann, and Michael T.M. Emmerich. Search dynamics on multimodal multiobjective problems.Evolutionary Computation, 27(4):577–609, 2019

    work page 2019

  29. [29]

    Suganthan, and Swagatam Das

    Abhishek Kumar, Guohua Wu, Mostafa Z Ali, Qizhang Luo, Rammohan Mallipeddi, Ponnuthurai N. Suganthan, and Swagatam Das. A benchmark-suite of real-world constrained multi-objective optimization problems and some baseline results. Swarm and Evolutionary Computation , 67:100961, 2021

    work page 2021

  30. [30]

    On finding the maxima of a set of vectors

    Hsiang-Tsung Kung, Fabrizio Luccio, and Franco P Preparata. On finding the maxima of a set of vectors. Journal of the ACM (JACM) , 22(4):469–476, 1975

    work page 1975

  31. [31]

    A survey on evolutionary constrained multiobjective optimization

    Jing Liang, Xuanxuan Ban, Kunjie Yu, Boyang Qu, Kangjia Qiao, Caitong Yue, Ke Chen, and Kay Chen Tan. A survey on evolutionary constrained multiobjective optimization. IEEE Trans. on Evolutionary Computation, 27(2):201–221, 2022

    work page 2022

  32. [32]

    Handling constrained multiobjective optimization problems with constraints in both the decision and objective spaces

    Zhi-Zhong Liu and Yong Wang. Handling constrained multiobjective optimization problems with constraints in both the decision and objective spaces. IEEE Trans. on Evolutionary Computation , 23(5):870–884, 2019

    work page 2019

  33. [33]

    Evolutionary constrained multiobjective optimization: Test suite construction and performance comparisons

    Zhongwei Ma and Yong Wang. Evolutionary constrained multiobjective optimization: Test suite construction and performance comparisons. IEEE Trans. on Evolutionary Computation , 23(6):972– 986, 2019

    work page 2019

  34. [34]

    Benchmarking derivative-free optimization algorithms

    Jorge J Mor´ e and Stefan M Wild. Benchmarking derivative-free optimization algorithms. SIAM Journal on Optimization , 20(1):172–191, 2009

    work page 2009

  35. [35]

    Operator splitting for a homogeneous embedding of the linear complemen- tarity problem

    Brendan O’Donoghue. Operator splitting for a homogeneous embedding of the linear complemen- tarity problem. SIAM Journal on Optimization , 31(3):1999–2023, 2021

    work page 1999

  36. [36]

    On the importance of information speed in structured popu- lations

    Mike Preuss and Christian Lasarczyk. On the importance of information speed in structured popu- lations. In Parallel Problem Solving from Nature , pages 91–100. Springer, 2004

    work page 2004

  37. [37]

    Yue Qi and Ralph E. Steuer. An analytical derivation of properly efficient sets in multi-objective portfolio selection. Annals of Operations Research, 346(2):1573–1595, 2025. Pareto Set Characterization and the COBI Problem Generator 22

    work page 2025

  38. [38]

    Approximation methods in multiobjective programming

    Stefan Ruzika and Margaret M Wiecek. Approximation methods in multiobjective programming. Journal of optimization theory and applications , 126(3):473–501, 2005

    work page 2005

  39. [39]

    Elsevier, 1985

    Yoshikazu Sawaragi, Hirotaka Nakayama, and Tanino Tetsuzo.Theory of multiobjective optimization, volume 176. Elsevier, 1985

    work page 1985

  40. [40]

    Peak-a-boo! Generating multi-objective multiple peaks benchmark problems with precise Pareto sets

    Lennart Sch¨ apermeier, Pascal Kerschke, Christian Grimme, and Heike Trautmann. Peak-a-boo! Generating multi-objective multiple peaks benchmark problems with precise Pareto sets. In Evolu- tionary Multi-Criterion Optimization (EMO 2023) , pages 291–304, 2023

    work page 2023

  41. [41]

    Decision space decomposition for multiobjective optimization

    Emma Soriano, Mishko Mitkovski, and Margaret M Wiecek. Decision space decomposition for multiobjective optimization. Journal of Optimization Theory and Applications , 208(3):103, 2026

    work page 2026

  42. [42]

    An easy-to-use real-world multi-objective optimization problem suite

    Ryoji Tanabe and Hisao Ishibuchi. An easy-to-use real-world multi-objective optimization problem suite. Applied Soft Computing , 89:106078, 2020

    work page 2020

  43. [43]

    A note on constrained multi-objective optimization benchmark problems

    Ryoji Tanabe and Akira Oyama. A note on constrained multi-objective optimization benchmark problems. In IEEE Congress on Evolutionary Comp. (CEC 2017) , pages 1127–1134, 2017

    work page 2017

  44. [44]

    On bi-objective convex-quadratic problems

    Cheikh Toure, Anne Auger, Dimo Brockhoff, and Nikolaus Hansen. On bi-objective convex-quadratic problems. In Evolutionary Multi-Criterion Optimization (EMO 2019) , pages 3–14, 2019

    work page 2019

  45. [45]

    The multiple peaks model 2

    Simon Wessing. The multiple peaks model 2. Algorithm Engineering Report TR15-2-001, Technische Universit¨ at Dortmund, Faculty of Computer Science, 2015

    work page 2015

  46. [46]

    Constrained multiobjective optimization: Test problem construction and performance evaluations

    Yuren Zhou, Yi Xiang, and Xiaoyu He. Constrained multiobjective optimization: Test problem construction and performance evaluations. IEEE Trans. on Evolutionary Computation , 25(1):172– 186, 2020

    work page 2020