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
Ⅰ 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
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
Ⅱ 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 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 Classification 422
8.7 Placement and location 432
8.8 Floor planning 438
Bibliography 446
Exercises 447
Ⅲ 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 field of values oftwo 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 equationswith 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