Mathematically rigorous global optimization in floating-point arithmetic

Abstract

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.

Keywords:

• Algorithmic Differentiation
• global optimization
• constrained optimization
• rigorous error bounds
• verification methods
• Matlab
• octave
• INTLAB

AMS Subject Classification:

• 65G20
• 65H20
• 65K05

Acknowledgments

The author is indebted to two anonymous referees and to Andreas Griewank for their thorough reading. Their very many constructive suggestions contributed significantly to the readability of the paper. Moreover, I would like to thank Florian Bünger, Christian Jansson, Marko Lange and Kai Torben Ohlhus for their fruitful comments, and many thanks to Kai Torben Ohlhus and Marcel Neumann for performing some tests. This research was partially supported by CREST, Japan Science and Technology Agency (JST).

Disclosure statement

No potential conflict of interest was reported by the author.

ORCID

Siegfried M. Rump  http://orcid.org/0000-0002-4779-4800