convex optimization---Stephen Boyd，Lieven Vandenberghe

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 Affine 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 viii Contents 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 fitting 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 fitting 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 Chernoff bounds . . . . . . . . . . . . . . . . . . . . . 374 7.5 Experiment design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 392 Exercises . . . . . . . . . . . . . . . . . . . . . .