Rigorous global search: continuous problems. (English) Zbl 0876.90082

Kearfott, R. Baker

Nonconvex Optimization and Its Applications. 13. Dordrecht: Kluwer Academic Publishers. xv, 262 p. (1996).

The monograph gives a survey of interval arithmetic based methods for solving systems of equations and global optimization problems. The connection between these two themes is that zero finding is an almost unavoidable part of optimization. The interval arithmetic philosophy of selfvalidation is followed in the book as indicated by the term “rigorous” in the title. That means that for each of the two problems all solutions are to be found and enclosed in sufficiently small boxes. In addition the solutions ought to be unique in these boxes. – The book contains standard results, new results and ones that need further development. Algorithmic and practical tools are emphasized, theoretical considerations are sporadically present. Many extensive remarks and explanations are connected with INTLIB, INTLIB 90 and INTOPT 90 which are the authors’s software and library packages for interval arithmetic and the solvers for the above mentioned problems in FORTRAN 77 resp. FORTRAN 90.
The book consists of seven chapters and a bibliography of 247 items. The first chapter (69 pages) introduces interval arithmetic, solving linear interval equations, automatic differentiation and code list generation, interval Newton method, and a short glance at the topological degree idea, which seems a bit outside the interval scope of the book. A groad chapter (42 pages) about interval software follows. Described are primarily the packages mentioned before which allow, among others, the generation of code lists and automatic differentiation. The chapter on preconditioning (32 pages) contains some of the authors own results and it provides techniques to transform linear interval equations into ones which might have tighter solution intervals. The chapter about solving nonlinear systems of equations (23 pages) features a rather practical and numerical approach in a branch and bound pattern touching many software details. The chapter on global optimization (40 pages) only admits equality constraints (within a box frame). The solution procedures are based on branch and bound, infeasibility test, interval Newton algorithm applied to the John conditions and computationally executed proofs of the existence of feasible points generalizing Hansen and Walster’s pioneering concept of 1987 (Nonlinear equations and optimization. Preprint.). The chapter about non-differentiable problems (17 pages) studies function expressions containing if-then-else connectives obtaining some new results with respect to zero search. The final chapter about intermediate values (8 pages) remains on the very surface of such a topic and contains only introductory examples of how these values can be used to reduce the overestimation.

Reviewer: H.Ratschek (Düsseldorf)

MSC:

90C30	Nonlinear programming
65G30	Interval and finite arithmetic
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
65H20	Global methods, including homotopy approaches to the numerical solution of nonlinear equations
65K05	Numerical mathematical programming methods
65-02	Research exposition (monographs, survey articles) pertaining to numerical analysis

Keywords:

interval arithmetic based methods; systems of equations; global optimization; automatic differentiation; interval Newton method; preconditioning

Software:

INTOPT_90; INTLIB