A method for convex black-box integer global optimization. (English) Zbl 1473.90181

Summary: We study the problem of minimizing a convex function on a nonempty, finite subset of the integer lattice when the function cannot be evaluated at noninteger points. We propose a new underestimator that does not require access to (sub)gradients of the objective; such information is unavailable when the objective is a blackbox function. Rather, our underestimator uses secant linear functions that interpolate the objective function at previously evaluated points. These linear mappings are shown to underestimate the objective in disconnected portions of the domain. Therefore, the union of these conditional cuts provides a nonconvex underestimator of the objective. We propose an algorithm that alternates between updating the underestimator and evaluating the objective function. We prove that the algorithm converges to a global minimum of the objective function on the feasible set. We present two approaches for representing the underestimator and compare their computational effectiveness. We also compare implementations of our algorithm with existing methods for minimizing functions on a subset of the integer lattice. We discuss the difficulty of this problem class and provide insights into why a computational proof of optimality is challenging even for moderate problem sizes.


90C56 Derivative-free methods and methods using generalized derivatives
90C10 Integer programming
90C25 Convex programming
90C26 Nonconvex programming, global optimization
Full Text: DOI arXiv


[1] Abhishek, K.; Leyffer, S.; Linderoth, JT, Modeling without categorical variables: a mixed-integer nonlinear program for the optimization of thermal insulation systems, Optim. Eng., 11, 2, 185-212 (2010) · Zbl 1273.80009
[2] Abramson, M.; Audet, C.; Chrissis, J.; Walston, J., Mesh adaptive direct search algorithms for mixed variable optimization, Optim. Lett., 3, 1, 35-47 (2009) · Zbl 1154.90551
[3] Audet, C.; Dennis, JE Jr, Pattern search algorithms for mixed variable programming, SIAM J. Optim., 11, 3, 573-594 (2000) · Zbl 1035.90048
[4] Audet, C.; Hare, WL, Derivative-Free and Blackbox Optimization (2017), Berlin: Springer, Berlin · Zbl 1391.90001
[5] Audet, C.; Le Digabel, S.; Tribes, C., The mesh adaptive direct search algorithm for granular and discrete variables, SIAM J. Optim., 29, 2, 1164-1189 (2019) · Zbl 1411.90229
[6] Balaprakash, P.; Tiwari, A.; Wildand, SM; Jarvis, SA; Wright, SA; Hammond, SD, Multi-objective optimization of HPC kernels for performance, power, and energy, High Performance Computing Systems Performance Modeling, Benchmarking and Simulation, 239-260 (2014), Berlin: Springer, Berlin
[7] Bartz-Beielstein, T.; Zaefferer, M., Model-based methods for continuous and discrete global optimization, Appl. Soft Comput., 55, 154-167 (2017)
[8] Bonami, P.; Biegler, L.; Conn, A.; Cornuéjols, G.; Grossmann, I.; Laird, C.; Lee, J.; Lodi, A.; Margot, F.; Sawaya, N.; Wächter, A., An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim., 5, 2, 186-204 (2008) · Zbl 1151.90028
[9] Borwein, JM; Bailey, DH; Girgensohn, R.; Bailey, DH; Borwein, JM, Experimentation in Mathematics: Computational Paths to Discovery (2004), Boca Raton: CRC Press, Boca Raton · Zbl 1083.00002
[10] Borwein, JM; Vanderwerff, JD, Convex Functions: Constructions Characterizations and Counterexamples (2010), Cambridge: Cambridge University Press, Cambridge · Zbl 1191.26001
[11] Boyd, S.; Vandenberghe, L., Convex Optimization (2004), Cambridge: Cambridge University Press, Cambridge · Zbl 1058.90049
[12] Buchheim, C.; Kuhlmann, R.; Meyer, C., Combinatorial optimal control of semilinear elliptic PDEs, Comput. Optim. Appl., 70, 3, 641-675 (2018) · Zbl 1397.49030
[13] Charalambous, C.; Bandler, JW, Non-linear minimax optimization as a sequence of least \(p\) th optimization with finite values of \(p\), Int. J. Syst. Sci., 7, 4, 377-391 (1976) · Zbl 0349.90108
[14] Charalambous, C.; Conn, AR, An efficient method to solve the minimax problem directly, SIAM J. Numer. Anal., 15, 1, 162-187 (1978) · Zbl 0384.65032
[15] Conn, AR; Scheinberg, K.; Vicente, LN, Introduction to Derivative-Free Optimization (2009), Philadelphia: SIAM, Philadelphia · Zbl 1163.49001
[16] Costa, A.; Nannicini, G., RBFOpt: an open-source library for black-box optimization with costly function evaluations, Math. Program. Comput., 10, 4, 597-629 (2018) · Zbl 1411.90005
[17] Davis, E.; Ierapetritou, M., A kriging based method for the solution of mixed-integer nonlinear programs containing black-box functions, J. Glob. Optim., 43, 2-3, 191-205 (2009) · Zbl 1179.90238
[18] Dennis, JE Jr; Woods, DJ; Wouk, A., Optimization on microcomputers: the Nelder-Mead simplex algorithm, New Computing Environments: Microcomputers in Large-Scale Computing, 116-122 (1987), Philadelphia: SIAM, Philadelphia
[19] Dolan, ED; Moré, J., Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[20] Duran, MA; Grossmann, IE, An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Math. Program., 36, 3, 307-339 (1986) · Zbl 0619.90052
[21] Fletcher, R.; Leyffer, S., Solving mixed integer nonlinear programs by outer approximation, Math. Program., 66, 1-3, 327-349 (1994) · Zbl 0833.90088
[22] García-Palomares, UM; Rodríguez-Hernández, PS, Unified approach for solving box-constrained models with continuous or discrete variables by non monotone direct search methods, Optim. Lett., 13, 1, 95-111 (2019) · Zbl 1417.90119
[23] Geoffrion, AM; Marsten, RE, Integer programming algorithms: a framework and state-of-the-art survey, Manag. Sci., 18, 9, 465-491 (1972) · Zbl 0238.90043
[24] Graf, PA; Billups, S., MDTri: robust and efficient global mixed integer search of spaces of multiple ternary alloys, Comput. Optim. Appl., 68, 3, 671-687 (2017) · Zbl 1391.90431
[25] Haarala, M.; Miettinen, K.; Mäkelä, MM, New limited memory bundle method for large-scale nonsmooth optimization, Optim. Methods Softw., 19, 6, 673-692 (2004) · Zbl 1068.90101
[26] Hemker, T.; Fowler, K.; Farthing, M.; von Stryk, O., A mixed-integer simulation-based optimization approach with surrogate functions in water resources management, Optim. Eng., 9, 4, 341-360 (2008) · Zbl 1419.90007
[27] Hemmecke, R., Köppe, M., Lee, J., Weismantel, R.: Nonlinear integer programming. In: 50 Years of Integer Programming 1958-2008. Springer, pp. 561-618, pp. 561-618 (2010). doi:10.1007/978-3-540-68279-0_15 · Zbl 1187.90270
[28] Holmström, K.; Quttineh, NH; Edvall, M., An adaptive radial basis algorithm (ARBF) for expensive black-box mixed-integer constrained global optimization, Optim. Eng., 9, 4, 311-339 (2008) · Zbl 1400.90226
[29] Jian, N.; Henderson, SG, Estimating the probability that a function observed with noise is convex, INFORMS J. Comput. (2019) · Zbl 07290852
[30] Jian, N., Henderson, S.G., Hunter, S.R.: Sequential detection of convexity from noisy function evaluations. In: Proceedings of the Winter Simulation Conference. IEEE (2014). doi:10.1109/wsc.2014.7020215
[31] Kiwiel, KC, An ellipsoid trust region bundle method for nonsmooth convex minimization, SIAM J. Control Optim., 27, 4, 737-757 (1989) · Zbl 0694.65026
[32] Kolda, TG; Lewis, RM; Torczon, VJ, Optimization by direct search: new perspectives on some classical and modern methods, SIAM Rev., 45, 3, 385-482 (2003) · Zbl 1059.90146
[33] Larson, J.; Menickelly, M.; Wild, SM, Derivative-free optimization methods, Acta Numer., 28, 287-404 (2019) · Zbl 1461.65169
[34] Le Digabel, S., Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm, ACM Trans. Math. Softw., 37, 4, 1-15 (2011) · Zbl 1365.65172
[35] Le Digabel, S., Wild, S.M.: A taxonomy of constraints in black-box simulation-based optimization. Preprint ANL/MCS-P5350-0515, Argonne (2015-01). http://www.mcs.anl.gov/papers/P5350-0515.pdf
[36] Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for bound constrained mixed-integer optimization, Comput. Optim. Appl., 53, 2, 505-526 (2011) · Zbl 1257.90058
[37] Liuzzi, G.; Lucidi, S.; Rinaldi, F., Derivative-free methods for mixed-integer constrained optimization problems, J. Optim. Theory Appl., 164, 3, 933-965 (2015) · Zbl 1321.90087
[38] Liuzzi, G.; Lucidi, S.; Rinaldi, F., An algorithmic framework based on primitive directions and nonmonotone line searches for black-box optimization problems with integer variables, Math. Program. Comput., 12, 4, 673-702 (2020) · Zbl 1452.90322
[39] Moré, JJ; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM J. Optim., 20, 1, 172-191 (2009) · Zbl 1187.90319
[40] Müller, J.: MATSuMoTo: the MATLAB surrogate model toolbox for computationally expensive black-box global optimization problems. Technial Report 1404.4261, arXiv (2014). https://arxiv.org/abs/1404.4261
[41] Müller, J., MISO: mixed-integer surrogate optimization framework, Opim. Eng., 17, 1, 177-203 (2016) · Zbl 1364.90230
[42] Müller, J.; Shoemaker, CA; Piché, R., SO-I: a surrogate model algorithm for expensive nonlinear integer programming problems including global optimization applications, J. Glob. Optim., 59, 4, 865-889 (2013) · Zbl 1305.90305
[43] Müller, J.; Shoemaker, CA; Piché, R., SO-MI: a surrogate model algorithm for computationally expensive nonlinear mixed-integer black-box global optimization problems, Comput. Oper. Res., 40, 5, 1383-1400 (2013) · Zbl 1352.90067
[44] Newby, E.; Ali, MM, A trust-region-based derivative free algorithm for mixed integer programming, Comput. Optim. Appl., 60, 1, 199-229 (2015) · Zbl 1308.90112
[45] Porcelli, M.; Toint, PL, BFO, a trainable derivative-free brute force optimizer for nonlinear bound-constrained optimization and equilibrium computations with continuous and discrete variables, ACM Trans. Math. Softw., 44, 1, 1-25 (2017) · Zbl 1484.65136
[46] Rashid, K.; Ambani, S.; Cetinkaya, E., An adaptive multiquadric radial basis function method for expensive black-box mixed-integer nonlinear constrained optimization, Eng. Optim., 45, 2, 185-206 (2012)
[47] Richter, P.; Ábrahám, E.; Morin, G.; Dobnikar, A.; Lotrič, U.; Šter, B., Optimisation of concentrating solar thermal power plants with neural networks, Adaptive and Natural Computing Algorithms, 190-199 (2011), Berlin: Springer, Berlin
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.