Aspects of Semidefinite Programming: Interior Point Algorithms...

Features

• Cover Type: Hard Cover with 300 pages
• Published by: Springer
• Edition: 1st Edition March 31, 2002
• Written in: English
• ISBN 10 Number: 1402005474
• ISBN 13 Number: 978-1402005473
• Book Dimensions: 9.3 x 6.8 x 0.9 inches
• Weighs: 1.3 pounds

Book Description
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.

Book Info
In this monograph the basic theory of interior point algorithms is explained. For researchers or graduate students in optimization or related fields, who wish to learn about the theory and applications of semidefinite programming.

Reader Reviews
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!. Comment | | (Report this)