×

zbMATH — the first resource for mathematics

Bound constrained interval global optimization in the COCONUT environment. (English) Zbl 1302.90152
Summary: We introduce a new interval global optimization method for solving bound constrained problems. The method originates from a small standalone software and is implemented in the COCONUT Environment, a framework designed for the development of complex algorithms, containing numerous state-of-the-art methods in a common software platform. The original algorithm is enhanced by various new methods implemented in COCONUT, regarding both interval function evaluations (such as first and second order derivatives with backward automatic differentiation, slopes, slopes of derivatives, bicentered forms, evaluations on the Karush-John conditions, etc.) and algorithmic elements (inclusion/exclusion boxes, local search, constraint propagation). This resulted in a substantial performance increase as compared to the original code. During the selection of the best combination of options, we performed comparison tests that gave empirical answers to long-lasting algorithmic questions (such as whether to use interval gradients or use slopes instead), that have never been studied numerically in such detail before. The new algorithm, called coco_gop_ex, was tested against the prestigious BARON software on an extensive set of bound constrained problems. We found that in addition to accepting a wider class of bound constrained problems and providing more output information (by locating all global minimizers), coco_gop_ex is competitive with BARON in terms of the solution success rates (with the exception of a set of nonlinear least squares problems), and it often outperforms BARON in running time. In particular, coco_gop_ex was around 21 % faster on average over the set of problems solved by both software systems.

MSC:
90C25 Convex programming
90-04 Software, source code, etc. for problems pertaining to operations research and mathematical programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baumann, E, Optimal centered forms, BIT Numer. Math., 28, 80-87, (1988) · Zbl 0641.65043
[2] Bliek, C.: Computer methods for design automation. PhD thesis, Department of Ocean Engineering, Massachusetts Institute of Technology (1992)
[3] Byrd, RH; Lu, P; Nocedal, J; Zhu, C, A limited memory algorithm for bound constrained optimization, SIAM J. Sci. Comput., 16, 1190-1208, (1995) · Zbl 0836.65080
[4] COCONUT Environment. Software, University of Vienna. http://www.mat.univie.ac.at/coconut-environment · Zbl 1080.65041
[5] Csendes, T; Ratz, D, Subdivision direction selection in interval methods for global optimization, SIAM J. Numer. Anal., 34, 922-938, (1997) · Zbl 0873.65063
[6] Gebremedhin, AH; Manne, F; Pothen, A, What color is your Jacobian? graph coloring for computing derivatives, SIAM Rev., 47, 629-705, (2005) · Zbl 1076.05034
[7] Griewank, A., Corliss, G.F.: Automatic Differentiation of Algorithms. SIAM, Philadelphia (1991) · Zbl 0747.00030
[8] Hammer, R., Hocks, M., Kulisch, U., Ratz, D.: C++ Toolbox for Verified Computing. Springer, Heidelberg (1995)
[9] Kearfott, RB; Du, K, The cluster problem in multivariate global optimization, J. Glob. Optim., 5, 253-265, (1994) · Zbl 0824.90121
[10] Kieffer, M., Markót, M.C., Schichl, H., Walter, E.: Verified global optimization for estimating the parameters of nonlinear models. In: Rauh, A., Auer, E. (eds.) Modeling, Design, and Simulation of Systems with Uncertainties, Chapter 7, Mathematical Engineering. Springer, New York (2011) · Zbl 1089.90045
[11] Kolev, LV, Use of interval slopes for the irrational part of factorable functions, Reliab. Comput., 3, 83-93, (1997) · Zbl 0878.65036
[12] Markót, MC; Csendes, T, A new verified optimization technique for the “packing circles in a unit square” problems, SIAM J. Optim., 16, 193-219, (2005) · Zbl 1089.90045
[13] Markót, MC; Csendes, T; Csallner, AE, Multisection in interval branch-and-bound methods for global optimization II. numerical tests, J. Glob. Optim., 16, 219-228, (2000) · Zbl 0971.90066
[14] Markót, MC; Fernández, J; Casado, LG; Csendes, T, New interval methods for constrained global optimization, Math. Program., 106, 287-318, (2006) · Zbl 1134.90497
[15] Markót, MC; Schichl, H, Comparison and automated selection of local optimization solvers for interval global optimization methods, SIAM J. Optim., 21, 1371-1391, (2011) · Zbl 1256.65057
[16] Moore, R.E., Kearfott, R.B., Cloud, M.J.: Introduction to Interval Analysis. SIAM, Philadelphia (2009) · Zbl 1168.65002
[17] Neumaier, A; Moore, RE (ed.), The enclosure of solutions of parameter-dependent systems of equations, 269-286, (1988), San Diego
[18] Neumaier, A.: Interval Methods for Systems of Equations. Vol. 37 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (1990)
[19] Ratschek, H, Centered forms, SIAM J. Numer. Anal., 17, 656-662, (1980) · Zbl 0456.65019
[20] Sahinidis, N.V., Tawarmalani, M.: BARON 9.0.4: global optimization of mixed-integer nonlinear programs, user’s manual, 2010. http://www.gams.com/dd/docs/solvers/baron.pdf · Zbl 0824.90121
[21] Schichl, H; Neumaier, A, Interval analysis on directed acyclic graphs for global optimization, J. Glob. Optim., 33, 541-562, (2005) · Zbl 1094.65061
[22] Schichl, H.: Mathematical Modeling and Global Optimization. Habilitation Thesis, draft of a book, Cambridge University Press (to appear) · Zbl 1099.90047
[23] Schichl, H; Neumaier, A, Exclusion regions for systems of equations, SIAM J. Numer. Anal., 42, 383-408, (2004) · Zbl 1080.65041
[24] Schichl, H; Markót, MC, Algorithmic differentiation techniques for global optimization in the COCONUT environment, Optim. Methods Softw., 27, 359-372, (2012) · Zbl 1242.65047
[25] Schichl, H., Markót, M.C., Neumaier, A.: Exclusion regions for optimization problems (in preparation) · Zbl 1297.65070
[26] Tawarmalani, M; Sahinidis, NV, A polyhedral branch-and-cut approach to global optimization, Math. Program., 103, 225-249, (2005) · Zbl 1099.90047
[27] Van Hentenryck, P., Numerica: a modeling language for global optimization. In: Proceedings of the 15th international joint conference on artificial intelligence (IJCAI-97) (1997) · Zbl 0905.65070
[28] Vu, X-H; Schichl, H; Sam-Haroud, D, Interval propagation and search on directed acyclic graphs for numerical constraint solving, J. Global Optim., 45, 499-531, (2009) · Zbl 1179.90267
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.