Lectures on convex optimization

✍ Scribed by Nesterov Yu

• Publisher: Springer
• Year: 2018
• Tongue: English
• Leaves: 603
• Edition: 2
• Category: Library

✦ Table of Contents

Preface......Page 7
Acknowledgements......Page 10
Introduction......Page 11
Contents......Page 17
Part I Black-Box Optimization......Page 22
1.1.1 General Formulation of the Problem......Page 23
1.1.2 Performance of Numerical Methods......Page 27
1.1.3 Complexity Bounds for Global Optimization......Page 30
1.1.4 Identity Cards of the Fields......Page 35
1.2 Local Methods in Unconstrained Minimization......Page 37
1.2.1 Relaxation and Approximation......Page 38
1.2.2 Classes of Differentiable Functions......Page 43
1.2.3 The Gradient Method......Page 48
1.2.4 Newton's Method......Page 55
1.3.1 The Gradient Method and Newton's Method: What Is Different?......Page 60
1.3.2 Conjugate Gradients......Page 65
1.3.3.1 Lagrangian Relaxation......Page 70
1.3.3.2 Penalty Functions......Page 74
1.3.3.3 Barrier Functions......Page 76
2.1.1 Smooth Convex Functions......Page 79
2.1.2 Lower Complexity Bounds for F∞,1L(Rn)......Page 89
2.1.3 Strongly Convex Functions......Page 93
2.1.4 Lower Complexity Bounds for S∞,1μ,L(Rn)......Page 97
2.1.5 The Gradient Method......Page 100
2.2 Optimal Methods......Page 102
2.2.1 Estimating Sequences......Page 103
2.2.2 Decreasing the Norm of the Gradient......Page 117
2.2.3 Convex Sets......Page 121
2.2.4 The Gradient Mapping......Page 132
2.2.5 Minimization over Simple Sets......Page 134
2.3.1 The Minimax Problem......Page 137
2.3.2 Gradient Mapping......Page 140
2.3.3 Minimization Methods for the Minimax Problem......Page 143
2.3.4 Optimization with Functional Constraints......Page 147
2.3.5 The Method for Constrained Minimization......Page 151
3.1 General Convex Functions......Page 158
3.1.1 Motivation and Definitions......Page 159
3.1.2 Operations with Convex Functions......Page 166
3.1.3 Continuity and Differentiability......Page 176
3.1.4 Separation Theorems......Page 178
3.1.5 Subgradients......Page 181
3.1.6 Computing Subgradients......Page 186
3.1.7 Optimality Conditions......Page 195
3.1.8 Minimax Theorems......Page 207
3.1.9 Basic Elements of Primal-Dual Methods......Page 210
3.2.1 General Lower Complexity Bounds......Page 213
3.2.2 Estimating Quality of Approximate Solutions......Page 217
3.2.3 The Subgradient Method......Page 220
3.2.4 Minimization with Functional Constraints......Page 223
3.2.5 Approximating the Optimal Lagrange Multipliers......Page 225
3.2.6 Strongly Convex Functions......Page 228
3.2.7 Complexity Bounds in Finite Dimension......Page 233
3.2.8 Cutting Plane Schemes......Page 236
3.3.1 Nonsmooth Models of the Objective Function......Page 244
3.3.2 Kelley's Method......Page 245
3.3.3 The Level Method......Page 248
3.3.4 Constrained Minimization......Page 252
4.1.1 Cubic Regularization of Quadratic Approximation......Page 260
4.1.2 General Convergence Results......Page 265
4.1.3 Global Efficiency Bounds on Specific Problem Classes......Page 270
4.1.3.1 Star-Convex Functions......Page 271
4.1.3.2 Gradient-Dominated Functions......Page 274
4.1.3.3 Nonlinear Transformations of Convex Functions......Page 278
4.1.4.1 Minimizing the Cubic Regularization......Page 281
4.1.4.2 Line Search Strategies......Page 285
4.1.5 Global Complexity Bounds......Page 287
4.2.1 Real Vector Spaces......Page 289
4.2.2 Uniformly Convex Functions......Page 293
4.2.3 Cubic Regularization of Newton Iteration......Page 297
4.2.4 An Accelerated Scheme......Page 300
4.2.5 Global Non-degeneracy for Second-Order Schemes......Page 304
4.2.6 Minimizing Strongly Convex Functions......Page 307
4.2.7 False Acceleration......Page 309
4.2.8 Decreasing the Norm of the Gradient......Page 310
4.2.9 Complexity of Non-degenerate Problems......Page 312
4.3.1 Lower Complexity Bounds......Page 313
4.3.2 A Conceptual Optimal Scheme......Page 318
4.3.3 Complexity of the Search Procedure......Page 323
4.4.1 Quadratic Regularization of the Gauss–Newton Iterate......Page 324
4.4.2 The Modified Gauss–Newton Process......Page 331
4.4.3 Global Rate of Convergence......Page 333
4.4.4.1 A Comparative Analysis of Scheme (4.4.17)......Page 338
4.4.4.2 Implementation Issues......Page 339
Part II Structural Optimization......Page 342
5.1.1 The Black Box Concept in Convex Optimization......Page 343
5.1.2 What Does the Newton's Method Actually Do?......Page 346
5.1.3 Definition of Self-concordant Functions......Page 348
5.1.4 Main Inequalities......Page 355
5.1.5 Self-Concordance and Fenchel Duality......Page 364
5.2.1 Local Convergence of Newton's Methods......Page 371
5.2.2 Path-Following Scheme......Page 376
5.2.3 Minimizing Strongly Convex Functions......Page 381
5.3.1 Motivation......Page 385
5.3.2 Definition of a Self-concordant Barrier......Page 387
5.3.3 Main Inequalities......Page 393
5.3.4 The Path-Following Scheme......Page 396
5.3.5 Finding the Analytic Center......Page 400
5.3.6 Problems with Functional Constraints......Page 403
5.4 Applications to Problems with Explicit Structure......Page 406
5.4.1 Lower Bounds for the Parameter of a Self-concordant Barrier......Page 407
5.4.2 Upper Bound: Universal Barrier and Polar Set......Page 408
5.4.3 Linear and Quadratic Optimization......Page 409
5.4.4 Semidefinite Optimization......Page 413
5.4.5.1 Circumscribed Ellipsoid......Page 418
5.4.5.2 Inscribed Ellipsoid with Fixed Center......Page 419
5.4.5.3 Inscribed Ellipsoid with Free Center......Page 420
5.4.6 Constructing Self-concordant Barriers for Convex Sets......Page 421
5.4.7 Examples of Self-concordant Barriers......Page 424
5.4.8 Separable Optimization......Page 432
5.4.8.2 Entropy Function......Page 433
5.4.8.5 Geometric Optimization......Page 434
5.4.9 Choice of Minimization Scheme......Page 435
6.1 Smoothing for an Explicit Model of an Objective Function......Page 440
6.1.1 Smooth Approximations of Non-differentiable Functions......Page 441
6.1.2 The Minimax Model of an Objective Function......Page 444
6.1.3 The Fast Gradient Method for Composite Minimization......Page 447
6.1.4 Application Examples......Page 450
6.1.4.1 Minimax Strategies for Matrix Games......Page 453
6.1.4.2 The Continuous Location Problem......Page 456
6.1.4.3 Variational Inequalities with a Linear Operator......Page 457
6.1.4.4 Piece-Wise Linear Optimization......Page 460
6.1.5.2 Computational Stability......Page 462
6.2.1 Primal-Dual Problem Structure......Page 463
6.2.2 An Excessive Gap Condition......Page 465
6.2.3 Convergence Analysis......Page 469
6.2.4 Minimizing Strongly Convex Functions......Page 471
6.3.1 Smooth Symmetric Functions of Eigenvalues......Page 477
6.3.2 Minimizing the Maximal Eigenvalue of the Symmetric Matrix......Page 483
6.4.1 A Linear Optimization Oracle......Page 485
6.4.2 The Method of Conditional Gradients with Composite Objective......Page 487
6.4.3 Conditional Gradients with Contraction......Page 491
6.4.4 Computing the Primal-Dual Solution......Page 496
6.4.5 Strong Convexity of the Composite Term......Page 498
6.4.6 Minimizing the Second-Order Model......Page 500
7.1 Homogeneous Models of an Objective Function......Page 505
7.1.1 The Conic Unconstrained Minimization Problem......Page 506
7.1.2 The Subgradient Approximation Scheme......Page 512
7.1.3 Direct Use of the Problem Structure......Page 514
7.1.4.1 Linear Programming......Page 520
7.1.4.2 Minimization of the Spectral Radius......Page 522
7.1.4.3 The Truss Topology Design Problem......Page 525
7.2.1 Computing Rounding Ellipsoids......Page 527
7.2.1.1 Convex Sets with Central Symmetry......Page 529
7.2.1.2 General Convex Sets......Page 535
7.2.1.3 Sign-Invariant Convex Sets......Page 539
7.2.2 Minimizing the Maximal Absolute Value of Linear Functions......Page 543
7.2.3 Bilinear Matrix Games with Non-negative Coefficients......Page 548
7.2.4 Minimizing the Spectral Radius of Symmetric Matrices......Page 551
7.3.1 Smoothing by a Self-Concordant Barrier......Page 555
7.3.2 The Barrier Subgradient Scheme......Page 560
7.3.3 Maximizing Positive Concave Functions......Page 564
7.3.4.1 The Fractional Covering Problem......Page 567
7.3.4.2 The Maximal Concurrent Flow Problem......Page 568
7.3.4.3 The Minimax Problem with Nonnegative Components......Page 569
7.3.4.4 Semidefinite Relaxation of the Boolean Quadratic Problem......Page 570
7.3.5.1 A Decision-Making Process in an Uncertain Environment......Page 571
7.3.5.3 Processes with Full Production Cycles......Page 575
7.3.5.4 Discussion......Page 576
7.4.1 Strictly Positive Functions......Page 577
7.4.2 The Quasi-Newton Method......Page 580
7.4.3 Interpretation of Approximate Solutions......Page 583
7.4.3.1 Relative Accuracy......Page 584
7.4.3.2 Absolute Accuracy......Page 585
A.1 Newton's Method for Univariate Minimization......Page 587
A.2 Barrier Projection onto a Simplex......Page 589
Chapter 1: Nonlinear Optimization......Page 592
Chapter 4: Second-Order Methods......Page 593
Chapter 5: Polynomial-Time Interior-Point Methods......Page 594
Chapter 7: Optimization in Relative Scale......Page 595
References......Page 596
Index......Page 599