Large-scale and distributed optimization

"This book presents tools and methods for large-scale and distributed optimization. Since many methods in "Big Data" fields rely on solving large-scale optimization problems, often in distributed fashion, this topic has over the last decade emerged to become very important. As well as specific coverage of this active research field, the book serves as a powerful source of information for practitioners as well as theoreticians. Large-Scale and Distributed Optimization is a unique combination of contributions from leading experts in the field, who were speakers at the LCCC Focus Period on Large-Scale and Distributed Optimization, held in Lund, 14th-16th June 2017. A source of information and innovative ideas for current and future research, this book will appeal to researchers, academics, and students who are interested in large-scale optimization"--Print version, page 4 of cover Preface......Page 6 Contents......Page 7 Contributors......Page 11 1.1.1 The Traditional Standard......Page 14 1.1.2 The Composite Form......Page 15 1.1.3 Randomized Methods......Page 18 1.1.4 Consensus Optimization......Page 19 1.1.4.1 Distributed Algorithms......Page 20 1.1.6 Omissions......Page 21 References......Page 22 2.1 Introduction......Page 24 Notation......Page 25 2.2 Convex Optimization......Page 26 2.2.1 Interior-Point Methods......Page 27 2.2.2 Parametric QPs......Page 28 2.3.1 Quadratic Program......Page 30 2.3.2 Backward Dynamic Programming......Page 31 2.3.3 Forward Dynamic Programming......Page 34 2.3.4 Parallel Computation......Page 35 2.3.5 Merging of Cliques......Page 37 2.4 Regularized MPC......Page 38 2.4.1 Equivalent QP......Page 39 2.5 Stochastic MPC......Page 40 2.7 Conclusions......Page 43 References......Page 44 3 Decomposition Methods for Large-Scale Semidefinite Programs with Chordal Aggregate Sparsity and Partial Orthogonality......Page 46 3.1 Introduction......Page 47 3.2.1 Essential Notions from Graph Theory......Page 49 3.2.2 Graphs, Sparse Matrices, and Chordal Decomposition......Page 50 3.3.1 Homogeneous Self-dual Embedding......Page 52 3.3.2 A Tailored ADMM Algorithm......Page 54 3.4 Cone Decomposition in Sparse SDPs......Page 55 3.5 Affine Decomposition in SDPs with Partial Orthogonality......Page 59 3.6.1 CDCS......Page 61 3.6.2 Cone Decomposition: The hsde Option......Page 62 3.6.3 Affine Decomposition: The sos Option......Page 64 3.7 Conclusion......Page 65 References......Page 66 4 Smoothing Alternating Direction Methods for Fully Nonsmooth Constrained Convex Optimization......Page 69 4.1 Introduction......Page 70 4.2 Preliminaries: Lagrangian Primal-Dual Formulation......Page 72 4.2.2 Basic Assumptions......Page 73 4.2.4 Technical Assumption......Page 74 4.3 Smoothing the Primal-Dual Gap Function......Page 75 4.4.1 Main Steps......Page 77 4.4.2 Initialization......Page 78 4.4.3 Updating the Parameters......Page 79 4.4.4 The New Smoothing AMA Algorithm......Page 80 4.4.5 Convergence Analysis......Page 81 4.4.6 Special Case: g is Strongly Convex......Page 82 4.4.7 Composite Convex Minimization with Linear Operators......Page 83 4.5.1 The Main Steps of the Smoothing ADMM Method......Page 84 4.5.2 Updating Parameters......Page 85 4.5.4 Convergence Analysis......Page 86 4.5.5 SAMA vs. SADMM......Page 87 4.6 Numerical Evidence......Page 88 4.7 Discussion......Page 90 Proof of Lemma 2: The Primal-Dual Bounds......Page 93 Convergence Analysis of Algorithm 1......Page 94 Proof of Lemma 4: Bound on Gγβ for the First Iteration......Page 96 Proof of Lemma 3: Gap Reduction Condition......Page 97 Proof of Lemma 5: Parameter Updates......Page 99 Proof of Theorem 1: Convergence of Algorithm 1......Page 100 Convergence Analysis of Algorithm 2......Page 101 Proof of Lemma 6: Gap Reduction Condition......Page 102 Proof of Lemma 7: Parameter Updates......Page 104 Proof of Theorem 2: Convergence of Algorithm 2......Page 105 References......Page 106 5.1 Introduction......Page 108 Notation and Background......Page 110 5.2 A Simple Framework for Primal-Dual Algorithms......Page 112 5.3 Simplified Asymmetric Forward-Backward-Adjoint Splitting......Page 118 5.4 A Unified Convergence Analysis for Primal-Dual Algorithms......Page 123 5.4.1 Linear Convergence......Page 124 References......Page 130 6.1 Introduction......Page 132 6.2 Applications......Page 135 6.3 Analysis......Page 138 6.3.1 Possible Generalizations......Page 148 6.4.1 Basis Pursuit......Page 149 6.4.2 Basis Pursuit with Noise......Page 151 6.4.3 Robust Principal Component Analysis......Page 154 References......Page 156 7.1 Introduction......Page 159 7.2 Notation, Background and Preliminary Results......Page 161 7.3.1 Stochastic Forward-Douglas-Rachford Splitting Method......Page 163 7.3.2 Composite Monotone Inclusions Involving Cocoercive Operators......Page 174 7.4 Convergence Rate......Page 179 References......Page 187 8 Mirror Descent and Convex Optimization Problems with Non-smooth Inequality Constraints......Page 190 8.1 Introduction......Page 191 8.2 Mirror Descent Basics......Page 192 8.3.1 Convex Non-smooth Objective Function......Page 194 8.3.2 Strongly Convex Non-smooth Objective Function......Page 199 8.3.3 General Convex Objective Function......Page 203 8.4 Randomization for Constrained Problems......Page 206 8.4.1 Convex Objective Function, Control of Expectation......Page 207 8.4.2 Convex Objective Function, Control of Large Deviation......Page 210 8.4.3 Strongly Convex Objective Function, Control of Expectation......Page 213 8.4.4 Strongly Convex Objective Function, Control of Large Deviation......Page 216 8.5 Discussion......Page 219 References......Page 220 9.1 Introduction......Page 223 9.2.1 Algorithm and Convergence......Page 229 9.2.2 Numerics......Page 232 9.3 Stochastic Variance Reduced Frank-Wolfe (SVRF) Algorithm with Approximate Oracle (SVRF)......Page 237 9.4 Theoretical Guarantees for SVRF......Page 239 9.5 SSVRF......Page 246 9.6 Theoretical Guarantees for SSVRF......Page 249 Appendix......Page 251 References......Page 252 10 Decentralized Consensus Optimization and Resource Allocation......Page 254 10.1 Introduction......Page 255 10.1.1 Literature Review......Page 256 10.1.2 Notation and Basic Settings for Networks......Page 261 10.2.1 Over Time-Invariant Undirected Graphs......Page 263 10.2.2 Over Time-Varying Undirected Graphs......Page 265 10.2.2.1 Geometric Convergence......Page 267 10.2.3 Over Time-Varying Directed Graphs......Page 271 10.2.3.1 Geometric Convergence......Page 272 10.3 Resource Allocation and Its Connection to Consensus Optimization......Page 274 10.3.1 The Resource Allocation and Consensus Optimization Problems......Page 275 10.3.2 The Mirror Relationship......Page 276 10.4 Decentralized Resource Allocation Algorithms......Page 277 10.4.1 Over Time-Invariant Undirected Graphs......Page 278 10.4.1.1 Unconstrained Case: Mirror-EXTRA......Page 279 10.4.2 Over Time-Varying Directed Graphs......Page 281 10.4.3 Decentralized Resource Allocation with Local Couplings......Page 282 10.5.1 Consensus Optimization......Page 284 10.5.2 Resource Allocation......Page 286 References......Page 290 11 Communication-Efficient Distributed Optimization of Self-concordant Empirical Loss......Page 295 11.1 Introduction......Page 296 11.1.1 Communication Efficiency of Distributed Algorithms......Page 297 11.1.2 Outline of Our Approach......Page 299 11.2 Self-concordant Empirical Loss......Page 302 11.3 Inexact Damped Newton Method......Page 305 11.3.2 Scaling for Non-standard Self-concordant Functions......Page 309 11.4 The DiSCO Algorithm......Page 310 11.4.1 Distributed Computing of the Inexact Newton Step......Page 311 11.4.2 DiSCO and Its Communication Efficiency......Page 315 11.4.3 A Simple Variant Without PCG Iterations......Page 317 11.5 Stochastic Analysis......Page 318 11.5.1 Application to Linear Regression......Page 322 11.5.2.1 Logistic Regression......Page 324 11.5.2.2 Smoothed Hinge Loss......Page 325 11.6.1 Experiment Setup......Page 326 11.6.2 Performance Evaluation......Page 327 11.7 Extension to Distributed Composite Minimization......Page 329 11.8 Conclusions......Page 330 Appendix 1: Proof of Theorem 1......Page 331 Appendix 2: Proof of Theorem 2 and Corollary 2......Page 334 Appendix 3: Proof of Lemma 4......Page 336 Appendix 4: Proof of Lemma 5......Page 337 Appendix 5: Proof of Lemma 6......Page 341 Appendix 6: Proof of Theorem 5......Page 343 References......Page 345 12 Numerical Construction of Nonsmooth Control LyapunovFunctions......Page 348 12.1 Introduction......Page 349 12.2 Mathematical Setting......Page 351 12.3.1 Discretization of the State Space......Page 354 12.3.2 Continuous Piecewise Affine Functions......Page 355 12.4.1 The Decrease Condition for Piecewise Affine Functions......Page 357 12.4.2 Semiconcavity Conditions......Page 358 12.4.3 Local Minimum Condition......Page 364 12.4.4 A Finite Dimensional Optimization Problem......Page 365 12.5.1 Approximation of System Parameters and Reformulation of Nonlinear Constraints......Page 367 12.5.2 The Mixed Integer Linear Programming Formulation......Page 369 12.6.1 Artstein's Circles......Page 370 12.6.2 A Two-Dimensional Example with Two Inputs......Page 373 12.7 Conclusions......Page 376 References......Page 377 13 Convergence of an Inexact Majorization-Minimization Method for Solving a Class of Composite Optimization Problems......Page 379 13.1 Introduction......Page 380 13.2.2 Definition......Page 382 13.2.3 Examples......Page 383 13.2.4 Consistent Majorizers of Composite Functions......Page 387 13.3 Stationarity Measures and Conditions......Page 392 13.4.1 The General Scheme......Page 397 13.4.2 Convergence Analysis of the IMM Method......Page 400 13.5 Applying the IMM Method on Compositions of Strongly Convex Majorizers......Page 403 References......Page 413 "This book presents tools and methods for large-scale and distributed optimization. Since many methods in "Big Data" fields rely on solving large-scale optimization problems, often in distributed fashion, this topic has over the last decade emerged to become very important. As well as specific coverage of this active research field, the book serves as a powerful source of information for practitioners as well as theoreticians. Large-Scale and Distributed Optimization is a unique combination of contributions from leading experts in the field, who were speakers at the LCCC Focus Period on Large-Scale and Distributed Optimization, held in Lund, 14th–16th June 2017. A source of information and innovative ideas for current and future research, this book will appeal to researchers, academics, and students who are interested in large-scale optimization". -- Prové de l'editor