You are here

Handbook on Semidefinite, Conic and Polynomial Optimization

Miguel F. Anjos and Jean B. Lassere, editors
Publication Date: 
Number of Pages: 
International Series in Operations Research and Management Science
[Reviewed by
Brian Borchers
, on

In conic optimization problems, we minimize or maximize a linear function subject to linear equality constraints with an additional constraint that the solution lies in a particular closed convex cone. For example, linear programming problems can be formulated as minimization of a linear function subject to linear equality constraints and the constraint that the solution lies in the nonnegative orthant. An important generalization of linear programming that has received much attention over the last 20 years is semidefinite programming. In semidefinite programming (SDP), the optimization is over the cone of symmetric and positive semidefinite matrices rather than nonnegative vectors. Although a few researchers had studied SDP earlier, interest in the subject grew after it became apparent in the early 1990s that polynomial time interior point methods for linear programming could be extended to polynomial time algorithms for SDP. These methods made practical the solution of small and medium sized SDP problems with up to a few thousand constraints. The development of methods for very large scale problems is an important topic of current research in SDP.

The semidefiniteness constraint in SDP was quite natural in many applications in control systems and statistics where positive semidefinite matrices frequently arise. Semidefinite programming also found early application in the approximate solution of NP-Hard combinatorial optimization problems. For example, an improved randomized approximation algorithm for the MAX-SAT problem based on SDP was published by Goemans and Williamson in 1994. A more surprising development was the discovery that semidefinite programming can be extremely useful in solving optimization problems involving polynomial objective functions subject to polynomial inequality and equality constraints. One of the editors, Jean Lasserre, has been a leader in the study of SDP relaxations of these polynomial optimization problems.

This volume is a collection of self contained survey papers on various aspects of semidefinite programming and polynomial optimization. The volume is divided into four sections, covering the theory of conic and polynomial optimization, algorithms, software implementations, and applications of semidefinite and polynomial optimization.

The theory section contains several interesting papers on aspects of the semidefinite programming approach to polynomial optimization. The section on algorithms includes a survey on self regular interior point methods for SDP. Surprisingly, the volume does not include a discussion of augmented Lagrangian methods for SDP. These methods have received a lot of attention in recent years. The section on software includes a list of available software packages with brief descriptions as well as descriptions of three of the more popular solvers. The sections on software and applications provide the reader with a good sense what is possible using the current generation of software tools. However, progress in this area is extremely rapid, and some of this material will be outdated within a few years. Overall, the coverage of topics is quite broad, but certainly not comprehensive.

This is an advanced book and particularly in the theory section, many papers will only be accessible to readers who are already familiar with optimization, semidefinite programming, and interior point methods. The papers in this volume will be of interest to advanced graduate students and researchers working in conic optimization, SDP, and polynomial optimization. Most readers are likely to find individual chapters as the result of more narrowly focused web searches. The high cost of the printed volume means that few researchers will want to purchase it for themselves. Rather, this is a resource that should be made available, preferably in electronic form, by institutional libraries.

Brian Borchers is a professor of Mathematics at the New Mexico Institute of Mining and Technology. His interests are in optimization and applications of optimization in parameter estimation and inverse problems.