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 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

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

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

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

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

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 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