Dichotomic Search for Complex Multiobjective Optimization Problems

Authors:

Abstract
Dichotomic search is a classical scalarization-based method for computing extreme supported nondominated points in bi-objective optimization. Its extension to more than two objectives and to continuous, numerically difficult problems is challenging due to the loss of a natural ordering of extreme supported points, the complexity of convex-hull updates, and the instability of weighted-sum solves.In this paper, we study dichotomic-search-based methods for complex multiobjective optimization problems. We review the bi-objective setting and higher-dimensional boundary dichotomic search, and propose a Continuous Boundary Dichotomic Search (CBDS) framework for continuous problems with approximate scalarization solves. The method combines boundary-first exploration, adaptive refinement of bi-objective subproblems, validity checks for dominated or inconsistent outcomes, and focused search on relevant regions of the weight set. We also introduce a Pareto knee score to identify extreme supported points with favorable trade-offs.Numerical experiments on multiobjective combinatorial problems, a radiotherapy beam intensity optimization problem, and a physics-informed neural network for a pendulum system illustrate the proposed framework. The results show that dichotomic-search-based methods can reliably identify extreme supported solutions with high Pareto knee scores with relatively few scalarization solves in low-dimensional settings, while also revealing the geometrical and computational limitations caused by the growth of convex-hull complexity in higher dimensions.