Convex Optimization

"Convex optimization problems arise frequently in many different fields. This book provides a comprehensive introduction to the subject, covering the theory, many applications and examples, and numerical methods. The book begins with the basic elements of convex sets and functions, describes various classes of convex optimization problems, and then treats duality theory. The second part covers a wide variety of applications, in estimation, approximation, statistics, computational geometry, and other areas. The last part of the book presents numerical methods for convex optimization problems, moving from basic methods for unconstrained problems to interior-point methods. The focus of the book is on recognizing and formulating convex optimization problems, and then solving them efficiently. It contains many worked examples and homework exercises and will appeal to students, researchers, and practitioners in fields such as engineering, computer science, mathematics, finance, and economics. Cover......Page 1 Convex Optimization......Page 2 Title......Page 4 ISBN 978-0-521-83378-3......Page 5 Dedications......Page 6 Contents......Page 8 Preface......Page 12 1.1 Mathematical optimization......Page 16 1.1.1 Applications......Page 17 1.1.2 Solving optimization problems......Page 18 1.2.1 Least-squares problems......Page 19 Using linear programming......Page 21 1.3.1 Solving convex optimization problems......Page 22 1.3.2 Using convex optimization......Page 23 1.4.1 Local optimization......Page 24 1.4.3 Role of convex optimization in nonconvex problems......Page 25 1.5.1 Part I: Theory......Page 26 1.5.3 Part III: Algorithms......Page 27 1.5.5 Comments on examples......Page 28 1.6 Notation......Page 29 Bibliography......Page 31 Part I: Theory......Page 34 2.1.2 Affine sets......Page 36 2.1.4 Convex sets......Page 38 2.1.5 Cones......Page 40 2.2.1 Hyperplanes and halfspaces......Page 42 2.2.2 Euclidean balls and ellipsoids......Page 44 2.2.3 Norm balls and norm cones......Page 45 2.2.4 Polyhedra......Page 46 2.2.5 The positive semidefinite cone......Page 49 2.3 Operations that preserve convexityIn......Page 50 2.3.2 Affine functions......Page 51 2.3.3 Linear-fractional and perspective functions......Page 54 Linear-fractional functions......Page 56 2.4.1 Proper cones and generalized inequalities......Page 58 2.4.2 Minimum and minimal elements......Page 60 2.5.1 Separating hyperplane theorem......Page 61 Strict separation......Page 64 2.5.2 Supporting hyperplanes......Page 65 2.6.1 Dual cones......Page 66 2.6.2 Dual generalized inequalities......Page 68 2.6.3 Minimum and minimal elements via dual inequalities......Page 69 Dual characterization of minimal elements......Page 70 Bibliography......Page 74 Exercises......Page 75 3.1.1 Definition......Page 82 3.1.2 Extended-value extensions......Page 83 3.1.3 First-order conditions......Page 84 3.1.5 Examples......Page 86 3.1.7 Epigraph......Page 90 3.1.8 Jensen’s inequality and extensions......Page 92 3.1.9 Inequalities......Page 93 3.2.2 Composition with an affine mapping......Page 94 3.2.3 Pointwise maximum and supremum......Page 95 3.2.4 Composition......Page 98 Scalar composition......Page 99 Vector composition......Page 101 3.2.5 Minimization......Page 102 3.2.6 Perspective of a function......Page 104 3.3 The conjugate function......Page 105 3.3.1 Definition and examples......Page 106 Conjugate of the conjugate......Page 109 3.4.1 Definition and examples......Page 110 3.4.2 Basic properties......Page 113 First-order conditions......Page 114 Nonnegative weighted maximum......Page 116 Minimization......Page 117 3.4.5 Representation via family of convex functions......Page 118 3.5.1 Definition......Page 119 Multiplication, addition, and integration......Page 120 Integration of log-concave functions......Page 121 3.6.1 Monotonicity with respect to a generalized inequality......Page 123 3.6.2 Convexity with respect to a generalized inequality......Page 124 Dual characterization of K-convexity......Page 125 Composition theorem......Page 126 Bibliography......Page 127 Exercises......Page 128 4.1.1 Basic terminology......Page 142 Feasibility problems......Page 143 Maximization problems......Page 144 Change of variables......Page 145 Slack variables......Page 146 Introducing equality constraints......Page 147 Optimizing over some variables......Page 148 Implicit and explicit constraints......Page 149 4.2.1 Convex optimization problems in standard form......Page 151 Abstract form convex optimization problem......Page 152 4.2.2 Local and global optima......Page 153 Proof of optimality condition......Page 154 Unconstrained problems......Page 155 Problems with equality constraints only......Page 156 Eliminating equality constraints......Page 157 Epigraph problem form......Page 158 Locally optimal solutions and optimality conditions......Page 159 Quasiconvex optimization via convex feasibility problems......Page 160 Standard and inequality form linear programs......Page 161 Converting LPs to standard form......Page 162 Chebyshev center of a polyhedron......Page 163 Dynamic activity planning......Page 164 Piecewise-linear minimization......Page 165 Transforming to a linear program......Page 166 4.4 Quadratic optimization problems......Page 167 4.4.1 Examples......Page 168 4.4.2 Second-order cone programming......Page 171 Linear programming with random constraints......Page 172 Minimal surface......Page 174 4.5.1 Monomials and posynomials......Page 175 Extensions of geometric programming......Page 176 4.5.3 Geometric program in convex form......Page 177 Design of a cantilever beam......Page 178 Minimizing spectral radius via Perron-Frobenius theory......Page 180 4.6 Generalized inequality constraints......Page 182 4.6.2 Semidefinite programming......Page 183 4.6.3 Examples......Page 184 4.7.1 General and convex vector optimization problems......Page 189 4.7.2 Optimal points and values......Page 190 4.7.3 Pareto optimal points and values......Page 192 4.7.4 Scalarization......Page 193 Scalarization of convex vector optimization problems......Page 194 4.7.5 Multicriterion optimization......Page 196 Trade-off analysis......Page 197 Scalarizing multicriterion problems......Page 198 Regularized least-squares......Page 199 Risk-return trade-off in portfolio optimization......Page 200 Bibliography......Page 203 Exercises......Page 204 5.1.1 The Lagrangian......Page 230 5.1.4 Linear approximation interpretation......Page 231 5.1.5 Examples......Page 233 5.1.6 The Lagrange dual function and conjugate functions......Page 236 Minimum volume covering ellipsoid......Page 237 5.2 The Lagrange dual problem......Page 238 5.2.1 Making dual constraints explicit......Page 239 5.2.2 Weak duality......Page 240 5.2.3 Strong duality and Slater’s constraint qualification......Page 241 5.2.4 Examples......Page 242 5.2.5 Mixed strategies for matrix games......Page 245 Epigraph variation......Page 247 5.3.2 Proof of strong duality under constraint qualification......Page 249 5.3.3 Multicriterion interpretation......Page 251 5.4.1 Max-min characterization of weak and strong duality......Page 252 5.4.2 Saddle-point interpretation......Page 253 5.4.3 Game interpretation......Page 254 5.4.4 Price or tax interpretation......Page 255 5.5.1 Certificate of suboptimality and stopping criteria......Page 256 5.5.2 Complementary slackness......Page 257 KKT conditions for nonconvex problems......Page 258 KKT conditions for convex problems......Page 259 5.5.4 Mechanics interpretation of KKT conditions......Page 261 5.5.5 Solving the primal problem via the dual......Page 263 5.6.1 The perturbed problem......Page 264 Sensitivity interpretations......Page 265 5.6.3 Local sensitivity analysis......Page 266 5.7.1 Introducing new variables and equality constraints......Page 268 5.7.2 Transforming the objective......Page 271 5.7.3 Implicit constraints......Page 272 5.8.1 Weak alternatives via the dual function......Page 273 Strict inequalities......Page 274 Strict inequalities......Page 275 5.8.3 Examples......Page 276 5.9.1 The Lagrange dual......Page 279 Slater’s condition and strong duality......Page 280 5.9.2 Optimality conditions......Page 281 KKT conditions......Page 282 5.9.3 Perturbation and sensitivity analysis......Page 283 Strong alternatives......Page 284 Bibliography......Page 287 Exercises......Page 288 Part II: Applications......Page 304 Approximation interpretation......Page 306 Design interpretation......Page 307 Chebyshev or minimax approximation......Page 308 Interpretation......Page 309 Example......Page 311 Sensitivity to outliers or large errors......Page 313 Small residuals and l1-norm approximation......Page 315 Variable bounds......Page 316 6.2 Least-norm problems......Page 317 Geometric interpretation......Page 318 Sparse solutions via least l1-norm......Page 319 6.3.1 Bi-criterion formulation......Page 320 Tikhonov regularization......Page 321 Smoothing regularization......Page 322 l1-norm regularization......Page 323 6.3.3 Reconstruction, smoothing, and de-noising......Page 325 Total variation reconstruction......Page 327 Total variation reconstruction example......Page 329 6.4.1 Stochastic robust approximation......Page 333 6.4.2 Worst-case robust approximation......Page 334 Norm bound error......Page 336 Uncertainty ellipsoids......Page 337 Norm bounded error with linear structure......Page 338 6.5 Function fitting and interpolation......Page 339 Piecewise-linear functions......Page 341 Piecewise polynomials and splines......Page 342 Function value interpolation and inequalities......Page 344 Integral constraints......Page 345 Minimum norm function fitting......Page 346 6.5.4 Sparse descriptions and basis pursuit......Page 348 Time-frequency analysis via basis pursuit......Page 349 6.5.5 Interpolation with convex functions......Page 352 Bounding values of an interpolating convex function......Page 353 Bounding consumer preference......Page 354 Bibliography......Page 358 Exercises......Page 359 7.1.1 Maximum likelihood estimation......Page 366 Linear measurements with IID noise......Page 367 Counting problems with Poisson distribution......Page 368 Covariance estimation for Gaussian variables......Page 370 7.1.2 Maximum a posteriori probability estimation......Page 372 Linear measurements with IID noise......Page 373 7.2 Nonparametric distribution estimation......Page 374 Prior information......Page 375 Maximum likelihood estimation......Page 376 Minimum Kullback-Leibler divergence......Page 377 7.3 Optimal detector design and hypothesis testing......Page 379 7.3.1 Deterministic and randomized detectors......Page 380 Limits on errors and detection probabilities......Page 381 Bias, mean-square error, and other quantities......Page 382 7.3.4 Multicriterion formulation and scalarization......Page 383 MAP and ML detectors......Page 384 7.3.5 Binary hypothesis testing......Page 385 7.3.6 Robust detectors......Page 387 Robust minimax detector for polyhedral P......Page 388 7.4.1 Chebyshev bounds......Page 389 Probability bounds with known first and second moments......Page 391 7.4.2 Chernoff bounds......Page 394 Chernoff bound for a Gaussian variable on a polyhedron......Page 395 7.4.3 Example......Page 396 Chernoff bounds......Page 397 7.5 Experiment design......Page 399 7.5.1 The relaxed experiment design problem......Page 400 7.5.2 Scalarizations......Page 401 A-optimal design......Page 402 Experiment design example......Page 403 Multiple measurements per experiment......Page 405 Bibliography......Page 407 Exercises......Page 408 8.1 Projection on a set......Page 412 Euclidean projection on a polyhedron......Page 413 8.1.2 Separating a point and a convex set......Page 414 8.1.3 Projection and separation via indicator and support functions......Page 416 8.2.1 Computing the distance between convex sets......Page 417 Euclidean distance between polyhedra......Page 418 8.2.3 Distance and separation via indicator and support functions......Page 419 8.3.1 Gram matrix and realizability......Page 420 Angle and distance constraints......Page 421 Ellipsoid and simplex volume......Page 422 8.3.2 Problems involving angles only......Page 423 8.3.3 Euclidean distance problems......Page 424 8.4.1 The L ̈owner-John ellipsoid......Page 425 Minimum volume ellipsoid covering union of ellipsoids......Page 426 Efficiency of L ̈owner-John ellipsoidal approximation......Page 427 Approximating a norm by a quadratic norm......Page 428 Maximum volume ellipsoid in an intersection of ellipsoids......Page 429 8.4.3 Affine invariance of extremal volume ellipsoids......Page 430 8.5.1 Chebyshev center......Page 431 Chebyshev center of a polyhedron......Page 432 8.5.2 Maximum volume ellipsoid center......Page 433 8.5.3 Analytic center of a set of inequalities......Page 434 Analytic center of a set of linear inequalities......Page 435 8.6 Classification......Page 437 Linear discrimination alternative......Page 438 Robust linear discrimination......Page 439 Support vector classifier......Page 440 Approximate linear discrimination via logistic modeling......Page 442 Quadratic discrimination......Page 444 Polynomial discrimination......Page 445 8.7.1 Linear facility location problems......Page 447 8.7.2 Placement constraints......Page 448 8.7.3 Nonlinear facility location problems......Page 449 Minimax delay placement......Page 451 8.8 Floor planning......Page 453 8.8.1 Relative positioning constraints......Page 454 Minimum spacing......Page 456 Containment constraints......Page 457 Distance constraints......Page 458 8.8.3 Floor planning via geometric programming......Page 459 Bibliography......Page 461 Exercises......Page 462 Part III: Algorithms......Page 470 Initial point and sublevel set......Page 472 Unconstrained geometric programming......Page 473 9.1.2 Strong convexity and implications......Page 474 Condition number of sublevel sets......Page 476 9.2 Descent methods......Page 478 Backtracking line search......Page 479 9.3.1 Convergence analysis......Page 481 Analysis for backtracking line search......Page 483 A quadratic problem in R^2......Page 484 A nonquadratic problem in R^2......Page 485 A problem in R^100......Page 487 Gradient method and condition number......Page 488 9.4 Steepest descent method......Page 490 Steepest descent for quadratic norm......Page 491 9.4.2 Steepest descent for l1-norm......Page 492 9.4.3 Convergence analysis......Page 494 Choice of norm for steepest descent......Page 495 Examples......Page 496 Minimizer of second-order approximation......Page 499 Solution of linearized optimality condition......Page 500 The Newton decrement......Page 501 9.5.2 Newton’s method......Page 502 Idea and outline of convergence proof......Page 503 Damped Newton phase......Page 504 Quadratically convergent phase......Page 505 Example in R^100......Page 507 Affine invariance of Newton’s method......Page 509 9.6 Self-concordance......Page 511 9.6.1 Definition and examples......Page 512 Self-concordant functions on R^n......Page 513 Composition with affine function......Page 514 Composition with logarithm......Page 515 Bound on suboptimality......Page 516 9.6.4 Analysis of Newton’s method for self-concordant functions......Page 518 Damped Newton phase......Page 519 The final complexity bound......Page 520 A family of self-concordant functions......Page 521 Practical importance of self-concordance......Page 522 Analytic center of a linear matrix inequality......Page 523 9.7.2 Computing the Newton step......Page 524 Band structure......Page 525 Diagonal plus low rank......Page 526 Bibliography......Page 528 Exercises......Page 529 10.1 Equality constrained minimization problems......Page 536 10.1.1 Equality constrained convex quadratic minimization......Page 537 10.1.2 Eliminating equality constraints......Page 538 10.1.3 Solving equality constrained problems via the dual......Page 539 10.2 Newton’s method with equality constraints......Page 540 Solution of linearized optimality conditions......Page 541 Affine invariance......Page 542 10.2.3 Newton’s method and elimination......Page 543 Assumptions......Page 544 Analysis via the eliminated problem......Page 545 10.3.1 Newton step at infeasible points......Page 546 Interpretation as primal-dual Newton step......Page 547 Residual norm reduction property......Page 548 10.3.2 Infeasible start Newton method......Page 549 Using infeasible start Newton method to simplify initialization......Page 550 Assumptions......Page 551 A basic inequality......Page 552 Damped Newton phase......Page 553 Quadratically convergent phase......Page 554 10.3.4 Convex-concave games......Page 555 A simple example......Page 556 10.4.2 Solving KKT systems......Page 557 Solving KKT system via elimination......Page 560 10.4.3 Examples......Page 562 Equality constrained analytic centering......Page 563 Optimal network flow......Page 565 Optimal control......Page 567 Analytic center of a linear matrix inequality......Page 568 Bibliography......Page 571 Exercises......Page 572 11.1 Inequality constrained minimization problems......Page 576 11.2 Logarithmic barrier function and central path......Page 577 11.2.1 Logarithmic barrier......Page 578 11.2.2 Central path......Page 579 Dual points from central path......Page 580 Force field interpretation......Page 582 11.3 The barrier method......Page 583 11.3.1 The barrier method......Page 584 Choice of t^(0)......Page 585 Linear programming in inequality form......Page 586 Geometric programming......Page 588 A family of standard form LPs......Page 589 11.3.4 Newton step for modified KKT equations......Page 592 11.4.1 Basic phase I method......Page 594 Sum of infeasibilities......Page 595 Termination near the phase II central path......Page 596 11.4.3 Examples......Page 597 Feasibility using infeasible start Newton method......Page 598 11.5 Complexity analysis via self-concordance......Page 600 11.5.1 Self-concordance assumption......Page 601 11.5.2 Newton iterations per centering step......Page 602 Choosing μ as a function of m......Page 605 11.5.4 Feasibility problems......Page 607 11.5.5 Combined phase I/phase II complexity......Page 609 11.5.6 Summary......Page 610 11.6 Problems with generalized inequalities......Page 611 11.6.1 Logarithmic barrier and central path......Page 612 The central path......Page 613 Dual points on central path......Page 614 A small SOCP......Page 616 A small SDP......Page 617 A family of SDPs......Page 618 11.6.4 Complexity analysis via self-concordance......Page 620 Generalized logarithm for dual cone......Page 622 Derivation of the basic bound......Page 623 11.7.1 Primal-dual search direction......Page 624 Comparison with barrier method search directions......Page 625 Line search......Page 627 Small LP and GP......Page 628 11.8 Implementation......Page 630 11.8.1 Standard form linear programming......Page 631 11.8.2 l1-norm approximation......Page 632 11.8.3 Semidefinite programming in inequality form......Page 633 11.8.4 Network rate optimization......Page 634 Bibliography......Page 636 Exercises......Page 638 Appendices......Page 646 A.1.1 Inner product, Euclidean norm, and angle......Page 648 A.1.2 Norms, distance, and unit ball......Page 649 A.1.3 Examples......Page 650 A.1.5 Operator norms......Page 651 A.2.1 Open and closed sets......Page 652 A.2.2 Supremum and infimum......Page 653 A.3.3 Closed functions......Page 654 A.4.1 Derivative and gradient......Page 655 A.4.2 Chain rule......Page 657 A.4.3 Second derivative......Page 658 A.5.1 Range and nullspace......Page 660 A.5.2 Symmetric eigenvalue decomposition......Page 661 A.5.3 Generalized eigenvalue decomposition......Page 662 A.5.4 Singular value decomposition......Page 663 Bibliography......Page 667 B.1 Single constraint quadratic optimization......Page 668 B.2 The S-procedure......Page 670 B.3 The field of values of two symmetric matrices......Page 671 B.4 Proofs of the strong duality results......Page 672 Bibliography......Page 674 C.1 Matrix structure and algorithm complexity......Page 676 C.1.1 Complexity analysis via flop count......Page 677 C.1.2 Cost of basic matrix-vector operations......Page 678 C.2.1 Linear equations that are easy to solve......Page 679 C.2.2 The factor-solve method......Page 681 C.3.1 LU factorization......Page 683 C.3.2 Cholesky factorization......Page 684 C.3.3 LDLT factorization......Page 686 C.4.1 Eliminating a block of variables......Page 687 C.4.2 Block elimination and structure......Page 691 C.4.3 The matrix inversion lemma......Page 693 C.5 Solving underdetermined linear equations......Page 696 Bibliography......Page 699 References......Page 700 Notation......Page 712 Index......Page 716 Back Cover......Page 732 From the publisher. Convex optimization problems arise frequently in many different fields. This book provides a comprehensive introduction to the subject, and shows in detail how such problems can be solved numerically with great efficiency. The book begins with the basic elements of convex sets and functions, and then describes various classes of convex optimization problems. Duality and approximation techniques are then covered, as are statistical estimation techniques. Various geometrical problems are then presented, and there is detailed discussion of unconstrained and constrained minimization problems, and interior-point methods. The focus of the book is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. It contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics Convex optimization problems arise frequently in many different fields. A comprehensive introduction to the subject, this book shows in detail how such problems can be solved numerically with great efficiency. The focus is on recognizing convex optimization problems and then finding the most appropriate technique for solving them. The text contains many worked examples and homework exercises and will appeal to students, researchers and practitioners in fields such as engineering, computer science, mathematics, statistics, finance, and economics.