This book, developed through class instruction at MIT over the last 15 years, provides an accessible, concise, and intuitive presentation of algorithms for solving convex optimization problems. It relies on rigorous mathematical analysis, but also aims at an intuitive exposition that makes use of visualization where possible. This is facilitated by the extensive use of analytical and algorithmic concepts of duality, which by nature lend themselves to geometrical interpretation. The book places particular emphasis on modern developments, and their widespread applications in fields such as large-scale resource allocation problems, signal processing, and machine learning.
Among its features, the book:
* Develops comprehensively the theory of descent and approximation methods, including gradient and subgradient projection methods, cutting plane and simplicial decomposition methods, and proximal methods
* Describes and analyzes augmented Lagrangian methods, and alternating direction methods of multipliers
* Develops the modern theory of coordinate descent methods, including distributed asynchronous convergence analysis
* Comprehensively covers incremental gradient, subgradient, proximal, and constraint projection methods
* Includes optimal algorithms based on extrapolation techniques, and associated rate of convergence analysis
* Describes a broad variety of applications of large-scale optimization and machine learning
* Contains many examples, illustrations, and exercises
* Is structured to be used conveniently either as a standalone text for a class on convex analysis and optimization, or as a theoretical supplement to either an applications/convex optimization models class or a nonlinear programming class
Author(s): Dimitri P. Bertsekas
Edition: 1
Publisher: Athena Scientific
Year: 2015
Language: English
Pages: 576
Tags: Математика;Методы оптимизации;
Bertsekas, D.Convex optimization algorithms (AS,1 ed.,2015)(ISBN 9781886529281)(578p) ......Page 2
Copyright ......Page 3
About the author vii ......Page 8
Preface ix ......Page 10
Contents iii ......Page 4
1. Convex Optimization Models: An Overview 1 ......Page 14
1.1. Lagrange Duality 2 ......Page 15
1.1.1. Separable Problems - Decomposition 7 ......Page 20
1.1.2. Partitioning 9 ......Page 22
1.2. Fenchel Duality and Conic Programming 10 ......Page 23
1.2.1. Linear Conic Problems 15 ......Page 28
1.2.2. Second Order Cone Programming 17 ......Page 30
1.2.3. Semidefinite Programming 22 ......Page 35
1.3. Additive Cost Problems 25 ......Page 38
1.4. Large Number of Constraints 34 ......Page 47
1.5. Exact Penalty Functions 39 ......Page 52
1.6. Notes, Sources, and Exercises 47 ......Page 60
2. Optimization Algorithms: An Overview 53 ......Page 66
2.1. Iterative Descent Algorithms 55 ......Page 68
2.1.1. Differentiable Cost Function Descent - Unconstrained Problems 58 ......Page 71
2.1.2. Constrained Problems - Feasible Direction Methods 71 ......Page 84
2.1.3. Nondifferentiable Problems - Subgradient Methods 78 ......Page 91
2.1.4. Alternative Descent Methods 80 ......Page 93
2.1.5. Incremental Algorithms 83 ......Page 96
2.1.6. Distributed Asynchronous Iterative Algorithms 104 ......Page 117
2.2. Approximation Methods 106 ......Page 119
2.2.1. Polyhedral Approximation 107 ......Page 120
2.2.2. Penalty, Augmented Lagrangian, and Interior Point Methods 108 ......Page 121
2.2.3. Proximal Algorithm, Bundle Methods, and \tTikhonov Regularization 110 ......Page 123
2.2.4. Alternating Direction Method of Multipliers 111 ......Page 124
2.2.5. Smoothing of Nondifferentiable Problems 113 ......Page 126
2.3. Notes, Sources, and Exercises 119 ......Page 132
3. Subgradient Methods 135 ......Page 148
3.1. Subgradients of Convex Real-Valued Functions 136 ......Page 149
3.1.1. Characterization of the Subdifferential 146 ......Page 159
3.2. Convergence Analysis of Subgradient Methods 148 ......Page 161
3.3. 6-Subgradient Methods 162 ......Page 175
3.3.1. Connection with Incremental Subgradient Methods 166 ......Page 179
3.4. Notes, Sources, and Exercises 167 ......Page 180
4. Polyhedral Approximation Methods 181 ......Page 194
4.1. Outer Linearization - Cutting Plane Methods 182 ......Page 195
4.2. Inner Linearization - Simplicial Decomposition 188 ......Page 201
4.3. Duality of Outer and Inner Linearization 194 ......Page 207
4.4. Generalized Polyhedral Approximation 196 ......Page 209
4.5. Generalized Simplicial Decomposition 209 ......Page 222
4.5.2. Nondifferentiable Cost and Side Constraints 213 ......Page 226
4.6. Polyhedral Approximation for Conic Programming 217 ......Page 230
4.7. Notes, Sources, and Exercises 228 ......Page 241
5. Proximal Algorithms 233 ......Page 246
5.1. Basic Theory of Proximal Algorithms 234 ......Page 247
5.1.1. Convergence 235 ......Page 248
5.1.2. Rate of Convergence 239 ......Page 252
5.1.3. Gradient Interpretation 246 ......Page 259
5.1.4. Fixed Point Interpretation, Overrelaxation, and Generalization 248 ......Page 261
5.2. Dual Proximal Algorithms 256 ......Page 269
5.2.1. Augmented Lagrangian Methods 259 ......Page 272
5.3. Proximal Algorithms with Linearization 268 ......Page 281
5.3.1. Proximal Cutting Plane Methods 270 ......Page 283
5.3.2. Bundle Methods 272 ......Page 285
5.3.3. Proximal Inner Linearization Methods 276 ......Page 289
5.4. Alternating Direction Methods of Multipliers 280 ......Page 293
5.4.1. Applications in Machine Learning 286 ......Page 299
5.4.2. ADMM Applied to Separable Problems 289 ......Page 302
5.5. Notes, Sources, and Exercises 293 ......Page 306
6. Additional Algorithmic Topics 301 ......Page 314
6.1. Gradient Projection Methods 302 ......Page 315
6.2. Gradient Projection with Extrapolation 322 ......Page 335
6.2.1. An Algorithm with Optimal Iteration Complexity 323 ......Page 336
6.2.2. Nondifferentiable Cost - Smoothing 326 ......Page 339
6.3. Proximal Gradient Methods 330 ......Page 343
6.4. Incremental Subgradient Proximal Methods 340 ......Page 353
6.4.1. Convergence for Methods with Cyclic Order 344 ......Page 357
6.4.2. Convergence for Methods with Randomized Order 353 ......Page 366
6.4.3. Application in Specially Structured Problems 361 ......Page 374
6.4.4. Incremental Constraint Projection Methods 365 ......Page 378
6.5. Coordinate Descent Methods 369 ......Page 382
6.5.1. Variants of Coordinate Descent 373 ......Page 386
6.5.2. Distributed Asynchronous Coordinate Descent 376 ......Page 389
6.6. Generalized Proximal Methods p. 382 ......Page 395
6.7. e-Descent and Extended Monotropic Programming 396 ......Page 409
6.7.1. e-Subgradients 397 ......Page 410
6.7.2. e-Descent Method 400 ......Page 413
6.7.3. Extended Monotropic Programming Duality 406 ......Page 419
6.7.4. Special Cases of Strong Duality 408 ......Page 421
6.8. Interior Point Methods 412 ......Page 425
6.8.1. Primal-Dual Methods for Linear Programming 416 ......Page 429
6.8.2. Interior Point Methods for Conic Programming 423 ......Page 436
6.8.3. Central Cutting Plane Methods 425 ......Page 438
6.9. Notes, Sources, and Exercises 426 ......Page 439
Appendix A: Mathematical Background 443 ......Page 456
A.I. Linear Algebra 445 ......Page 458
A.2. Topological Properties 450 ......Page 463
A.3. Derivatives 456 ......Page 469
A.4. Convergence Theorems 458 ......Page 471
B.l. Basic Concepts of Convex Analysis 467 ......Page 480
B.2. Basic Concepts of Polyhedral Convexity 489 ......Page 502
B.3. Basic Concepts of Convex Optimization 494 ......Page 507
B.4. Geometric Duality Framework 498 ......Page 511
B.5. Duality and Optimization 505 ......Page 518
References 519 ......Page 532
Index 557 ......Page 570
cover......Page 1
