de Klerk Aspects of Semidefinite Programming

Interior Point Algorithms and Selected Applications
1. Auflage 2006
ISBN: 978-0-306-47819-2
Verlag: Springer US
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 65, 304 Seiten

Reihe: Applied Optimization

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 Lovasz theta function and the MAX-CUT approximation algorithm by Goemans and Williamson. It is aimed at researchers or graduate students in optimization or related fields, who wish to learn more about the theory and applications of semidefinite programming.

Autoren/Hrsg.

de Klerk, E.

Inhaltsverzeichnis

1;Contents;6
2;Acknowledgments;10
3;Foreword;12
4;List of Notation;14
5;1 INTRODUCTION;18
5.1;1.1 PROBLEM STATEMENT;18
5.2;1.2 THE IMPORTANCE OF SEMIDEFINITE PROGRAMMING;20
5.3;1.3 SPECIAL CASES OF SEMIDEFINITE PROGRAMMING;20
5.4;1.4 APPLICATIONS IN COMBINATORIAL OPTIMIZATION;21
5.5;1.5 APPLICATIONS IN APPROXIMATION THEORY;25
5.6;1.6 ENGINEERING APPLICATIONS;27
5.7;1.7 INTERIOR POINT METHODS;28
5.8;1.8 OTHER ALGORITHMS FOR SDP;33
5.9;1.9 THE COMPLEXITY OF SDP;34
5.10;1.10 REVIEW LITERATURE AND INTERNET RESOURCES;35
6;I THEORY AND ALGORITHMS;37
6.1;2 DUALITY, OPTIMALITY, AND DEGENERACY;38
6.1.1;2.1 PROBLEMS IN STANDARD FORM;39
6.1.2;2.2 WEAK AND STRONG DUALITY;42
6.1.3;2.3 FEASIBILITY ISSUES;46
6.1.4;2.4 OPTIMALITY AND COMPLEMENTARITY;49
6.1.5;2.5 DEGENERACY;53
6.2;3 THE CENTRAL PATH;58
6.2.1;3.1 EXISTENCE AND UNIQUENESS OF THE CENTRAL PATH;58
6.2.2;3.2 ANALYTICITY OF THE CENTRAL PATH;63
6.2.3;3.3 LIMIT POINTS OF THE CENTRAL PATH;65
6.2.4;3.4 CONVERGENCE IN THE CASE OF STRICT COMPLEMENTARITY;68
6.2.5;3.5 CONVERGENCE PROOF IN THE ABSENCE OF STRICT COMPLEMENTARITY;73
6.2.6;3.6 CONVERGENCE RATE OF THE CENTRAL PATH;75
6.3;4 SELF-DUAL EMBEDDINGS;78
6.3.1;4.1 INTRODUCTION;78
6.3.2;4.2 THE EMBEDDING STRATEGY;81
6.3.3;4.3 SOLVING THE EMBEDDING PROBLEM;84
6.3.4;4.4 INTERPRETING THE SOLUTION OF THE EMBEDDING PROBLEM;85
6.3.5;4.5 SEPARATING SMALL AND LARGE VARIABLES;87
6.3.6;4.6 REMAINING DUALITY AND FEASIBILITY ISSUES;89
6.4;5 THE PRIMAL LOGARITHMIC BARRIER METHOD;92
6.4.1;5.1 INTRODUCTION;92
6.4.2;5.2 A CENTRALITY FUNCTION;94
6.4.3;5.3 THE PROJECTED NEWTON DIRECTION FOR THE PRIMAL BARRIER FUNCTION;95
6.4.4;5.4 THE AFFINE–SCALING DIRECTION;98
6.4.5;5.5 BEHAVIOUR NEAR THE CENTRAL PATH;100
6.4.6;5.6 UPDATING THE CENTERING PARAMETER;102
6.4.7;5.7 COMPLEXITY ANALYSIS;104
6.4.8;5.8 THE DUAL ALGORITHM;106
6.4.9;5.9 LARGE UPDATE METHODS;107
6.4.10;5.10 THE DUAL METHOD AND COMBINATORIAL RELAXATIONS;110
6.5;6 PRIMAL-DUAL AFFINE–SCALING METHODS;112
6.5.1;6.1 INTRODUCTION;112
6.5.2;6.2 THE NESTEROV–TODD (NT) SCALING;114
6.5.3;6.3 THE PRIMAL–DUAL AFFINE–SCALING AND DIKIN–TYPE METHODS;116
6.5.4;6.4 FUNCTIONS OF CENTRALITY;119
6.5.5;6.5 FEASIBILITY OF THE DIKIN-TYPE STEP;121
6.5.6;6.6 COMPLEXITY ANALYSIS FOR THE DIKIN-TYPE METHOD;124
6.5.7;6.7 ANALYSIS OF THE PRIMAL–DUAL AFFINE–SCALING METHOD;126
6.6;7 PRIMAL–DUAL PATH–FOLLOWING METHODS;132
6.6.1;7.1 THE PATH–FOLLOWING APPROACH;132
6.6.2;7.2 FEASIBILITY OF THE FULL NT STEP;135
6.6.3;7.3 QUADRATIC CONVERGENCE TO THE CENTRAL PATH;137
6.6.4;7.4 UPDATING THE BARRIER PARAMETER;140
6.6.5;7.5 A LONG STEP PATH–FOLLOWING METHOD;141
6.6.6;7.6 PREDICTOR–CORRECTOR METHODS;142
6.7;8 PRIMAL–DUAL POTENTIAL REDUCTION METHODS;150
6.7.1;8.1 INTRODUCTION;151
6.7.2;8.2 DETERMINING STEP LENGTHS VIA PLANE SEARCHES OF THE POTENTIAL;152
6.7.3;8.3 THE CENTRALITY FUNCTION;153
6.7.4;8.4 COMPLEXITY ANALYSIS IN A POTENTIAL REDUCTION FRAMEWORK;154
6.7.5;8.5 A BOUND ON THE POTENTIAL REDUCTION;156
6.7.6;8.6 THE POTENTIAL REDUCTION METHOD OF NESTEROV AND TODD;159
7;II SELECTED APPLICATIONS;165
7.1;9 CONVEX QUADRATIC APPROXIMATION;166
7.1.1;9.1 PRELIMINARIES;166
7.1.2;9.2 QUADRATIC APPROXIMATION IN THE UNIVARIATE CASE;167
7.1.3;9.3 QUADRATIC APPROXIMATION FOR THE MULTIVARIATE CASE;169
7.2;10 THE LOVÁSZ v-FUNCTION;174
7.2.1;10.1 INTRODUCTION;174
7.2.2;10.2 THE SANDWICH THEOREM;175
7.2.3;10.3 OTHER FORMULATIONS OF THE v-FUNCTION;179
7.2.4;10.4 THE SHANNON CAPACITY OF A GRAPH;181
7.3;11 GRAPH COLOURING AND THE MAX-K-CUT PROBLEM;186
7.3.1;11.1 INTRODUCTION;188
7.3.2;11.2 THE OF v-APPROXIMATION THE CHROMATIC NUMBER;189
7.3.3;11.3 AIM UPPER BOUND FOR THE OPTIMAL VALUE OF MAX-K-CUT;189
7.3.4;11.4 APPROXIMATION GUARANTEES;191
7.3.5;11.5 A RANDOMIZED MAX- K-CUT ALGORITHM;192
7.3.6;11.6 ANALYSIS OF THE ALGORITHM;195
7.3.7;11.7 APPROXIMATION RESULTS FOR MAX-K-CUT;196
7.3.8;11.8 APPROXIMATE COLOURING OF k-COLORABLI GRAPHS;200
7.4;12 THE STABILITY NUMBER OF A GRAPH AND STANDARD QUADRATIC OPTIMIZATION;204
7.4.1;12.1 PRELIMINARIES;205
7.4.2;12.2 THE STABILITY NUMBER VIA COPOSITIVE PROGRAMMING;206
7.4.3;12.3 APPROXIMATIONS OF THE COPOSITIVE CONE;210
7.4.4;12.4 APPLICATION TO THE MAXIMUM STABLE SET PROBLEM;215
7.4.5;12.5 THE STRENGTH OF LOW-ORDER APPROXIMATIONS;218
7.4.6;12.6 RELATED LITERATURE;221
7.4.7;12.7 EXTENSIONS: STANDARD QUADRATIC OPTIMIZATION;221
7.5;13 THE SATISFIABILITY PROBLEM;228
7.5.1;13.1 INTRODUCTION;229
7.5.2;13.2 BOOLEAN QUADRATIC REPRESENTATIONS OF CLAUSES;231
7.5.3;13.3 FROM BOOLEAN QUADRATIC INEQUALITY TO SDP;232
7.5.4;13.4 DETECTING UNSATISFIABILITY OF SOME CLASSES OF FORMULAE;235
7.5.5;13.5 ROUNDING PROCEDURES;240
7.5.6;13.6 APPROXIMATION GUARANTEES FOR THE ROUNDING SCHEMES;241
8;Appendix;246
8.1;Appendix A Properties of positive (semi)definite matrices;246
8.1.1;A.1 CHARACTERIZATIONS OF POSITIVE (SEMI)DEFINITENESS;246
8.1.2;A.2 SPECTRAL PROPERTIES;247
8.1.3;A.3 THE TRACE OPERATOR AND THE FROBENIUS NORM;249
8.1.4;A.4 THE LÖWNER PARTIAL ORDER AND THE SCHUR COMPLEMENT THEOREM;252
8.2;Appendix B Background material on convex optimization;254
8.2.1;B.1 CONVEX ANALYSIS;254
8.2.2;B.2 DUALITY IN CONVEX OPTIMIZATION;257
8.2.3;B.3 THE KKT OPTIMALITY CONDITIONS;259
8.3;Appendix C The function log det(X);260
8.4;Appendix D Real analytic functions;264
8.5;Appendix E The (symmetric) Kronecker product;266
8.5.1;E.1 THE KRONECKER PRODUCT;266
8.5.2;E.2 THE SYMMETRIC KRONECKER PRODUCT;268
8.6;Appendix F Search directions for the embedding problem;274
8.7;Appendix G Regularized duals;278
9;References;282
10;Index;296
11;More eBooks at www.ciando.com;0

Leseproben

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.