×

zbMATH — the first resource for mathematics

Mathematically rigorous global optimization in floating-point arithmetic. (English) Zbl 1398.65093
Summary: This paper gives details on how to obtain mathematically rigorous results for global unconstrained and equality constrained optimization problems, as well as for finding all roots of a nonlinear function within a box. When trying to produce mathematically rigorous results for such problems of global nature, the main issue is to mathematically verify that a certain sub-box cannot contain a solution to the problem, i.e. to discard boxes. The presented verification methods are based on mathematical theorems, the assumptions of which are verified using Algorithmic Differentiation and interval arithmetic. In contrast to traditional numerical algorithms, the main problem of verification methods is how to formulate those assumptions. We present mathematical and implementation details on how to obtain fast verification algorithms in pure Matlab/Octave code. The methods are implemented in INTLAB, the Matlab/Octave toolbox for Reliable Computing. Several examples together with executable code show advantages and weaknesses of the proposed methods. New results are included, however, the main goal is to introduce and give enough details to understand black-box Matlab/Octave routines to solve the mentioned problems. An outlook on current research on verification methods for large problems with several million variables and several tens of thousands of constraints based on conic programming is given as well. The latter can be regarded as an extension of interval arithmetic.
MSC:
65G20 Algorithms with automatic result verification
65H20 Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bouissou, O.; Goubault, E.; Goubault-Larrecq, J.; Putot, S., A generalization of p-boxes to affine arithmetic, Computing, 94, 2-4, 180-201, (2012) · Zbl 1247.60006
[2] Chaykin, D.; Jansson, C.; Keil, F.; Lange, M.; Ohlhus, K. T.; Rump, S. M., rigorous results in electronic structure calculations, Optim. online, (2016)
[3] ADMAT-2.0, 2012. Available at
[4] Collatz, L., einschließungssatz für die charakteristischen zahlen von matrizen, Math. Z., 48, 221-226, (1942) · Zbl 0027.00604
[5] Affine arithmetic and its applications to computer graphics. In Proceedings SIBGRAPI’93 - VI Simposio Brasileiro de Computacao Grafica e Processamento de Imagens (Recife, Brazil), October 20–22, 1993, pp. 9–18
[6] Performance of a multifrontal scheme for partially separable optimization, Technical Report 88/4, Dept of Mathematics, FUNDP (Namur, B), 1988
[7] Csendes, T., interval method for bounding level sets: revisited and tested with global optimization problems, BIT Numer. Math., 30, 650-657, (1990) · Zbl 0726.65069
[8] Csendes, T.; Pintér, J., the impact of accelerating tools on the interval subdivision algorithm for global optimization, Eur J Oper Res, 65, 314-320, (1993) · Zbl 0768.90068
[9] Csendes, T.; Pál, L.; Sedín, J. O.H.; Banga, J. R., the GLOBAL optimization method revisited, Optim. Lett., 2, 445-454, (2008) · Zbl 1160.90660
[10] GLOPT - a program for constrained global optimization, in Developments in global optimization nonconvex optimization and its applications, I.M. Bomze, T. Csendes, R. Horst, and P.M. Pardalos, eds., Kluwer Academic Publishers, Boston, MA, 1997, pp. 19–36
[11] On floating point errors in Cholesky, LAPACK Working Note 14 CS-89-87, Department of Computer Science, University of Tennessee, Knoxville, TN, USA, 1989
[12] de Figueiredo, L. H.; Stolfi, J., affine arithmetic: concepts and applications, Numer Algorithms, 37, 1-4, 147-158, (2004) · Zbl 1074.65050
[13] Forth, S. A., simplifying multivariate second-order response surfaces by Fitting constrained models using automatic differentiation, Technometrics, 47, 3, 249-259, (2005)
[14] Forth, S. A., an efficient overloaded implementation of forward mode automatic differentiation in Matlab, ACM Trans. Math. Softw., 32, 2, 195-222, (2006) · Zbl 1365.65053
[15] Gargantini, I.; Henrici, P., circular arithmetic and the determination of polynomial zeros, Numer. Math., 18, 305-320, (1972) · Zbl 0228.65038
[16] GNU Octave. Release 4.0.1 User’s Guide, 2016.
[17] Golub, G. H.; Van Loan, Ch., Matrix Computations, (1996), Johns Hopkins University Press, Baltimore, MD · Zbl 0865.65009
[18] Griewank, A. O., generalized descent for global optimization, J. Optim. Theory Appl., 34, 11-39, (1981) · Zbl 0431.49036
[19] Griewank, A.; Walther, A., Evaluating Derivatives, Principles and Techniques of Algorithmic Differentiation, (2008), SIAM, Philadelphia, PA, USA · Zbl 1159.65026
[20] Trufflec: Dynamic execution of c on a java virtual machine, in Proceedings of the 2014 International Conference on Principles and Practices of Programming on the Java Platform: Virtual Machines, Languages, and Tools, ACM, New York, NY, 2014, pp. 17–26. Available at
[21] Hammer, M.; Hocks, R.; Kulisch, U.; Ratz, D., C++ Toolbox for Verified Computing, (1995), Springer, Heidelberg · Zbl 0828.68041
[22] Hansen, E. R.; Sengupta, S., bounding solutions of systems of equations using interval analysis, BIT Numer. Math., 21, 203-211, (1981) · Zbl 0455.65037
[23] Hansen, E.; Walster, G. W., Global Optimization using Interval Analysis, (2003), Dekker, New York
[24] Higham, N. J., Accuracy and Stability of Numerical Algorithms, (1996), SIAM Publications, Philadelphia · Zbl 0847.65010
[25] ANSI/IEEE 754-2008: IEEE standard for floating-point arithmetic, IEEE, New York, 2008
[26] ANSI/IEEE 754-1985: IEEE standard for binary floating-point arithmetic, IEEE, New York, 1985
[27] An interval method for global unconstrained optimization, in Operations Research, Vol. 91, P. Gritzmann, R. Hettich, R. Horst, and E. Sachs, eds., Physica Verlag, Heidelberg, 1991, pp. 102–105
[28] On Self-validating methods for optimization problems, in Topics in Validated Computations – Studies in Computational Mathematics, Vol. 5, J. Herzberger, ed., North-Holland, Amsterdam, 1994, pp. 381–438 · Zbl 0817.65044
[29] Jansson, C., A rigorous lower bound for the optimal value of convex optimization problems, J. Global Optim., 28, 121-137, (2004) · Zbl 1134.90461
[30] Jansson, C., on verification of ill-posed optimization problems, ECMI Newsletter, 39, 18, (2006)
[31] Jansson, C., on verified numerical computations in convex programming, Japan J. Indust. Appl. Math., 26, 337-363, (2009) · Zbl 1184.90124
[32] Private communication, 2016
[33] A more complete interval arithmetic. Lecture notes for a summer course at the University of Michigan, June 17–21, 1968
[34] GlobSol. World Wide Web. Available at
[35] Kearfott, R. B., an interval branch and bound algorithm for bound constrained optimization problems, J. Global Optim., 2, 259-280, (1992) · Zbl 0760.90085
[36] A review of techniques in the verified solution of constrained global optimization problems, in Applications of Interval Computations – Proceedings of An International Workshop, El Paso, TX, USA, February 23–25, 1995, R.B. Kearfott, et al., eds., Kluwer Academic Publisher, Dordrecht, 1996, pp. 23–59
[37] Kearfott, R. B., on proving existence of feasible points in equality constrained optimization problems, Math. Program., 83, 1, 89-100, (1998) · Zbl 0949.90089
[38] Kearfott, R. B.; Dawande, M.; Hu, C., intlib: A portable Fortran-77 interval standard function library, ACM Trans. Math. Softw., 20, 447-459, (1994) · Zbl 0888.65057
[39] Source transformation for Matlab automatic differentiation, in Computational Science – ICCS 2006, V.N. Alexandrov, G.D. van Albada, P.M.A. Sloot, and J. Dongarra, eds., Springer Berlin Heidelberg, Berlin, 2006, pp. 558–565 · Zbl 1157.65529
[40] Klatte, R.; Kulisch, U.; Neaga, M.; Ratz, D.; Ullrich, Ch., PASCAL-XSC: Language Reference with Examples, (1992), Springer, Heidelberg, New York · Zbl 0757.68023
[41] Einschließungsmethoden zur Bestimmung der Nullstellen nichtlinearer Gleichungssysteme und ihre Implementierung, Ph.D. thesis, Technische Universität Hamburg-Harburg, 1994
[42] Knüppel, O., PROFIL / BIAS – a fast interval library, Computing, 53, 277-287, (1994) · Zbl 0808.65055
[43] Krawczyk, R., Newton-algorithmen zur bestimmung von nullstellen mit fehlerschranken, Computing, 4, 187-201, (1969) · Zbl 0187.10001
[44] Semidefinite relaxation approaches for the quadratic assignment problem, Ph.D. thesis, Hamburg Technical University, 2016
[45] MATLAB. User’s Guide, Version 2017b, the MathWorks Inc., 2017
[46] Module GOP in the C-XSC Version 2.5.4 C++ Toolbox, 2014. Available at
[47] Module GOP in the C-XSC 2.5.4 c++ toolbox
[48] Intsolver: An interval based toolbox for global optimization. Version 1.0, 2009. Available at
[49] Moore, R. E., A test for existence of solutions to nonlinear systems, SIAM J. Numer. Anal., 4, 611-615, (1977) · Zbl 0365.65034
[50] Rigorous methods for global optimization, in In Recent Advances in Global Optimization, Princeton Series in Computer Science, Princeton University Press, Princeton, NJ, 1992, pp. 321–342
[51] Nakata, M.; Nakatsuji, H.; Ehara, M.; Fukuda, M.; Nakata, K.; Fujisawa, K., variational calculations of fermion second-order reduced density matrices by semidefinite programming algorithm, J. Chem. Phys., 114, 19, 8282-8292, (2001)
[52] Ben-Tal, A.; Nemirovski, A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, (2001), Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 0986.90032
[53] Neumaier, A., Interval Methods for Systems of Equations, (1990), Cambridge University Press, Cambridge · Zbl 0706.15009
[54] Neumaier, A., second-order sufficient optimality conditions for local and global nonlinear programming, J. Global Optim., 9, 141-151, (1996) · Zbl 0868.90112
[55] Complete search in continuous global optimization and constraint satisfaction, in Acta Numerica, Vol. 13, A. Iserles, ed., Cambridge University Press, Cambridge, 2004, pp. 271–369 · Zbl 1113.90124
[56] Neumaier, A.; Shcherbina, O.; Huyer, W.; Vinko, T., A comparison of complete global optimization solvers, Math. Program., 103, 335-356, (2005) · Zbl 1099.90001
[57] Private communication, 1998 · Zbl 1015.91507
[58] Pál, L.; Csendes, T., INTLAB implementation of an interval global optimization algorithm, Optim. Methods Softw., 24, 749-759, (2009) · Zbl 1180.90318
[59] Payne, M.; Hanek, R., Radian reduction for trigonometric functions, SIGNUM Newsletter, 18, 19-24, (1983)
[60] Automatic differentiation: Point and interval AD, in Encyclopedia of Optimization, P.M. Pardalos and C.A. Floudas, eds., Kluwer, Dordrecht, the Netherlands, 1999
[61] Ratschek, H.; Rokne, J., New Computer Methods for Global Optimization, (2007), John Wiley & Sons (Ellis Horwood Limited), New York (Chichester) · Zbl 0648.65049
[62] Automatische Ergebnisverifikation bei globalen Optimierungsproblemen, diss., Universität Karlsruhe, 1992
[63] Ringrose, T. J.; Forth, S. A., an efficient overloaded implementation of forward mode automatic differentiation in MATLAB, ACM Trans. Math. Softw., 32, 2, 195-222, (2005) · Zbl 1365.65053
[64] Kleine Fehlerschranken bei Matrixproblemen, Ph.D. thesis, Universität Karlsruhe, 1980
[65] Rump, S. M., fast and parallel interval arithmetic, BIT Numer. Math., 39, 3, 539-560, (1999) · Zbl 0942.65048
[66] INTLAB - INTerval LABoratory, in Developments in Reliable Computing, T. Csendes, ed., Kluwer Academic Publishers, Dordrecht, 1999, pp. 77–104. Available at
[67] Rump, S. M., rigorous and portable standard functions, BIT Numer. Math., 41, 3, 540-562, (2001) · Zbl 0994.65017
[68] Rump, S. M., verification methods: rigorous results using floating-point arithmetic, Acta Numer., 19, 287-449, (2010) · Zbl 1323.65046
[69] Rump, S. M., gleitkommaarithmetik auf dem prüfstand [wie werden verifiziert(e) numerische L”osungen berechnet?], Jahresber. Deutsch. Math.-Verein., 118, 3, 179-226, (2016) · Zbl 1372.65140
[70] Rump, S. M.; Jeannerod, C.-P., improved backward error bounds for LU and Cholesky factorizations, SIAM J. Matrix Anal. Appl., 35, 2, 684-698, (2014) · Zbl 1309.65031
[71] Rump, S. M.; Kashiwagi, M., implementation and improvements of affine arithmetic, Nonlinear Theory Appl., 2, 3, 1101-1119, (2014)
[72] Validated Numerics in Julia.
[73] Some experiments in machine learning using vector evaluated genetic algorithms (artificial intelligence, optimization, adaptation, pattern recognition), Ph.D. diss., Vanderbilt University, 1984
[74] Sekhar, C.; Özdamar, L.; Csendes, T.; Vinkó, T., efficient interval partitioning for constrained global optimization, J. Global Optim., 42, 369-384, (2008) · Zbl 1151.90047
[75] Tawaralani, M.; Sahinidis, N. V., Convexification and Global Optimization in Continuous and Mixed-Integer Nonlinear Programming, (2002), Springer Science+Business Media, Dordrecht
[76] Trefethen, L. N., the SIAM 100-dollar, 100-digit challenge, SIAM-NEWS, 35, 6, 2, (2002)
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.