Aspects of semidefinite programming
Subtitle: interior point algorithms and selected applications
By: by  Etienne de Klerk.
Series: Applied optimization -- v. 65
Publisher: Kluwer Academic Publishers
Published: 2002
Place of publication: Dordrecht; Boston
Language: eng
Number of pages: 283
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.
Notes: Includes bibliographical references and index.
Table of contents: title: Machine generated contents note: 1. INTRODUCTION; title: 1.1 Problem statement; title: 1.2 The importance of semidefinite programming; title: 1.3 Special cases of semidefinite programming; title: 1.4 Applications in combinatorial optimization; title: 1.5 Applications in approximation theory; title: 1.6 Engineering applications; title: 1.7 Interior point methods; title: 1.8 Other algorithms for SDP; title: 1.9 The complexity of SDP; title: 1.10 Review literature and internet resources; title: Part I Theory and Algorithms; title: 2. DUALITY, OPTIMALITY, AND DEGENERACY; title: 2.1 Problems in standard form; title: 2.2 Weak and strong duality; title: 2.3 Feasibility issues; title: 2.4 Optimality and complementarity; title: 2.5 Degeneracy; title: 3. THE CENTRAL PATH; title: 3.1 Existence and uniqueness of the central path; title: 3.2 Analyticity of the central path; title: 3.3 Limit points of the central path; title: 3.4 Convergence in the case of strict complementarity; title: 3.5 Convergence proof in the absence of strict complementarity; title: 3.6 Convergence rate of the central path; title: 4. SELF-DUAL EMBEDDINGS; title: 4.1 Introduction; title: 4.2 The embedding strategy; title: 4.3 Solving the embedding problem; title: 4.4 Interpreting the solution of the embedding problem; title: 4.5 Separating small and large variables; title: 4.6 Remaining duality and feasibility issues; title: 5. THE PRIMAL LOGARITHMIC BARRIER METHOD; title: 5.1 Introduction; title: 5.2 A centrality function; title: 5.3 The projected Newton direction for the primal barrier functioi; title: 5.4 The affine-scaling direction; title: 5.5 Behaviour near the central path; title: 5.6 Updating the centering parameter; title: 5.7 Complexity analysis; title: 5.8 The dual algorithm; title: 5.9 Large update methods; title: 5.10 The dual method and combinatorial relaxations; title: 6. PRIMAL-DUAL AFFINE-SCALING METHODS; title: 6.1 Introduction; title: 6.2 The Nesterov-Todd (NT) scaling; title: 6.3 The primal-dual affine-scaling and Dikin-type methods; title: 6.4 Functions of centrality; title: 6.5 Feasibility of the Dikin-type step; title: 6.6 Complexity analysis for the Dikin-type method; title: 6.7 Analysis of the primal-dual affine-scaling method; title: 7. PRIMAL-DUAL PATH-FOLLOWING METHODS; title: 7.1 The path-following approach; title: 7.2 Feasibility of the full NT step; title: 7.3 Quadratic convergence to the central path; title: 7.4 Updating the barrier parameter p; title: 7.5 A long step path-following method; title: 7.6 Predictor-corrector methods; title: 8. PRIMAL-DUAL POTENTIAL REDUCTION METHODS; title: 8.1 Introduction; title: 8.2 Determining step lengths via plane searches of the potential; title: 8.3 The centrality function I; title: 8.4 Complexity analysis in a potential reduction framework; title: 8.5 A bound on the potential reduction; title: 8.6 The potential reduction method of Nesterov and Todd; title: Part II Selected Applications; title: 9. CONVEX QUADRATIC APPROXIMATION; title: 9.1 Preliminaries; title: 9.2 Quadratic approximation in the univariate case; title: 9.3 Quadratic approximation for the multivariate case; title: 10. THE LOVASZ 0-FUNCTION; title: 10.1 Introduction; title: 10.2 The sandwich theorem; title: 10.3 Other formulations of the 0-function; title: 10.4 The Shannon capacity of a graph; title: 11. GRAPH COLOURING AND THE MAX-K-CUT PROBLEM; title: 11.1 Introduction; title: 11.2 The 0-approximation of the chromatic number; title: 11.3 An upper bound for the optimal value of MAX-k-CUT; title: 11.4 Approximation guarantees; title: 11.5 A randomized MAX-k-CUT algorithm; title: 11.6 Analysis of the algorithm; title: 11.7 Approximation results for MAX-k-CUT; title: 11.8 Approximate colouring of n-colourable graphs; title: 12. THE STABILITY NUMBER OF A GRAPH; title: 12.1 Preliminaries; title: 12.2 The stability number via copositive programming; title: 12.3 Approximations of the copositive cone; title: 12.4 Application to the maximum stable set problem; title: 12.5 The strength of low-order approximations; title: 12.6 Related literature; title: 12.7 Extensions: standard quadratic optimization; title: 13. THE SATISFIABILITY PROBLEM; title: 13.1 Introduction; title: 13.2 Boolean quadratic representations of clauses; title: 13.3 From Boolean quadratic inequality to SDP; title: 13.4 Detecting unsatisfiability of some classes of formulae; title: 13.5 Rounding procedures; title: 13.6 Approximation guarantees for the rounding schemes; title: Appendices; title: A- Properties of positive (semi)definite matrices; title: A.1 Characterizations of positive (semi)definiteness; title: A.2 Spectral properties; title: A.3 The trace operator and the Frobenius norm; title: A.3 The trace operator and the Frobenius norm; title: A.4 The Lowner partial order and the Schur complement theorem; title: B- Background material on convex optimization; title: B.1 Convex analysis; title: B.2 Duality in convex optimization; title: B.3 The KKT optimality conditions; title: C- The function log det(X); title: D- Real analytic functions; title: E- The (symmetric) Kronecker product; title: E.1 The Kronecker product; title: E.2 The symmetric Kronecker product; title: F- Search directions for the embedding problem; title: G- Regularized duals; title: References; title: Index.