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.