Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications (Applied Optimization, 65)

Rating:
Summary: An excellent introduction to the various facets of SDP
Review: Semidefinite Programming (SDP), which the author remarks is linear programming for the 21st century, has lately been one of the most exciting and active areas of research in the mathematical programming community. This tremendous excitement was spurred in part by the development of efficient interior point methods (IPMs) for the solution of SDPs, and important applications of the SDP especially in combinatorial optimization. I believe Etienne De Klerk gives an excellent introduction to these two topics, in this short, but concise monograph published by Kluwer Academic Publishers.

Topics covered include theory (duality, degeneracy, complementarity, properties of central path), algorithms (primal and primal dual affine scaling, path following, potential reduction algorithms), and finally applications (approximating the stable set and coloring number of a graph, the satisfiability problem, and quadratic programming).

Most of the material presented is based on the personal research of the author with other colloborators, and reflect his personal taste, and various insights on the subject. The monograph is probably the first textbook exclusively devoted to the SDP, and can be used in a graduate course on the subject. Personally, I enjoyed it immensely!.