Abstract
This paper proposes a Sequential Model Based Optimization framework for solving optimization problems characterized by a black-box, multi-extremal, expensive and partially defined objective function, under unknown constraints. This is a typical setting for simulation-optimization problems, where the objective function cannot be computed for some configurations of the decision/control variables due to the violation of some (unknown) constraint. The framework is organized in two consecutive phases, the first uses a Support Vector Machine classifier to approximate the boundary of the unknown feasible region within the search space, the second uses Bayesian Optimization to find a globally optimal (feasible) solution. A relevant difference with traditional Bayesian Optimization is that the optimization process is performed on the estimated feasibility region, only, instead of the entire search space. Some results on three 2D test functions and a real case study for the Pump Scheduling Optimization in Water Distribution Networks are reported. The proposed framework proved to be more effective and efficient than Bayesian Optimization approaches using a penalty for function evaluations outside the feasible region.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Frazier, P.I.: Bayesian Optimization. In: Recent Advances in Optimization and Modeling of Contemporary Problems - INFORMS, pp. 255–278 (2018)
Jones, D.R., Schonlau, M., Welch, W.J.: Efficient global optimization of expensive black-box functions. J. Global Optim. 13(4), 455–492 (1998)
Shahriari, B., Swersky, K., Wang, Z., Adams, R.P., De Freitas, N.: Taking the human out of the loop: A review of Bayesian Optimization. Proc. IEEE 104(1), 148–175 (2016)
Žilinskas, A., Žilinskas, J.: Global optimization based on a statistical model and simplicial partitioning. Comput. Math Appl. 44(7), 957–967 (2002)
Sergeyev, Y.D., Kvasov, D.E., Mukhametzhanov, M.S.: On the efficiency of nature-inspired metaheuristics in expensive global optimization with limited budget. Sci. Rep.-UK 8(1), 453 (2018)
Sergeyev, Y.D., Strongin, R.G., Lera, D.: Introduction to Global Optimization Exploiting Space-Filling Curves. Springer, New York (2013). https://doi.org/10.1007/978-1-4614-8042-6
Sergeyev, Y.D., Kvasov, D.E.: Deterministic Global Optimization: An Introduction to the Diagonal Approach. Springer, Berlin (2017). https://doi.org/10.1007/978-1-4939-7199-2
Zhigljavsky, A., Zilinskas, A.: Stochastic Global Optimization, vol. 9. Springer, Berlin (2008). https://doi.org/10.1007/978-0-387-74740-8
Archetti, F., Betrò, B.: A priori analysis of deterministic strategies. In: Towards Global Optimization 2 (1978)
Archetti, F., Betrò, B.: Stochastic models and optimization. Bollettinodell’Unione Matematica Italiana 5(17-A), 295–301 (1980)
Archetti, F., Betrò, B.: A probabilistic algorithm for global optimization. Calcolo 16, 335–343 (1979)
Thornton, C., Hutter, F., Hoos, H.H., Leyton-Brown, K.: Auto-WEKA: combined selection and hyperparameter optimization of classification algorithms. In: Proceedings of ACM-SIGKDD, pp. 847–855 (2013)
Feurer, M., Klein, A., Eggensperger, K., Springenberg, J., Blum, M., Hutter, F.: Efficient and robust automated machine learning. In: Advances in Neural Information, pp. 2962–2970 (2015)
Candelieri, A., Archetti, F.: Global optimization in machine learning: the design of a predictive analytics application. Soft Comput. 1–9 (2018)
Galuzzi, B.G., Perego, R., Candelieri, A., Archetti, F.: Bayesian optimization for full waveform inversion. In: Daniele, P., Scrimali, L. (eds.) New Trends in Emerging Complex Real Life Problems. ASS, vol. 1, pp. 257–264. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00473-6_28
Sergeyev, Y.D., Pugliese, P., Famularo, D.: Index information algorithm with local tuning for solving multidimensional global optimization problems with multiextremal constraints. Math. Program. 96(3), 489–512 (2003)
Paulavičius, R., Žilinskas, J.: Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints. Optim. Lett. 10(2), 237–246 (2016)
Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Springer, Boston (2013). https://doi.org/10.1007/978-1-4615-4677-1
Donskoi, V.I.: Partially defined optimization problems: an approach to a solution that is based on pattern recognition theory. J. Sov. Mathematics 65(3), 1664–1668 (1993)
Rudenko, L.I.: Objective functional approximation in a partially defined optimization problem. J. Math. Sci. 72(5), 3359–3363 (1994)
Sergeyev, Y.D., Kvasov, D.E., Khalaf, F.M.: A one-dimensional local tuning algorithm for solving GO problems with partially defined constraints. Optim. Lett. 1(1), 85–99 (2007)
Hernández-Lobato, J.M., Gelbart, M.A., Adams, R.P., Hoffman, M.W., Ghahramani, Z.: A general framework for constrained Bayesian optimization using information-based search. J. Mach. Learn. Res. 17(1), 5549–5601 (2016)
Gorji Daronkolaei, A., Hajian, A., Custis, T.: Constrained bayesian optimization for problems with piece-wise smooth constraints. In: Bagheri, E., Cheung, J.C.K. (eds.) Canadian AI 2018. LNCS (LNAI), vol. 10832, pp. 218–223. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-89656-4_18
Picheny, V., Gramacy, R.B., Wild, S., Le Digabel, S.: Bayesian optimization under mixed constraints with a slack-variable augmented Lagrangian. In Advances in Neural Information Processing Systems, pp. 1435–1443 (2016)
Feliot, P., Bect, J., Vazquez, E.: A bayesian approach to constrained single-and multi-objective optimization. J. Global Optim. 67(1–2), 97–133 (2017)
Gramacy, R.B., Lee, H.K.M., Holmes, C., Osborne, M.: Optimization Under Unknown Constraints. In: Bayesian Statistics 9 (2012)
Bernardo, J., et al.: Optimization under unknown constraints. Bayesian Stat. 9(9), 229 (2011)
Hernández-Lobato, J.M., Gelbart, M.A., Hoffman, M.W., Adams, R.P., Ghahramani, Z.: Predictive entropy search for bayesian optimization with unknown constraints. In: Proceedings of the 32nd International Conference on Machine Learning, vol. 37 (2015)
Scholkopf, B., Smola, A.J.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge (2001)
Steinwart, I., Christmann, A.: Support Vector Machines. Springer, New York (2008). https://doi.org/10.1007/978-0-387-77242-4
Basudhar, A., Dribusch, C., Lacaze, S., Missoum, S.: Constrained efficient global optimization with support vector machines. Struct. Multidiscip. Optim. 46(2), 201–221 (2012)
Tsai, Y.A., et al.: Stochastic optimization for feasibility determination: an application to water pump operation in water distribution network. In: Winter Simulation Conference 2018 (WSC 2018) December 9–12, Gothenburg, Sweden (2018)
Candelieri, A., Perego, R., Archetti, F.: Bayesian optimization of pump operations in water distribution systems. J. Global Optim. 71(1), 213–235 (2018)
Letham, B., Karrer, B., Ottoni, G., Bakshy, E.: Constrained Bayesian optimization with noisy experiments. Bayesian Anal. 14, 495–519 (2018)
Hartfiel, D.J., Curry, G.L.: On optimizing certain nonlinear convex functions which are partially defined by a simulation process. Math. Program. 13(1), 88–93 (1977)
Srinivas, N., Krause, A., Kakade, S.M., Seeger, M.: Gaussian process optimization in the bandit setting: No regret and experimental design. In: Proceedings of International Conference on Machine Learning, pp. 1015–1022 (2010)
Neve, A.G., Kakandikar, G.M., Kulkarni, O.: Application of grasshopper optimization algorithm for constrained and unconstrained test functions. Int. J. Swarm Intel. EvolComput. 6(165), 2 (2017)
Simionescu, P.A., Beale, D.G.: New concepts in graphic visualization of objective functions. In ASME 2002 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference, pp. 891–897 (2002)
Mishra, S.K.: Some new test functions for global optimization and performance of repulsive particle swarm method. MPRA Paper No. 2718 (2008)
Castro Gama, M.E., Pan, Q., Salman, M.A.: Jonoski, Multivariate optimization to decrease total energy consumption in the water supply system of Abbiategrasso (Milan, Italy). Environ. Eng. Manag. J. 14(9), 2019–2029 (2015)
Rossman, L.A.: EPANET2 User’s Manual. U.S. Environmental Protection Agency, Washington, DC (2000)
Castro-Gama, M., Pan, Q., Lanfranchi, E.A., Jomoski, A., Solomatine, D.P.: Pump scheduling for a large water distribution network. Milan, Italy. Procedia Eng. 186, 436–443 (2017)
Huang, D., Allen, T.T., Notz, W.I., Zheng, N.: Global optimization of stochastic black-box systems via sequential Kriging meta-models. J. Global Optim. 3(34), 441–466 (2006)
Hoffman, M.D., Brochu, E., De Freitas, N.: Portfolio Allocation for Bayesian Optimization. In: UAI, pp. 327–336 (2011)
Acknowledgements
This study has been partially supported by the Italian project “PerFORM WATER 2030” – programme POR (Programma Operativo Regionale) FESR (Fondo Europeo di Sviluppo Regionale) 2014–2020, innovation call “Accordi per la Ricerca e l’Innovazione” (“Agreements for Research and Innovation”) of Regione Lombardia, (DGR N. 5245/2016 - AZIONE I.1.B.1.3 – ASSE I POR FESR 2014–2020) – CUP E46D17000120009.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Candelieri, A., Galuzzi, B., Giordani, I., Perego, R., Archetti, F. (2020). Optimizing Partially Defined Black-Box Functions Under Unknown Constraints via Sequential Model Based Optimization: An Application to Pump Scheduling Optimization in Water Distribution Networks. In: Matsatsinis, N., Marinakis, Y., Pardalos, P. (eds) Learning and Intelligent Optimization. LION 2019. Lecture Notes in Computer Science(), vol 11968. Springer, Cham. https://doi.org/10.1007/978-3-030-38629-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-030-38629-0_7
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-38628-3
Online ISBN: 978-3-030-38629-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)