On the Extension of the DIRECT Algorithm to Multiple Objectives
- PDF / 1,989,998 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 17 Downloads / 214 Views
On the Extension of the DIRECT Algorithm to Multiple Objectives Alberto Lovison1
· Kaisa Miettinen2
Received: 1 March 2019 / Accepted: 7 August 2020 © The Author(s) 2020
Abstract Deterministic global optimization algorithms like Piyavskii–Shubert, direct, ego and many more, have a recognized standing, for problems with many local optima. Although many single objective optimization algorithms have been extended to multiple objectives, completely deterministic algorithms for nonlinear problems with guarantees of convergence to global Pareto optimality are still missing. For instance, deterministic algorithms usually make use of some form of scalarization, which may lead to incomplete representations of the Pareto optimal set. Thus, all global Pareto optima may not be obtained, especially in nonconvex cases. On the other hand, algorithms attempting to produce representations of the globally Pareto optimal set are usually based on heuristics. We analyze the concept of global convergence for multiobjective optimization algorithms and propose a convergence criterion based on the Hausdorff distance in the decision space. Under this light, we consider the well-known global optimization algorithm direct, analyze the available algorithms in the literature that extend direct to multiple objectives and discuss possible alternatives. In particular, we propose a novel definition for the notion of potential Pareto optimality extending the notion of potential optimality defined in direct. We also discuss its advantages and disadvantages when compared with algorithms existing in the literature. Keywords Global convergence · Multiobjective optimization · Multiple criteria optimization · DIRECT algorithm · Deterministic optimization algorithms Mathematics Subject Classification 90C29 · 90C26 · 90C30
This paper deepens and utilizes some ideas in the extended abstract Exact extension of the DIRECT algorithm to multiple objectives [26]. This research was partly funded by the Academy of Finland (Grant no. 287496).
B
Alberto Lovison [email protected] Kaisa Miettinen [email protected]
1
Department of Mathematics “Tullio Levi-Civita”, Università di Padova, Via Trieste 63, 35121 Padova, Italy
2
University of Jyvaskyla, Faculty of Information Technology, P.O. Box 35 (Agora), FI-40014 University of Jyvaskyla, Jyvaskyla, Finland
123
Journal of Global Optimization
1 Introduction We consider the class of exact (or deterministic) global optimization algorithms and their possible extensions to the multiobjective optimization case. Among their characteristics, these algorithms exhibit appreciable convergence speed when the dimension of the decision space is moderate, but their specific strength is global convergence, the proved ability of approximating the global optimum of a black-box function with an arbitrary accuracy as e.g., in [22,30,32,35,36,40,41]. Since many real-world problems have multiple conflicting objectives to be optimized simultaneously, we concentrate here on multiobjective optimization. Such problems have so
Data Loading...
