Worst-Case Complexity Bounds of Directional Direct-Search Methods for Multiobjective Optimization
- PDF / 541,258 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 83 Downloads / 165 Views
Worst-Case Complexity Bounds of Directional Direct-Search Methods for Multiobjective Optimization Ana Luísa Custódio1 Elisa Riccietti3
· Youssef Diouane2
· Rohollah Garmanjani1
·
Received: 12 September 2019 / Accepted: 4 November 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Direct Multisearch is a well-established class of algorithms, suited for multiobjective derivative-free optimization. In this work, we analyze the worst-case complexity of this class of methods in its most general formulation for unconstrained optimization. Considering nonconvex smooth functions, we show that to drive a given criticality measure below a specific positive threshold, Direct Multisearch takes at most a number of iterations proportional to the square of the inverse of the threshold, raised to the number of components of the objective function. This number is also proportional to the size of the set of linked sequences between the first unsuccessful iteration and the iteration immediately before the one where the criticality condition is satisfied. We then focus on a particular instance of Direct Multisearch, which considers a more strict criterion for accepting new nondominated points. In this case, we can establish a better worst-case complexity bound, simply proportional to the square of the inverse of the threshold, for driving the same criticality measure below the considered threshold. Keywords Multiobjective unconstrained optimization · Derivative-free optimization methods · Directional direct-search · Worst-case complexity · Nonconvex smooth optimization Mathematics Subject Classification 90C29 · 90C30 · 90C56 · 90C60
1 Introduction Multiobjective optimization is a challenging domain in nonlinear optimization [1,2], when there are different conflicting objectives that need to be optimized. Difficulties
Communicated by Xinmin Yang.
B
Ana Luísa Custódio [email protected]
Extended author information available on the last page of the article
123
Journal of Optimization Theory and Applications
increase if derivatives are not available, neither can be numerically approximated due to the associated computational cost or to the presence of noise [3]. We are then in the domain of multiobjective derivative-free optimization, which often appears in problems where the objective function is evaluated through numerical simulation (for complementary information on single-objective derivative-free optimization methods, see [4–6]). We are interested in establishing worst-case complexity (WCC) bounds for directional direct-search, a class of derivative-free optimization methods, when used for solving unconstrained multiobjective optimization problems. Each iteration of this class of algorithms can be divided into a search step and a poll step, being the former optional. In fact, the convergence properties of these methods rely on the procedure implemented in the poll step [7]. The objective function is evaluated at a finite set of points, corresponding to directions with good geometrical
Data Loading...
