Multi-objective simultaneous optimistic optimization
From MaRDI portal
Publication:781163
DOI10.1016/J.INS.2017.09.066zbMATH Open1436.90129arXiv1612.08412OpenAlexW2963495607MaRDI QIDQ781163FDOQ781163
Authors: D. Kharzeev 
Publication date: 16 July 2020
Published in: Information Sciences (Search for Journal in Brave)
Abstract: Optimistic methods have been applied with success to single-objective optimization. Here, we attempt to bridge the gap between optimistic methods and multi-objective optimization. In particular, this paper is concerned with solving black-box multi-objective problems given a finite number of function evaluations and proposes an optimistic approach, which we refer to as the Multi-Objective Simultaneous Optimistic Optimization (MO-SOO). Popularized by multi-armed bandits, MO-SOO follows the optimism in the face of uncertainty principle to recognize Pareto optimal solutions, by combining several multi-armed bandits in a hierarchical structure over the feasible decision space of a multi-objective problem. Based on three assumptions about the objective functions smoothness and hierarchical partitioning, the algorithm finite-time and asymptotic convergence behaviors are analyzed. The finite-time analysis establishes an upper bound on the Pareto-compliant unary additive epsilon indicator characterized by the objectives smoothness as well as the structure of the Pareto front with respect to its extrema. On the other hand, the asymptotic analysis indicates the consistency property of MO-SOO. Moreover, we validate the theoretical provable performance of the algorithm on a set of synthetic problems. Finally, three-hundred bi-objective benchmark problems from the literature are used to substantiate the performance of the optimistic approach and compare it with three state-of-the-art stochastic algorithms, namely MOEA/D, MO-CMA-ES, and SMS-EMOA in terms of two Pareto-compliant quality indicators. Besides sound theoretical properties, MO-SOO shows a performance on a par with the top performing stochastic algorithm, viz. SMS-EMOA.
Full work available at URL: https://arxiv.org/abs/1612.08412
Recommendations
- From bandits to Monte-Carlo tree search: the optimistic principle applied to optimization and planning
- Revisiting norm optimization for multi-objective black-box problems: a finite-time analysis
- Output Space Entropy Search Framework for Multi-Objective Bayesian Optimization
- A statistical model-based algorithm for `black-box' multi-objective optimisation
- A Bayesian approach to constrained single- and multi-objective optimization
asymptotic analysismulti-objective optimizationmulti-armed banditsfinite-time analysisoptimistic methodssimultaneous optimistic optimization
Multi-objective and goal programming (90C29) Derivative-free methods and methods using generalized derivatives (90C56)
Cites Work
- SMS-EMOA: multiobjective selection based on dominated hypervolume
- Multiple objective decision making - methods and applications. A state- of-the-art survey. In collaboration with Sudhakar R. Paidy and Kwangsun Yoon
- Finite-time analysis of the multiarmed bandit problem
- Multi-objective optimization using evolutionary algorithms
- Global convergence of general derivative-free trust-region algorithms to first- and second-order critical points
- Title not available (Why is that?)
- 10.1162/153244303321897663
- Direct Multisearch for Multiobjective Optimization
- On the convergence of multiobjective evolutionary algorithms
- From bandits to Monte-Carlo tree search: the optimistic principle applied to optimization and planning
- A naive multi-scale search algorithm for global optimization problems
- Foundations of Genetic Algorithms
Cited In (9)
- Multi-objective ordinal optimization for simulation optimization problems
- Efficient multiobjective optimization employing Gaussian processes, spectral sampling and a genetic algorithm
- Multiobjective optimization: when objectives exhibit non-uniform latencies
- Multi-armed linear bandits with latent biases
- Bi-objective memetic GP with dispersion-keeping Pareto evaluation for real-world regression
- Multi-objective retrospective optimization using stochastic zigzag search
- Revisiting norm optimization for multi-objective black-box problems: a finite-time analysis
- Pareto-aware strategies for faster convergence in multi-objective multi-scale search optimization
- From bandits to Monte-Carlo tree search: the optimistic principle applied to optimization and planning
Uses Software
This page was built for publication: Multi-objective simultaneous optimistic optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q781163)
