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