Convex Optimization by Stephen Boyd and Lieven Vandenberghe

vatraxaki said:

Here is a link to a very good book on convex optimization by Stephen Boyd and Lieven Vandenberghe. It is available in electronic format at:

**broken link removed**

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

Click to expand...