×

zbMATH — the first resource for mathematics

Tuning BARON using derivative-free optimization algorithms. (English) Zbl 1428.90135
Summary: Optimization solvers include many options that allow users to control algorithmic aspects that may have a considerable impact on solver performance. Tuning solver options is often necessary to reduce execution time and improve solution quality. Previous studies of solver tuning techniques have focused on mixed-integer linear programming and local nonlinear programming solvers. In this paper, we investigate the potential of tuning a global optimization solver for nonlinear and mixed-integer nonlinear programming problems. In particular, derivative-free optimization (DFO) algorithms are used to find optimal values for options of the global optimization solver BARON. A set of 126 problems from the GLOBALLib and MINLPLib collections are utilized in a computational study from which we conclude that tuning options can improve the default performance of BARON for individual problems and an entire library. Additionally, we present a systematic comparison of 27 DFO solvers in terms of their ability to improve the performance of the global solver. We find that several DFO implementations are much better than others in terms of finding optimal tuning parameters.

MSC:
90C26 Nonconvex programming, global optimization
90C56 Derivative-free methods and methods using generalized derivatives
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Audet, C.; Dennis, JE, Mesh adaptive direct search algorithms for constrained optimization, SIAM J. Optim., 17, 188-217, (2006) · Zbl 1112.90078
[2] Audet, C.; Orban, D., Finding optimal algorithmic parameters using derivative-free optimization, Soc. Ind. Appl. Math., 17, 642-664, (2001) · Zbl 1128.90060
[3] Bao, X.; Sahinidis, NV; Tawarmalani, M., Multiterm polyhedral relaxations for nonconvex, quadratically-constrained quadratic programs, Optim. Methods Softw., 24, 485-504, (2009) · Zbl 1179.90252
[4] Bartholomew-Biggs, MC; Parkhurst, SC; Wilson, SP, Using DIRECT to solve an aircraft routing problem, Comput. Optim. Appl., 21, 311-323, (2002) · Zbl 1017.90133
[5] Baz, M., Hunsaker, B.: Automated Tuning of Optimization Software Parameters. Technical report. Department of Industrial Engineering, University of Pittsburgh, Pittsburgh, PA (2007)
[6] Baz, M.; Hunsaker, B.; Prokopyev, O., How much do we “pay” for using default parameters?, Comput. Optim. Appl., 48, 91-108, (2011) · Zbl 1209.90275
[7] Bussieck, MR; Drud, AS; Meeraus, A., MINLPLib-A collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput., 15, 114-119, (2003) · Zbl 1238.90104
[8] Chen, W.; Shao, Z.; Wang, K.; Chen, X.; Biegler, LT, Random sampling-based automatic parameter tuning for nonlinear programming solvers, Ind. Eng. Chem. Res., 50, 3907-3918, (2011)
[9] Conn, AR; Scheinberg, K.; Toint, PL; Buhmann, MD (ed.); Iserles, A. (ed.), On the convergence of derivative-free methods for unconstrained optimization, 83-108, (1996), Cambridge
[10] Custódio, AL; Dennis, JE; Vicente, LN, Using simplex gradients of nonsmooth functions in direct search methods, IMA J. Numer. Anal., 28, 770-784, (2008) · Zbl 1156.65059
[11] Fan, SS; Zahara, E., A hybrid simplex search and particle swarm optimization for unconstrained optimization, Eur. J. Oper. Res., 181, 527-548, (2007) · Zbl 1121.90116
[12] Fowler, KR; Reese, JP; Kees, CE; Dennis, JE; Kelley, CT; Miller, CT; Audet, C.; Booker, AJ; Couture, G.; Darwin, RW; Farthing, MW; Finkel, DE; Gablonsky, JM; Gray, G.; Kolda, TG, A comparison of derivative-free optimization methods for groundwater supply and hydraulic capture community problems, Adv. Water Resour., 31, 743-757, (2008)
[13] GLOBAL Library. http://www.gamsworld.org/global/globallib.htm. Accessed 25 Feb 2018
[14] Gutmann, HM, A radial basis function method for global optimization, J. Glob. Optim., 19, 201-227, (2001) · Zbl 0972.90055
[15] Han, J.; Kokkolaras, M.; Papalambros, PY, Optimal design of hybrid fuel cell vehicles, J. Fuel Cell Sci. Technol., 5, 041014, (2008)
[16] Hutter, F.; Hoos, HH; Stützle, T.; Howe, A. (ed.); Holte, RC (ed.), Automatic algorithm configuration based on local search, 1152-1157, (2007), Menlo Park, CA
[17] Hutter, F.; Hoos, HH; Leyton-Brown, K., Automated configuration of mixed integer programming solvers, LNCS, 6140, 186-202, (2010)
[18] Hutter, F., Hoos, H.H., Leyton-Brown, K.: Sequential model-based optimization for general algorithm configurations. In: Coello, C.A.C. (ed.) Learning and Intelligent Optimization, pp. 507-523. Springer, Berlin (2011)
[19] Hutter, F.; Hoos, HH; Leyton-Brown, K.; Stützle, T., ParamILS: an antomatic algorithm configuration framework, J. Artif. Intell. Res., 36, 267-306, (2009) · Zbl 1192.68831
[20] Huyer, W.; Neumaier, A., Global optimization by multilevel coordinate search, J. Glob. Optim., 14, 331-355, (1999) · Zbl 0956.90045
[21] Hvattum, LM; Glover, F., Finding local optima of high-dimensional functions using direct search methods, Eur. J. Oper. Res., 195, 31-45, (2009) · Zbl 1156.90440
[22] Ingber, L.: Adaptive Simulated Annealing (ASA). http://www.ingber.com/#ASA. Accessed 25 Feb 2018
[23] Jones, DR; Perttunen, CD; Stuckman, BE, Lipschitzian optimization without the Lipschitz constant, J. Optim. Theory Appl., 79, 157-181, (1993) · Zbl 0796.49032
[24] Liu, ML; Sahinidis, NV; Shectman, JP; Grossmann, IE (ed.), Planning of chemical process networks via global concave minimization, 195-230, (1996), Boston · Zbl 0874.90140
[25] Mongeau, M.; Karsenty, H.; Rouzé, V.; Hiriart-Urruty, JB, Comparison of public-domain software for black box global optimization, Optim. Methods Softw., 13, 203-226, (2000) · Zbl 0963.90062
[26] Moré, JM; Wild, SM, Benchmarking derivative-free optimization algorithms, SIAM. J. Optim., 20, 172-191, (2009) · Zbl 1187.90319
[27] Nelder, JA; Mead, R., A simplex method for function minimization, Comput. J., 7, 308-313, (1965) · Zbl 0229.65053
[28] Powell, MJD; Gomez, S. (ed.); Hennart, JP (ed.), A direct search optimization method that models the objective and constraint functions by linear interpolation, 51-67, (1994), Dordrecht
[29] Powell, M.J.D.: Recent research at Cambridge on radial basis functions. Technical report. Department of Applied Mathematics and Theoretical Physics, University of Cambridge (1998) · Zbl 0958.41501
[30] Puranik, Y.; Sahinidis, NV, Bounds tightening based on optimality conditions for nonconvex box-constrained optimization, J. Glob. Optim., 67, 59-77, (2017) · Zbl 1359.90107
[31] Puranik, Y.; Sahinidis, NV, Domain reduction techniques for global NLP and MINLP optimization, Constraints, 22, 338-376, (2017) · Zbl 1387.90164
[32] Rios, LM; Sahinidis, NV, Derivative-free optimization: a review of algorithms and comparison of software implementations, J. Glob. Optim., 56, 1247-1293, (2013) · Zbl 1272.90116
[33] Ryoo, HS; Sahinidis, NV, Global optimization of nonconvex NLPs and MINLPs with applications in process design, Comput. Chem. Eng., 19, 551-566, (1995)
[34] Ryoo, HS; Sahinidis, NV, A branch-and-reduce approach to global optimization, J. Glob. Optim., 8, 107-139, (1996) · Zbl 0856.90103
[35] Sahinidis, NV, BARON: a general purpose global optimization software package, J. Glob. Optim., 8, 201-205, (1996) · Zbl 0856.90104
[36] Sahinidis, NV; Bliek, C. (ed.); Jermann, C. (ed.); Neumaier, A. (ed.), Global optimization and constraint satisfaction: the branch-and-reduce approach, No. 2861, 1-16, (2003), Berlin
[37] Sahinidis, N.V.: BARON 15.5.0: Global Optimization of Mixed-Integer Nonlinear Programs, User’s Manual (2015)
[38] Shectman, JP; Sahinidis, NV, A finite algorithm for global minimization of separable concave programs, J. Glob. Optim., 12, 1-36, (1998) · Zbl 0906.90159
[39] Spendley, W.; Hext, GR; Himsworth, FR, Sequential application for simplex designs in optimisation and evolutionary operation, Technometrics, 4, 441-461, (1962) · Zbl 0121.35603
[40] Stewart, C.R.: Master’s thesis. Vriginia Commonwealth University, Richmond, VA (2010)
[41] Tawarmalani, M.; Ahmed, S.; Sahinidis, NV, Product disaggregation and relaxations of mixed-integer rational programs, Optim. Eng., 3, 281-303, (2002) · Zbl 1035.90064
[42] Tawarmalani, M.; Sahinidis, NV, Convex extensions and convex envelopes of l.s.c. functions, Math. Program., 93, 247-263, (2002) · Zbl 1065.90062
[43] Tawarmalani, M.; Sahinidis, NV, Global optimization of mixed-integer nonlinear programs: a theoretical and computational study, Math. Program., 99, 563-591, (2004) · Zbl 1062.90041
[44] Tawarmalani, M.; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[45] Torczon, VJ, On the convergence of pattern search algorithms, SIAM J. Optim., 7, 1-25, (1997) · Zbl 0884.65053
[46] Vaz, A.I.F.: PSwarm Home Page. http://www.norg.uminho.pt/aivaz/pswarm/. Accessed 25 Feb 2018
[47] Vaz, AIF; Vicente, LN, A particle swarm pattern search method for bound constrained global optimization, J. Glob. Optim., 39, 197-219, (2007) · Zbl 1180.90252
[48] Zorn, K.; Sahinidis, NV, Global optimization of general nonconvex problems with intermediate bilinear substructures, Optim. Methods Softw., 29, 442-462, (2013) · Zbl 1285.90043
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.