The Kalai-Smorodinsky solution for many-objective Bayesian optimization. (English) Zbl 07306856

Summary: An ongoing aim of research in multiobjective Bayesian optimization is to extend its applicability to a large number of objectives. While coping with a limited budget of evaluations, recovering the set of optimal compromise solutions generally requires numerous observations and is less interpretable since this set tends to grow larger with the number of objectives. We thus propose to focus on a specific solution originating from game theory, the Kalai-Smorodinsky solution, which possesses attractive properties. In particular, it ensures equal marginal gains over all objectives. We further make it insensitive to a monotonic transformation of the objectives by considering the objectives in the copula space. A novel tailored algorithm is proposed to search for the solution, in the form of a Bayesian optimization algorithm: sequential sampling decisions are made based on acquisition functions that derive from an instrumental Gaussian process prior. Our approach is tested on four problems with respectively four, six, eight, and nine objectives. The method is available in the R package GPGame available on CRAN at https://cran.r-project.org/package=GPGame.


68T05 Learning and adaptive systems in artificial intelligence
Full Text: arXiv Link


[1] Majid Abdolshah, Alistair Shilton, Santu Rana, Sunil Gupta, and Svetha Venkatesh. Multiobjective Bayesian optimisation with preferences over objectives. InAdvances in Neural
[2] Badr Abou El Majd, Jean-Antoine Desideri, and Abderrahmane Habbal. Optimisation de forme fluide-structure par un jeu de Nash.Revue Africaine de la Recherche en Informatique
[3] Joseph J. Allaire and François Chollet.keras: R Interface to ’Keras’, 2018. URLhttps: //keras.rstudio.com. R package version 2.1.4.
[4] Md Asafuddoula, Tapabrata Ray, and Ruhul Sarker. A decomposition-based evolutionary algorithm for many objective optimization.IEEE Transactions on Evolutionary Computation, 19(3):445-460, 2015. · Zbl 1338.90468
[5] Johannes Bader and Eckart Zitzler. Hype: An algorithm for fast hypervolume-based manyobjective optimization.Evolutionary Computation, 19(1):45-76, 2011.
[6] Slim Bechikh, Lamjed Ben Said, and Khaled Ghedira. Estimating nadir point in multiobjective optimization using mobile reference points. InIEEE Congress on Evolutionary
[7] Julien Bect, David Ginsbourger, Ling Li, Victor Picheny, and Emmanuel Vazquez. Sequential design of computer experiments for the estimation of a probability of failure.Statistics · Zbl 1252.62081
[8] Julien Bect, François Bachoc, David Ginsbourger, et al. A supermartingale approach to gaussian process based sequential design of experiments.Bernoulli, 25(4A):2883-2919, 2019. · Zbl 1428.62369
[9] James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization.The Journal of Machine Learning Research, 13:281-305, 2012. · Zbl 1283.68282
[10] James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyperparameter optimization. InAdvances in Neural Information Processing Systems, pages 2546-2554, 2011.
[11] Mickaël Binois and Victor Picheny. GPareto: An R package for Gaussian-process-based multi-objective optimization and analysis.Journal of Statistical Software, 89(1):1-30, 2019.
[12] Mickaël Binois, Didier Rullière, and Olivier Roustant. On the estimation of Pareto fronts from the point of view of copula theory.Information Sciences, 324:270 - 285, 2015. · Zbl 1390.62043
[13] Mickaël Binois, Robert B Gramacy, and Mike Ludkovski. Practical heteroscedastic Gaussian process modeling for large simulation experiments.Journal of Computational and Graphical Statistics, 27(4):808-821, 2018.
[14] Mickaël Binois, Jiangeng Huang, Robert B Gramacy, and Mike Ludkovski. Replication or exploration? Sequential design for stochastic simulation experiments.Technometrics, 61
[15] Mathieu Bourgais, Patrick Taillandier, and Laurent Vercouter. Enhancing the behavior of agents in social simulations with emotions and social relations. In18th workshop on
[16] Irem Bozbay, Franz Dietrich, and Hans Peters. Bargaining with endogenous disagreement: The extended Kalai-Smorodinsky solution.Games and Economic Behavior, 74(1):407-417, 2012. · Zbl 1279.91078
[17] Abraham Charnes and William Wager Cooper. Goal programming and multiple objective optimizations: Part 1.European journal of operational research, 1(1):39-54, 1977. · Zbl 0375.90079
[18] Ran Cheng, Miqing Li, Ye Tian, Xingyi Zhang, Shengxiang Yang, Yaochu Jin, and Xin Yao. A benchmark test suite for evolutionary many-objective optimization.Complex &
[19] Clément Chevalier, Julien Bect, David Ginsbourger, Emmanuel Vazquez, Victor Picheny, and Yann Richet. Fast parallel kriging-based stepwise uncertainty reduction with application to the identification of an excursion set.Technometrics, 56(4):455-465, 2014.
[20] Clément Chevalier, Xavier Emery, and David Ginsbourger. Fast update of conditional simulation ensembles.Mathematical Geosciences, 47(7):771-789, 2015. · Zbl 1323.86020
[21] François Chollet et al. Keras.https://github.com/fchollet/keras, 2015.
[22] Tinkle Chugh, Karthik Sindhya, Jussi Hakanen, and Kaisa Miettinen. A survey on handling computationally expensive multiobjective optimization problems with evolutionary algorithms.Soft Computing, pages 1-30, 2017.
[23] Tinkle Chugh, Yaochu Jin, Kaisa Miettinen, Jussi Hakanen, and Karthik Sindhya. A surrogate-assisted reference vector guided evolutionary algorithm for computationally expensive many-objective optimization.IEEE Transactions on Evolutionary Computation, 22(1):129-143, 2018.
[24] John P Conley and Simon Wilkie. The bargaining problem without convexity: Extending the egalitarian and Kalai-Smorodinsky solutions.Economics Letters, 36(4):365-369, 1991. · Zbl 0758.90089
[25] Ivo Couckuyt, Dirk Deschrijver, and Tom Dhaene. Fast calculation of multiobjective probability of improvement and expected improvement criteria for Pareto optimization. · Zbl 1303.90093
[26] Indraneel Das and John E Dennis. Normal-boundary intersection: A new method for generating the Pareto surface in nonlinear multicriteria optimization problems.SIAM · Zbl 0911.90287
[27] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan. A fast and elitist multiobjective genetic algorithm: NSGA-II.IEEE transactions on Evolutionary
[28] Kalyanmoy Deb, Shamik Chaudhuri, and Kaisa Miettinen. Towards estimating nadir objective vector using evolutionary approaches. InProceedings of the 8th annual conference on · Zbl 1184.90151
[29] Thomas Desautels, Andreas Krause, and Joel W Burdick. Parallelizing explorationexploitation tradeoffs in gaussian process bandit optimization.The Journal of Machine · Zbl 1312.62036
[30] Jean-Antoine Désidéri, Régis Duvigneau, and Abderrahmane Habbal.Computational Intelligence in Aerospace Sciences, V. M. Becerra and M. Vassile Eds., volume 244 ofProgress in Astronautics and Aeronautics, chapter Multi-Objective Design Optimization Using Nash · Zbl 1416.35201
[31] Peter Diggle and Paulo Justiniano Ribeiro.Model-Based Geostatistics. Springer, 2007. · Zbl 1132.86002
[32] Laurence Charles Ward Dixon and Giorgio P Szegö.Towards global optimisation, volume 2. North-Holland Amsterdam, 1978.
[33] Valerii Vadimovich Fedorov.Theory of Optimal Experiments. Elsevier, 1972.
[34] David Gaudrie, Rodolphe Le Riche, Victor Picheny, Benoit Enaux, and Vincent Herbert. Targeting solutions in Bayesian multi-objective optimization: sequential and batch versions. · Zbl 1432.90138
[35] Debasish Ghose and UR Prasad. Solution concepts in two-person multicriteria games.Journal of Optimization Theory and Applications, 63(2):167-189, 1989. · Zbl 0662.90093
[36] Jussi Hakanen and Joshua D Knowles. On using decision maker preferences with ParEGO. InInternational Conference on Evolutionary Multi-Criterion Optimization, pages 282-297. Springer, 2017.
[37] Philipp Hennig and Christian J Schuler. Entropy search for information-efficient global optimization.The Journal of Machine Learning Research, 13:1809-1837, 2012. · Zbl 1432.65073
[38] Daniel Hernández-Lobato, Jose Hernandez-Lobato, Amar Shah, and Ryan Adams. Predictive entropy search for multi-objective Bayesian optimization. InInternational Conference on
[39] José Miguel Hernández-Lobato, Michael A Gelbart, Ryan P Adams, Matthew W Hoffman, and Zoubin Ghahramani. A general framework for constrained Bayesian optimization using information-based search.Journal of Machine Learning Research, 17(160):1-53, 2016b. · Zbl 1391.90641
[40] Jens Leth Hougaard and Mich Tvede. Nonconvex n-person bargaining: efficient maxmin solutions.Economic Theory, 21(1):81-95, 2003. · Zbl 1032.91059
[41] Hisao Ishibuchi, Noritaka Tsukamoto, and Yusuke Nojima. Evolutionary many-objective optimization: A short review. InIEEE Congress on Evolutionary Computation, 2008. · Zbl 1136.90466
[42] Hisao Ishibuchi, Yu Setoguchi, Hiroyuki Masuda, and Yusuke Nojima. Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes.
[43] Hamed Jalali, Inneke Van Nieuwenhuyse, and Victor Picheny. Comparison of kriging-based algorithms for simulation optimization with heterogeneous noise.European Journal of · Zbl 1403.90553
[44] Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions.Journal of Global Optimization, 13(4):455-492, 1998. · Zbl 0917.90270
[45] Ulrich Junker. Preference-based search and multi-criteria optimization.Annals of Operations Research, 130(1-4):75-115, 2004. · Zbl 1156.90381
[46] Ehud Kalai and Meir Smorodinsky. Other solutions to Nash’s bargaining problem.Econometrica, 43:513-518, 1975. · Zbl 0308.90053
[47] Joshua Knowles. ParEGO: a hybrid algorithm with on-line landscape approximation for expensive multiobjective optimization problems.IEEE Transactions on Evolutionary
[48] Saku Kukkonen and Jouni Lampinen. Ranking-dominance and many-objective optimization. InIEEE Congress on Evolutionary Computation, 2007. CEC 2007., pages 3983-3990. IEEE, 2007.
[49] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition.Proceedings of the IEEE, 86(11):2278-2324, 1998.
[50] Miqing Li, Liangli Zhen, and Xin Yao. How to read many-objective solution sets in parallel coordinates [educational forum].IEEE Computational Intelligence Magazine, 12(4):88-100, 2017.
[51] Michael D McKay, Richard J Beckman, and William J Conover. Comparison of three methods for selecting values of input variables in the analysis of output from a computer code.Technometrics, 21(2):239-245, 1979. · Zbl 0415.62011
[52] Kaisa Miettinen.Nonlinear multiobjective optimization, volume 12. Springer Science & Business Media, 2012. · Zbl 1282.90166
[53] Roger B Nelsen.An Introduction to Copulas. Springer, 2006. · Zbl 1152.62030
[54] Harald Niederreiter. Low-discrepancy and low-dispersion sequences.Journal of Number Theory, 30(1):51-70, 1988. · Zbl 0651.10034
[55] Jeremy Oakley. Estimating percentiles of uncertain computer code outputs.Journal of the Royal Statistical Society: Series C (Applied Statistics), 53(1):83-93, 2004. · Zbl 1111.62395
[56] Marek Omelka, Irène Gijbels, and Noël Veraverbeke. Improved kernel estimation of copulas: weak convergence and goodness-of-fit testing.The Annals of Statistics, 37(5B):3023-3058, 2009. · Zbl 1360.62160
[57] Biswajit Paria, Kirthevasan Kandasamy, and Barnabás Póczos. A flexible framework for multi-objective Bayesian optimization using random scalarizations. InUAI, 2019.
[58] James Parr.Improvement criteria for constraint handling and multiobjective optimization. PhD thesis, University of Southampton, 2013.
[59] Victor Picheny. Multiobjective optimization using Gaussian process emulators via stepwise uncertainty reduction.Statistics and Computing, pages 1-16, 2013. · Zbl 1331.90102
[60] Victor Picheny and Mickaël Binois.GPGame: Solving Complex Game Problems using Gaussian Processes, 2018. URLhttp://CRAN.R-project.org/package=GPGame. R package version 1.1.0.
[61] Victor Picheny, Tobias Wagner, and David Ginsbourger. A benchmark of kriging-based infill criteria for noisy optimization.Structural and Multidisciplinary Optimization, 48(3): 607-626, 2013.
[62] Victor Picheny, Mickaël Binois, and Abderrahmane Habbal. A Bayesian optimization approach to find Nash equilibria.Journal of Global Optimization, 73(1):171-192, 2019. · Zbl 1410.91030
[63] Wolfgang Ponweiser, Tobias Wagner, Dirk Biermann, and Markus Vincze. Multiobjective optimization on a limited budget of evaluations using model-assisted s-metric selection. InInternational Conference on Parallel Problem Solving from Nature, pages 784-794. Springer, 2008.
[64] R Core Team.R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria, 2018. URLhttps://www.R-project.org/.
[65] Carl E. Rasmussen and Christopher Williams.Gaussian Processes for Machine Learning. MIT Press, 2006. URLhttp://www.gaussianprocess.org/gpml/. · Zbl 1177.68165
[66] Olivier Roustant, Esperan Padonou, Yves Deville, Aloïs Clément, Guillaume Perrin, Jean Giorla, and Henry Wynn. Group kernels for Gaussian process metamodels with categorical inputs.arXiv preprint arXiv:1802.02368, 2018. · Zbl 1443.60040
[67] Daniel Russo and Benjamin Van Roy. Learning to optimize via information-directed sampling. InAdvances in Neural Information Processing Systems, pages 1583-1591, 2014. · Zbl 1458.90497
[68] Matthias Schonlau, William J Welch, and Donald R Jones. Global versus local search in constrained optimization of computer models.Lecture Notes-Monograph Series, pages 11-25, 1998.
[69] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando de Freitas. Taking the human out of the loop: A review of Bayesian optimization.Proceedings of the IEEE, 104(1):148-175, 2016.
[70] Hemant Kumar Singh, Amitay Isaacs, and Tapabrata Ray. A Pareto corner search evolutionary algorithm and dimensionality reduction in many-objective optimization problems.
[71] Sean C Smithson, Guang Yang, Warren J Gross, and Brett H Meyer. Neural networks designing neural networks: Multi-objective hyper-parameter optimization. In2016 IEEE/ACM
[72] Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Informationtheoretic regret bounds for Gaussian process optimization in the bandit setting.Information · Zbl 1365.94131
[73] Joshua D. Svenson.Computer Experiments: Multiobjective Optimization and Sensitivity Analysis. PhD thesis, The Ohio State University, 2011.
[74] Mohammad Tabatabaei, Markus Hartikainen, Karthik Sindhya, Jussi Hakanen, and Kaisa Miettinen. An interactive surrogate-based method for computationally expensive multiobjective optimisation.Journal of the Operational Research Society, 70(6):898-914, 2019.
[75] Franck Taillandier, Alice Micolier, and Patrick Taillandier. Li-bim (version 1.0.0), 2017.
[76] Patrick Taillandier, Benoit Gaudou, Arnaud Grignard, Quang-Nghi Huynh, Nicolas Marilleau, Philippe Caillou, Damien Philippon, and Alexis Drogoul. Building, composing and experimenting complex spatial models with the gama platform.GeoInformatica, pages 1-24, 2018.
[77] Lothar Thiele, Kaisa Miettinen, Pekka J Korhonen, and Julian Molina. A preference-based evolutionary algorithm for multi-objective optimization.Evolutionary computation, 17(3): 411-436, 2009.
[78] Julien Villemonteix, Emmanuel Vazquez, and Eric Walter. An informational approach to the global optimization of expensive-to-evaluate functions.Journal of Global Optimization, 44 · Zbl 1180.90253
[79] Tobias Wagner, Michael Emmerich, André Deutz, and Wolfgang Ponweiser. On expectedimprovement criteria for model-based multi-objective optimization. InInternational
[80] Eric Walter and Luc Pronzato.Identification of Parametric Models from Experimental Data. Springer Verlag, 1997. · Zbl 0864.93014
[81] Andrzej P Wierzbicki. The use of reference objectives in multiobjective optimizationtheoretical implications and practical experience. 1979.
[82] Andrzej P Wierzbicki. The use of reference objectives in multiobjective optimization. In Multiple criteria decision making theory and application, pages 468-486. Springer, 1980. · Zbl 0435.90098
[83] Andrew G Wilson and Zoubin Ghahramani. Copula processes. InAdvances in Neural Information Processing Systems, pages 2460-2468, 2010.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.