| Acknowledgments | p. ix |
| Foreword | p. xi |
| List of Notation | p. xiii |
| Introduction | p. 1 |
| Problem statement | p. 1 |
| The importance of semidefinite programming | p. 3 |
| Special cases of semidefinite programming | p. 3 |
| Applications in combinatorial optimization | p. 4 |
| Applications in approximation theory | p. 8 |
| Engineering applications | p. 10 |
| Interior point methods | p. 11 |
| Other algorithms for SDP | p. 16 |
| The complexity of SDP | p. 17 |
| Review literature and internet resources | p. 18 |
| Theory and Algorithms | |
| Duality, Optimality, and Degeneracy | p. 21 |
| Problems in standard form | p. 22 |
| Weak and strong duality | p. 25 |
| Feasibility issues | p. 29 |
| Optimality and complementarity | p. 32 |
| Degeneracy | p. 36 |
| The Central Path | p. 41 |
| Existence and uniqueness of the central path | p. 41 |
| Analyticity of the central path | p. 46 |
| Limit points of the central path | p. 48 |
| Convergence in the case of strict complementarity | p. 51 |
| Convergence proof in the absence of strict complementarity | p. 56 |
| Convergence rate of the central path | p. 58 |
| Self-Dual Embeddings | p. 61 |
| Introduction | p. 61 |
| The embedding strategy | p. 64 |
| Solving the embedding problem | p. 67 |
| Interpreting the solution of the embedding problem | p. 68 |
| Separating small and large variables | p. 70 |
| Remaining duality and feasibility issues | p. 72 |
| The Primal Logarithmic Barrier Method | p. 75 |
| Introduction | p. 75 |
| A centrality function | p. 77 |
| The projected Newton direction for the primal barrier function | p. 78 |
| The affine-scaling direction | p. 81 |
| Behaviour near the central path | p. 83 |
| Updating the centering parameter | p. 85 |
| Complexity analysis | p. 87 |
| The dual algorithm | p. 89 |
| Large update methods | p. 90 |
| The dual method and combinatorial relaxations | p. 93 |
| Primal-Dual Affine-Scaling Methods | p. 95 |
| Introduction | p. 95 |
| The Nesterov-Todd (NT) scaling | p. 97 |
| The primal-dual affine-scaling and Dikin-type methods | p. 99 |
| Functions of centrality | p. 102 |
| Feasibility of the Dikin-type step | p. 104 |
| Complexity analysis for the Dikin-type method | p. 107 |
| Analysis of the primal-dual affine-scaling method | p. 109 |
| Primal-Dual Path-Following Methods | p. 115 |
| The path-following approach | p. 115 |
| Feasibility of the full NT step | p. 118 |
| Quadratic convergence to the central path | p. 120 |
| Updating the barrier parameter [mu] | p. 123 |
| A long step path-following method | p. 124 |
| Predictor-corrector methods | p. 125 |
| Primal-Dual Potential Reduction Methods | p. 133 |
| Introduction | p. 134 |
| Determining step lengths via plane searches of the potential | p. 135 |
| The centrality function [psi] | p. 136 |
| Complexity analysis in a potential reduction framework | p. 137 |
| A bound on the potential reduction | p. 139 |
| The potential reduction method of Nesterov and Todd | p. 142 |
| Selected Applications | |
| Convex Quadratic Approximation | p. 149 |
| Preliminaries | p. 149 |
| Quadratic approximation in the univariate case | p. 150 |
| Quadratic approximation for the multivariate case | p. 152 |
| The Lovasz [curly or open theta]-Function | p. 157 |
| Introduction | p. 157 |
| The sandwich theorem | p. 158 |
| Other formulations of the [curly or open theta]-function | p. 162 |
| The Shannon capacity of a graph | p. 164 |
| Graph Colouring and the MAX-[kappa]-CUT Problem | p. 169 |
| Introduction | p. 171 |
| The [curly or open theta]-approximation of the chromatic number | p. 172 |
| An upper bound for the optimal value of MAX-[kappa]-CUT | p. 172 |
| Approximation guarantees | p. 174 |
| A randomized MAX-[kappa]-CUT algorithm | p. 175 |
| Analysis of the algorithm | p. 178 |
| Approximation results for MAX-[kappa]-CUT | p. 179 |
| Approximate colouring of [kappa]-colourable graphs | p. 183 |
| The Stability Number of a Graph | p. 187 |
| Preliminaries | p. 188 |
| The stability number via copositive programming | p. 189 |
| Approximations of the copositive cone | p. 193 |
| Application to the maximum stable set problem | p. 198 |
| The strength of low-order approximations | p. 201 |
| Related literature | p. 204 |
| Extensions: standard quadratic optimization | p. 204 |
| The Satisfiability Problem | p. 211 |
| Introduction | p. 212 |
| Boolean quadratic representations of clauses | p. 214 |
| From Boolean quadratic inequality to SDP | p. 215 |
| Detecting unsatisfiability of some classes of formulae | p. 218 |
| Rounding procedures | p. 223 |
| Approximation guarantees for the rounding schemes | p. 224 |
| Appendices | p. 229 |
| Properties of positive (semi)definite matrices | p. 229 |
| Characterizations of positive (semi)definiteness | p. 229 |
| Spectral properties | p. 230 |
| The trace operator and the Frobenius norm | p. 232 |
| The Lowner partial order and the Schur complement theorem | p. 235 |
| Background material on convex optimization | p. 237 |
| Convex analysis | p. 237 |
| Duality in convex optimization | p. 240 |
| The KKT optimality conditions | p. 242 |
| The function log det(X) | p. 243 |
| Real analytic functions | p. 247 |
| The (symmetric) Kronecker product | p. 249 |
| The Kronecker product | p. 249 |
| The symmetric Kronecker product | p. 251 |
| Search directions for the embedding problem | p. 257 |
| Regularized duals | p. 261 |
| References | p. 265 |
| Index | p. 279 |
| Table of Contents provided by Ingram. All Rights Reserved. |
