Nonlinear Optimization Book

Preface xi

Chapter 1. Introduction 1

PART 1. THEORY 15

Chapter 2. Elements of Convex Analysis 17
2.1 Convex Sets 17
2.2 Cones 25
2.3 Extreme Points 39
2.4 Convex Functions 44
2.5 Subdifferential Calculus 57
2.6 Conjugate Duality 75

Chapter 3. Optimality Conditions 88
3.1 Unconstrained Minima of Differentiable Functions 88
3.2 Unconstrained Minima of Convex Functions 92
3.3 Tangent Cones 98
3.4 Optimality Conditions for Smooth Problems 113
3.5 Optimality Conditions for Convex Problems 125
3.6 Optimality Conditions for Smooth-Convex Problems 133
3.7 Second Order Optimality Conditions 139
3.8 Sensitivity 150

Chapter 4. Lagrangian Duality 160
4.1 The Dual Problem 160
4.2 Duality Relations 166
4.3 Conic Programming 175
4.4 Decomposition 180
4.5 Convex Relaxation of Nonconvex Problems 186
4.6 The Optimal Value Function 191
4.7 The Augmented Lagrangian 196

PART 2. METHODS 209

Chapter 5. Unconstrained Optimization of Differentiable Functions 211
5.1 Introduction to Iterative Algorithms 211
5.2 Line Search 213
5.3 The Method of Steepest Descent 218
5.4 Newton's Method 233
5.5 The Conjugate Gradient Method 240
5.6 Quasi-Newton Methods 257
5.7 Trust Region Methods 266
5.8 Nongradient Methods 275

Chapter 6. Constrained Optimization of Differentiable Functions 286
6.1 Feasible Point Methods 286
6.2 Penalty Methods 297
6.3 The Basic Dual Method 308
6.4 The Augmented Lagrangian Method 311
6.5 Newton's Method 324
6.6 Barrier Methods 331

Chapter 7. Nondifferentiable Optimization 343
7.1 The Subgradient Method 343
7.2 The Cutting Plane Method 357
7.3 The Proximal Point Method 366
7.4 The Bundle Method 372
7.5 The Trust Region Method 384
7.6 Constrained Problems 389
7.7 Composite Optimization 397
7.8 Nonconvex Constraints 406

Appendix A. Stability of Set-Constrained Systems 411
A.1 Linear-Conic Systems 411
A.2 Set-Constrained Linear Systems 415
A.3 Set-Constrained Nonlinear Systems 418
Further Reading 427

Bibliography 431
Index 445