Aspects of Semidefinite Programming
Interior Point Algorithms and Selected Applications
1st Edition
Published on 18. April 2006
XVI, 288 pages
978-0-306-47819-2 (ISBN)
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.
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.
More details
Other editions
Additional editions
Book
03/2002
Kluwer Academic Publishers
€160.49
Shipment within 15-20 days
Content
Theory and Algorithms.- Duality, Optimality, and Degeneracy.- The Central Path.- Self-Dual Embeddings.- The Primal Logarithmic Barrier Method.- Primal-Dual Affine-Scaling Methods.- Primal-Dual Path-Following Methods.- Primal-Dual Potential Reduction Methods.- Selected Applications.- Convex Quadratic Approximation.- The Lovász ?-Function.- Graph Coulouring and the Max-K-Cut Problem.- The Stability Number of a Graph and Standard Quadratic Optimization.- The Satisfiability Problem.
2 DUALITY, OPTIMALITY, AND DEGENERACY (p.21-22)
Preamble All convex optimization problems can in principle be restated as so-called conic linear programs (conic LP's for short); these are problems where the objective function is linear, and the feasible set is the intersection of an affine space with a convex cone. For conic LP's, all nonlinearity is therefore hidden in the definition of the convex cone. Conic LP's also have the strong duality property under a constraint qualification: if the affine space intersects the relative interior of the cone, it has a solvable dual with the same optimal value (if the dual problem is feasible).
A special subclass of conic LP's is formed if we consider cones which are selfdual. There are three such cones over the reals: the positive orthant in the Lorentz (or ice-cream or second order) cone, and the positive semidefinite cone. These cones respectively define the conic formulation of linear programming (LP) problems, second order cone (SOC) programming problems, and semidefinite programming (SDP) problems. The self-duality of these cones ensures a perfect symmetry between primal and dual problems, i.e. the primal and dual problem can be cast in exactly the same form. As discussed in Chapter 1, LP and SCO problems may be viewed as special cases of SDP.
Some fundamental theoretical properties of semidefinite programs (SDP's) will be reviewed in this chapter. We define the standard form for SDP's and derive the associated dual problem. The classical weak and strong duality theorems are proved to obtain necessary and sufficient optimality conditions for the standard form SDP. Subsequently we review the concepts of degeneracy and maximal complementarity of optimal solutions.
Preamble All convex optimization problems can in principle be restated as so-called conic linear programs (conic LP's for short); these are problems where the objective function is linear, and the feasible set is the intersection of an affine space with a convex cone. For conic LP's, all nonlinearity is therefore hidden in the definition of the convex cone. Conic LP's also have the strong duality property under a constraint qualification: if the affine space intersects the relative interior of the cone, it has a solvable dual with the same optimal value (if the dual problem is feasible).
A special subclass of conic LP's is formed if we consider cones which are selfdual. There are three such cones over the reals: the positive orthant in the Lorentz (or ice-cream or second order) cone, and the positive semidefinite cone. These cones respectively define the conic formulation of linear programming (LP) problems, second order cone (SOC) programming problems, and semidefinite programming (SDP) problems. The self-duality of these cones ensures a perfect symmetry between primal and dual problems, i.e. the primal and dual problem can be cast in exactly the same form. As discussed in Chapter 1, LP and SCO problems may be viewed as special cases of SDP.
Some fundamental theoretical properties of semidefinite programs (SDP's) will be reviewed in this chapter. We define the standard form for SDP's and derive the associated dual problem. The classical weak and strong duality theorems are proved to obtain necessary and sufficient optimality conditions for the standard form SDP. Subsequently we review the concepts of degeneracy and maximal complementarity of optimal solutions.
