Convex Optimization

Stephen Boyd Department of Electrical Engineering Stanford University Lieven Vandenberghe Electrical Engineering Department University of California, Los Angeles

Contents

Preface xi 1 Introduction 1 1.1 Mathematical optimization . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Least-squares and linear programming . . . . . . . . . . . . . . . . . . 4 1.3 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.4 Nonlinear optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 I Theory 19 2 Convex sets 21 2.1 A±ne and convex sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2.2 Some important examples . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.3 Operations that preserve convexity . . . . . . . . . . . . . . . . . . . . 35 2.4 Generalized inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5 Separating and supporting hyperplanes . . . . . . . . . . . . . . . . . . 46 2.6 Dual cones and generalized inequalities . . . . . . . . . . . . . . . . . . 51 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3 Convex functions 67 3.1 Basic properties and examples . . . . . . . . . . . . . . . . . . . . . . 67 3.2 Operations that preserve convexity . . . . . . . . . . . . . . . . . . . . 79 3.3 The conjugate function . . . . . . . . . . . . . . . . . . . . . . . . . . 90 3.4 Quasiconvex functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 3.5 Log-concave and log-convex functions . . . . . . . . . . . . . . . . . . 104 3.6 Convexity with respect to generalized inequalities . . . . . . . . . . . . 108 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

4 Convex optimization problems 127 4.1 Optimization problems . . . . . . . . . . . . . . . . . . . . . . . . . . 127 4.2 Convex optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 4.3 Linear optimization problems . . . . . . . . . . . . . . . . . . . . . . . 146 4.4 Quadratic optimization problems . . . . . . . . . . . . . . . . . . . . . 152 4.5 Geometric programming . . . . . . . . . . . . . . . . . . . . . . . . . . 160 4.6 Generalized inequality constraints . . . . . . . . . . . . . . . . . . . . . 167 4.7 Vector optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189 5 Duality 215 5.1 The Lagrange dual function . . . . . . . . . . . . . . . . . . . . . . . . 215 5.2 The Lagrange dual problem . . . . . . . . . . . . . . . . . . . . . . . . 223 5.3 Geometric interpretation . . . . . . . . . . . . . . . . . . . . . . . . . 232 5.4 Saddle-point interpretation . . . . . . . . . . . . . . . . . . . . . . . . 237 5.5 Optimality conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 5.6 Perturbation and sensitivity analysis . . . . . . . . . . . . . . . . . . . 249 5.7 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 5.8 Theorems of alternatives . . . . . . . . . . . . . . . . . . . . . . . . . 258 5.9 Generalized inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . 264 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 II Applications 289 6 Approximation and ¯tting 291 6.1 Norm approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 6.2 Least-norm problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 6.3 Regularized approximation . . . . . . . . . . . . . . . . . . . . . . . . 305 6.4 Robust approximation . . . . . . . . . . . . . . . . . . . . . . . . . . . 318 6.5 Function ¯tting and interpolation . . . . . . . . . . . . . . . . . . . . . 324 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 7 Statistical estimation 351 7.1 Parametric distribution estimation . . . . . . . . . . . . . . . . . . . . 351 7.2 Nonparametric distribution estimation . . . . . . . . . . . . . . . . . . 359 7.3 Optimal detector design and hypothesis testing . . . . . . . . . . . . . 364 7.4 Chebyshev and Cherno® bounds . . . . . . . . . . . . . . . . . . . . . 374 7.5 Experiment design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393

8 Geometric problems 397 8.1 Projection on a set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 8.2 Distance between sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 402 8.3 Euclidean distance and angle problems . . . . . . . . . . . . . . . . . . 405 8.4 Extremal volume ellipsoids . . . . . . . . . . . . . . . . . . . . . . . . 410 8.5 Centering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 8.6 Classi¯cation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422 8.7 Placement and location . . . . . . . . . . . . . . . . . . . . . . . . . . 432 8.8 Floor planning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 438 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 447 III Algorithms 455 9 Unconstrained minimization 457 9.1 Unconstrained minimization problems . . . . . . . . . . . . . . . . . . 457 9.2 Descent methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463 9.3 Gradient descent method . . . . . . . . . . . . . . . . . . . . . . . . . 466 9.4 Steepest descent method . . . . . . . . . . . . . . . . . . . . . . . . . 475 9.5 Newton's method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484 9.6 Self-concordance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 496 9.7 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514 10 Equality constrained minimization 521 10.1 Equality constrained minimization problems . . . . . . . . . . . . . . . 521 10.2 Newton's method with equality constraints . . . . . . . . . . . . . . . . 525 10.3 Infeasible start Newton method . . . . . . . . . . . . . . . . . . . . . . 531 10.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 11 Interior-point methods 561 11.1 Inequality constrained minimization problems . . . . . . . . . . . . . . 561 11.2 Logarithmic barrier function and central path . . . . . . . . . . . . . . 562 11.3 The barrier method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 11.4 Feasibility and phase I methods . . . . . . . . . . . . . . . . . . . . . . 579 11.5 Complexity analysis via self-concordance . . . . . . . . . . . . . . . . . 585 11.6 Problems with generalized inequalities . . . . . . . . . . . . . . . . . . 596 11.7 Primal-dual interior-point methods . . . . . . . . . . . . . . . . . . . . 609 11.8 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 615 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 623

Appendices 631 A Mathematical background 633 A.1 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633 A.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637 A.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639 A.4 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 A.5 Linear algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 652 B Problems involving two quadratic functions 653 B.1 Single constraint quadratic optimization . . . . . . . . . . . . . . . . . 653 B.2 The S-procedure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 B.3 The ¯eld of values of two symmetric matrices . . . . . . . . . . . . . . 656 B.4 Proofs of the strong duality results . . . . . . . . . . . . . . . . . . . . 657 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 659 C Numerical linear algebra background 661 C.1 Matrix structure and algorithm complexity . . . . . . . . . . . . . . . . 661 C.2 Solving linear equations with factored matrices . . . . . . . . . . . . . . 664 C.3 LU, Cholesky, and LDLT factorization . . . . . . . . . . . . . . . . . . 668 C.4 Block elimination and Schur complements . . . . . . . . . . . . . . . . 672 C.5 Solving underdetermined linear equations . . . . . . . . . . . . . . . . . 681 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 684 References 685 Notation 697 Index 701