Interval computations, rigour and non-rigour in deterministic continuous global optimization

Abstract

Deterministic branch and bound methods for the solution of general nonlinear programs have become increasingly popular during the last decade or two, with increasing computer speed, algorithmic improvements, and multiprocessors. Presently, there are several commercial packages. Although such packages are based on exhaustive search, not all of them rigorously take account of roundoff error, singularities, and other possibilities. Popular non-rigorous packages have much in common with mathematically rigorous packages, including overall structure and basic techniques. Nonetheless, it is not trivial to make non-rigorous packages rigorous. We

1. define different kinds of answers that global optimization software can claim to provide,

2. explain where rigour might be needed and where it is not practical,

3. briefly review salient techniques common to deterministic branch and bound methods,

4. illustrate pitfalls in non-rigorous branch and bound methods,

5. outline some of the techniques to make non-rigorous software rigorous, and provide guidance for research into and implementation of these techniques,

6. provide some theoretical backing, with examples, for convergence of common relaxation techniques.

Keywords:

• deterministic global optimization
• mathematical rigour
• relaxations
• branch and bound
• interval computations

Acknowledgement

I wish to thank the referees for careful reading and comments on the manuscript that led to both significant clarification of the paper and avoidance of embarrassing errors.

Notes

In fact, certain diseases, such as mad cow disease, are linked to molecular conformations corresponding to potential energy minimizers other than the usual one. Furthermore, in actual populations of molecules, various conformations corresponding to various local minima have been observed.

This is borne out in experiments. One reason is that the search may stop once tight bounds on the optimum are known, whereas the search must subdivide the entire region if bounds on all optimizers are needed.

That is, for a convex program.

For example, with operator overloading, as opposed to the development of a special parsing program.

Professor Floudas has presented this composition explicitly in talks such as 12.

Signomial terms are terms of the form , where α _i are the arbitrary real numbers.

Or, alternatively, Fritz John.