Aspects of Semidefinite Programming (eBook)

Interior Point Algorithms and Selected Applications

E. de Klerk (Autor)

eBook Download: PDF

2006 | 1. Auflage
304 Seiten
Springer US (Verlag)
978-0-306-47819-2 (ISBN)

Infos

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.  

---

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 "e;classic"e; 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. Audience: Researchers or graduate students in optimization or related fields, who wish to learn more about the theory and applications of semidefinite programming.

Inhalt

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

Textauszug

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.

Produkt-Details

• Erscheint lt. Verlag: 18.4.2006
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Software Entwicklung
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Technik
• ISBN-10: 0-306-47819-6 / 0306478196
• ISBN-13: 978-0-306-47819-2 / 9780306478192