Journal of Optimization Theory and Applications Management Science and Operations Research

Worst-Case Complexity Analysis of Derivative-Free Methods for Multi-objective Optimization

Giampaolo Liuzzi, Stefano Lucidi
Springer Nature · 2026-11-01 · DOI 10.1007/s10957-026-03121-z

Abstract

Abstract In this work, we are concerned with the worst case complexity analysis of a posteriori methods for unconstrained multi-objective optimization problems where objective function values can only be obtained by querying a black-box. We present two main algorithms, namely and , which are based on a linesearch expansion technique. In particular, requires a complete exploration of the points in the current set of non-dominated solutions, whereas only requires the exploration around a single point in the set of non-dominated solutions. For these algorithms, we derive worst case iteration and evaluation complexity results. In particular, the complexity results for align with those recently proved in [11] for a directional multisearch method. Furthermore, by exploiting an expansion technique of the step, we are also able to give further complexity results concerning the number of iterations with a measure of stationarity above a prefixed tolerance.

Read at publisher →