Convex Optimization

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 ℓ1-norm approximation......Page 315
Variable bounds......Page 316
6.2 Least-norm problems......Page 317
Geometric interpretation......Page 318
Sparse solutions via least ℓ1-norm......Page 319
6.3.1 Bi-criterion formulation......Page 320
Tikhonov regularization......Page 321
Smoothing regularization......Page 322
ℓ1-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 ℓ1-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 ℓ1-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