Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications (Applied Optimization) [Hardcover]

E. de Klerk (Author)

Book Description

Series: Applied Optimization | Publication Date: March 31, 2002

Semidefinite programming has been described as linear programming for the year 2000. It is an exciting new branch of mathematical programming, due to important applications in control theory, combinatorial optimization and other fields. Moreover, the successful interior point algorithms for linear programming can be extended to semidefinite programming. In this monograph the basic theory of interior point algorithms is explained. This includes the latest results on the properties of the central path as well as the analysis of the most important classes of algorithms. Several "classic" applications of semidefinite programming are also described in detail. These include the Lovász theta function and the MAX-CUT approximation algorithm by Goemans and Williamson. Audience: Researchers or graduate students in optimization or related fields, who wish to learn more about the theory and applications of semidefinite programming.

Product Details

• Hardcover: 300 pages
• Publisher: Springer; 1 edition (March 31, 2002)
• Language: English
• ISBN-10: 1402005474
• ISBN-13: 978-1402005473
• Product Dimensions: 9.3 x 6.8 x 0.9 inches
• Shipping Weight: 1.3 pounds (View shipping rates and policies)
• Average Customer Review: 5.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #3,254,973 in Books (See Top 100 in Books)

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

2 of 2 people found the following review helpful:

5.0 out of 5 stars An excellent introduction to the various facets of SDP, November 6, 2003

By 

KARTIK KRISHNAN S. - See all my reviews

This review is from: Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications (Applied Optimization) (Hardcover)

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!.