×

Constrained global optimization: algorithms and applications. (English) Zbl 0638.90064

Lecture Notes in Computer Science, 268. Berlin etc.: Springer-Verlag. VII, 143 p.; DM 27.00 (1987).
The book is divided into ten chapters. Chapter One, entitled Convex Sets and Functions, is devoted to mathematical preliminaries. Chapter Two has two main sections, one devoted to Kuhn-Tucker conditions, the other one to convex quadratic problems solvable in polynomial time. Algorithms based on Kuhn-Tucker conditions, and the approaches proposed by Shor, Khachiyan and Karmarkar are mentioned. Chapter Three deals with combinatorial optimization problems which can be formulated as nonconvex quadratic problems. The topics include linear and quadratic 0-1 programming, the quadratic and the 3-dimensional assignment problems, bilinear programming and the linear complementarity problems. Chapter Four “Enumerative methods in Nonconvex Programming”, deals in the global concave minimization by ranking the extreme points, with the construction of linear underestimating functions, presents an algorithm (proposed by Manas) for the indefinite quadratic problem and mentions an algorithm by Zangwill for the concave cost network problem. Chapter Five is devoted to the cutting plane methods and Chapter Six to Branch and Bound methods. Chapter Seven is devoted to bilinear programming for nonconvex (and convex) quadratic problems. Chapter Eight is devoted to large scale problems with linear constraints and a quadratic objective function. Chapters Nine and Ten deal with the methods and the test problems for global indefinite quadratic programming problems. Each chapter contains some exercises and a substantial list of references; in addition to that, a bibliography of references for constrained global optimization is presented at the end of the book (237 titles).
Reviewer: J.Abrham

MSC:

90C30 Nonlinear programming
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming
90C10 Integer programming
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C20 Quadratic programming
90C25 Convex programming
90C09 Boolean programming
90C35 Programming involving graphs or networks
90C27 Combinatorial optimization
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)