1. Introduction 1
2. Elements of Convex Analysis 17
2.1 Convex Sets 17
2.1.1 Basic Properties 17
2.1.2 Projection 20
2.1.3 Separation Theorems 24
2.2 Cones 25
2.2.1 Basic Concepts 25
2.2.2 Separation of Cones 32
2.2.3 Normal Cones 37
2.3 Extreme Points 39
2.4 Convex Functions 44
2.4.1 Basic Concepts 44
2.4.2 Smooth Convex Functions 50
2.4.3 Directional Derivatives 54
2.5 Subdifferential Calculus 57
2.5.1 Subgradients and Subdifferentials 57
2.5.2 Chain Rules of Subdifferential Calculus 67
2.5.3 The Subdifferential of the Maximum Function 71
2.6 Conjugate Duality 75
2.6.1 The Conjugate Function 75
2.6.2 The Biconjugate Function 78
2.6.3 Subgradients of Conjugate Functions 81
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.3.1 Basic Concepts 98
3.3.2 Smooth Constraints. Metric Regularity 101
3.3.3 Convex Nonsmooth Constraints 107
3.3.4 Smooth--Convex Constraints 112
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.7.1 Second Order Tangent Sets 139
3.7.2 Optimality Conditions 144
3.8 Sensitivity 150
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
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.3.1 The Direction of Steepest Descent 218
5.3.2 Constant Step Size 219
5.3.3 Two-Slope Test 220
5.3.4 Directional Minimization 222
5.3.5 Speed of Convergence 223
5.4 Newton's Method 233
5.4.1 Basic Properties 233
5.4.2 Speed of Convergence 236
5.4.3 The Gauss--Newton Method 238
5.5 The Conjugate Gradient Method 240
5.5.1 Minimization of Quadratic Functions 240
5.5.2 Speed of Convergence. Application to Nonquadratic Functions 246
5.5.3 Pre-Conditioning 253
5.6 Quasi-Newton Methods 257
5.6.1 Conjugate Directions by Quasi-Newton Updates 257
5.6.2 Family of Quasi-Newton Methods. Application to Nonquadratic Functions 261
5.6.3 Limited Memory Versions 265
5.7 Trust Region Methods 266
5.7.1 Main Ideas 266
5.7.2 The Subproblem 268
5.7.3 Convergence 272
5.8 Nongradient Methods 275
5.8.1 Numerical Differentiation 275
5.8.2 Coordinate Descent 276
5.8.3 Conjugate Directions without Derivatives 278
5.8.4 Newton's Method Without Hessians 280
6. Constrained Optimization of Differentiable Functions 286
6.1 Feasible Point Methods 286
6.1.1 The Projection Method 286
6.1.2 The Reduced Gradient Method 288
6.2 Penalty Methods 297
6.2.1 General Ideas 297
6.2.2 Quadratic Penalty 299
6.2.3 Exact Penalty Function 304
6.3 The Basic Dual Method 308
6.4 The Augmented Lagrangian Method 311
6.4.1 General Ideas 311
6.4.2 Local Convergence 314
6.4.3 Application to Convex Problems 319
6.5 Newton's Method 324
6.5.1 Main Ideas 324
6.5.2 Local Convergence 326
6.5.3 Line Search 328
6.6 Barrier Methods 331
6.6.1 Main Ideas 331
6.6.2 Primal-Dual Newton's Method 338
7. Nondifferentiable Optimization 343
7.1 The Subgradient Method 343
7.1.1 The Basic Version 343
7.1.2 Projection 350
7.1.3 Application to Dual Problems 351
7.1.4 Known Optimal Value 355
7.2 The Cutting Plane Method 357
7.2.1 The Main Concepts 357
7.2.2 Convergence 359
7.2.3 Finite Convergence for Piecewise-Linear Functions 360
7.2.4 Application to Dual Problems 364
7.3 The Proximal Point Method 366
7.3.1 Moreau--Yosida Regularization 366
7.3.2 Application to Convex Optimization 368
7.4 The Bundle Method 372
7.4.1 Main Ideas 372
7.4.2 Convergence 374
7.4.3 Application to Polyhedral Problems 381
7.4.4 Aggregation of Cuts 382
7.5 The Trust Region Method 384
7.6 Constrained Problems 389
7.6.1 The Exact Penalty Function 389
7.6.2 Cutting Plane Methods 392
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