In this interesting monograph, the authors consider deterministic methods “for finding constrained global solutions to nonlinear optimization problems.” The methods include “enumerative techniques, cutting planes, branch-and-bound, bilinear programming, general approximation algorithms, and large-scale approaches.” The application of the methods, however, is restricted to the simplest of nonconvex programming problems: finding the global minimum of a concave or indefinite quadratic function over a convex set (usually a polyhedron). Thus, the solution is always at an extreme point when the function is concave or at a boundary when the function is an indefinite quadratic.
Chapter 1 summarizes some essential properties of functions and convex sets, while Chapter 2 reviews the familiar Kuhn-Tucker conditions, which are sufficient for global optimality in convex programming (minimizing a convex function over a convex set) but are not sufficient for even local optimality when the function is nonconvex.
In Chapter 3, the authors show how some types of combinatorial optimization problems can be transformed into nonconvex quadratic global minimization problems. Although the authors characterize the combinational optimization problems as difficult, it is not altogether clear if the problems would be easier to solve in their quadratic form.
Chapter 4 reviews enumerative techniques, including an algorithm that uses linear underestimating functions and extreme point ranking to bound and solve the concave quadratic global minimization problem.
Chapter 5 reviews cutting plane methods, most of which are variants of Tuy’s cone-splitting algorithm. Branch-and-bound and bilinear programming methods are reviewed in chapters 6 and 7.
In chapter 8, the authors propose their own algorithm for solving large-scale concave quadratic global minimization problems where some of the variables do not appear in the quadratic term. The algorithm combines eigenanalysis, linear and piecewise linear approximation, and zero-one mixed integer programming. They propose a similar algorithm in chapter 9 for the indefinite quadratic global minimization problem.
Chapter 10 concludes the monograph with some schemes for generating numerical problems to test these algorithms.
There are exercises and an extensive list of references at the end of each chapter as well as a general reference list after the last chapter.
This monograph clearly presents a wide collection of algorithms for finding the global minimum of concave or indefinite quadratic functions over convex sets. It should prove valuable to researchers in global optimization and, perhaps, as a supplementary text in a graduate course in nonlinear programming.