×

Revisiting norm optimization for multi-objective black-box problems: a finite-time analysis. (English) Zbl 1420.90063

Summary: The complexity of Pareto fronts imposes a great challenge on the convergence analysis of multi-objective optimization methods. While most theoretical convergence studies have addressed finite-set and/or discrete problems, others have provided probabilistic guarantees, assumed a total order on the solutions, or studied their asymptotic behaviour. In this paper, we revisit the Tchebycheff weighted method in a hierarchical bandits setting and provide a finite-time bound on the Pareto-compliant additive \(\epsilon \)-indicator. To the best of our knowledge, this paper is one of few that establish a link between weighted sum methods and quality indicators in finite time.

MSC:

90C29 Multi-objective and goal programming
90C56 Derivative-free methods and methods using generalized derivatives

Software:

SymPy; MSO
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Al-Dujaili, A., Suresh, S.: Dividing rectangles attack multi-objective optimization. In: IEEE Congress on Evolutionary Computation (CEC), 2016, pp. 1-8. IEEE, Vancouver, Canada (2016)
[2] Al-Dujaili, A., Suresh, S.: Multi-objective simultaneous optimistic optimization. ArXiv preprint arXiv:1612.08412 (2016) · Zbl 1436.90129
[3] Al-Dujaili, A., Suresh, S.: A naive multi-scale search algorithm for global optimization problems. Inf. Sci. 372, 294-312 (2016) · Zbl 1428.90178 · doi:10.1016/j.ins.2016.07.054
[4] Al-Dujaili, A., Suresh, S., Sundararajan, N.: MSO: a framework for bound-constrained black-box global optimization algorithms. J. Glob. Optim. https://doi.org/10.1007/s10898-016-0441-5 (2016) · Zbl 1394.90466
[5] Custódio, A.L., Madeira, J.A., Vaz, A.I.F., Vicente, L.N.: Direct multisearch for multiobjective optimization. SIAM J. Optim. 21(3), 1109-1140 (2011) · Zbl 1230.90167 · doi:10.1137/10079731X
[6] Fonseca, C.M., Fleming, P.J.: An overview of evolutionary algorithms in multiobjective optimization. Evol. Comput. 3(1), 1-16 (1995) · doi:10.1162/evco.1995.3.1.1
[7] Gimbutas, A.: Lipschitz optimization for multi-objective problems. VU Institute of Mathematics and Informatics, Lithuania (2016)
[8] Gimbutas, A., Zilinskas, A.: Generalization of Lipschitzian global optimization algorithms to the multi-objective case. In: International Workshop on Optimization and Learning: Challenges and Applications, At Alicante, Spain (2018) · Zbl 1402.90129
[9] Jones, D.; Floudas, C. (ed.); Pardalos, P. (ed.), Direct global optimization algorithm direct global optimization algorithm, 431-440 (2001), New York · doi:10.1007/0-306-48332-7_93
[10] Knowles, J., Thiele, L., Zitzler, E.: A tutorial on the performance assessment of stochastic multi-objective optimizers. TIK-Report 214, Computer Engineering and Networks Laboratory, ETH Zurich, Gloriastrasse 35, ETH-Zentrum, 8092 Zurich, Switzerland (2006)
[11] Loshchilov, I.: Surrogate-Assisted Evolutionary Algorithms. Theses, Université Paris Sud—Paris XI; Institut national de recherche en informatique et en automatique—INRIA (2013). https://tel.archives-ouvertes.fr/tel-00823882. Accessed 20 Jan 2018
[12] Messac, A., Mattson, C.A.: Normal constraint method with guarantee of even representation of complete pareto frontier. AIAA J. 42(10), 2101-2111 (2004) · doi:10.2514/1.8977
[13] Meurer, A., Smith, C.P., Paprocki, M., Čertík, O., Kirpichev, S.B., Rocklin, M., Kumar, A., Ivanov, S., Moore, J.K., Singh, S.: Sympy: symbolic computing in python. PeerJ Comput. Sci. 3, e103 (2017) · doi:10.7717/peerj-cs.103
[14] Miettinen, K.: Nonlinear multiobjective optimization. International series in operations research and management science, vol. 12. Kluwer Academic Publishers, Dordrecht (1999)
[15] Munos, R.; Cortes, C. (ed.); Lawrence, ND (ed.); Lee, DD (ed.); Sugiyama, M. (ed.); Garnett, R. (ed.), Optimistic optimization of a deterministic function without the knowledge of its smoothness, No. 24, 783-791 (2011), Red Hook
[16] Munos, R.: From bandits to Monte-Carlo Tree Search: the optimistic principle applied to optimization and planning. Found. Trends Mach. Learn. 7(1), 1-130 (2014). https://doi.org/10.1007/s00521-017-3057-x · Zbl 1296.91086 · doi:10.1007/s00521-017-3057-x
[17] Nabavi, S.R., Abbasi, M.: Black box modeling and multiobjective optimization of electrochemical ozone production process. Neural Comput. Appl. 1-12 (2017)
[18] Pareto, V.: Manual of political economy. Augustus M. Kelley Publishers, New York (1971)
[19] Roslund, J., Shir, O.M., Bäck, T., Rabitz, H.: Accelerated optimization and automated discovery with covariance matrix adaptation for experimental quantum control. Phys. Rev. A 80(4), 043-415 (2009) · doi:10.1103/PhysRevA.80.043415
[20] Soleimani-Damaneh, M., Zamani, M.: On compromise solutions in multiple objective programming. RAIRO Oper. Res. 52, 383-390 (2018) · Zbl 1401.90213 · doi:10.1051/ro/2017071
[21] Van Moffaert, K., Nowé, A.: Multi-objective reinforcement learning using sets of pareto dominating policies. J. Mach. Learn. Res. 15(1), 3483-3512 (2014) · Zbl 1312.90089
[22] Zadeh, L.: Optimality and non-scalar-valued performance criteria. IEEE Trans. Autom. Control 8(1), 59-60 (1963) · doi:10.1109/TAC.1963.1105511
[23] Zitzler, E., Thiele, L., Laumanns, M., Fonseca, C.M., Da Fonseca, V.G.: Performance assessment of multiobjective optimizers: an analysis and review. IEEE Trans. Evol. Comput. 7(2), 117-132 (2003) · doi:10.1109/TEVC.2003.810758
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.