Multi-agent optimization

Preface......Page 6
Contents......Page 8
 1.1 Introduction......Page 9
 1.2 Distributed Multi-Agent Problem......Page 13
  1.2.1 Problem and Assumptions......Page 14
  1.2.2 Consensus Problem and Algorithm......Page 16
 1.3 Distributed Synchronous Algorithms for Time-Varying Undirected Graphs......Page 21
  1.3.1 Convergence Analysis of Distributed Subgradient Method......Page 24
   1.3.1.1 Relation for a Single Agent Iterates......Page 25
   1.3.1.2 Relation for Agents' Iterates and Their Averages Through Perturbed Consensus......Page 27
   1.3.1.3 Basic Relation for Agents' Iterates......Page 31
   1.3.1.4 Convergence Result for Agents' Iterates......Page 37
  1.3.2 Numerical Examples......Page 40
 1.4 Distributed Asynchronous Algorithms for Static Undirected Graphs......Page 43
  1.4.1 Random Gossip and Random Broadcast for Consensus......Page 45
   1.4.1.1 Gossip-Based Consensus Algorithm......Page 46
   1.4.1.2 Broadcast-Based Consensus Algorithm......Page 49
  1.4.2 Distributed Asynchronous Algorithm......Page 52
  1.4.3 Convergence Analysis of Asynchronous Algorithm......Page 55
   1.4.3.1 Stepsize Analysis......Page 60
   1.4.3.2 Relation for Agents' Iterates and Their Averages......Page 64
   1.4.3.3 Convergence Result for Asynchronous Algorithm......Page 73
  1.5.1 Literature on Consensus Algorithms......Page 78
   1.5.2.1 Weighted Averaging-Based Approaches......Page 79
   1.5.2.3 ADMM Based Approaches......Page 81
   1.5.2.4 New Directions......Page 82
 References......Page 83
2 Five Lectures on Differential Variational Inequalities......Page 93
 2.1 Introduction......Page 94
 2.2 Lecture I: Differential Variational Systems......Page 96
 2.3 Lecture I: DVI in a Multi-Agent Paradigm......Page 98
 2.4 Lecture I: Modeling Breadth......Page 101
 2.5 Lecture I: Solution Concepts and Existence......Page 103
 2.7 Lecture II: The Zeno Phenomenon......Page 106
 2.8 Lecture II: Non-Zenoness of Complementarity Systems......Page 107
  2.8.1 Solution Expansion......Page 108
 2.9 Lecture II: Summary......Page 113
 2.10 Lecture III: Numerical Time-Stepping......Page 114
 2.11 Lecture III: The LCS......Page 117
 2.12 Lecture III: Boundary-Value Problems......Page 119
 2.14 Lecture IV: Linear-Quadratic Optimal Control Problems......Page 123
  2.14.1 The Time-Discretized Subproblems......Page 127
 2.15 Lecture IV: Summary......Page 130
 2.16 Lecture V: Open-Loop Differential Nash Games......Page 131
  2.16.1 The Symmetric Case......Page 132
  2.16.2 The Asymmetric Case......Page 133
  2.16.3 Two Illustrative Examples......Page 135
 2.17 Lecture V: Summary......Page 140
 References......Page 141
3 Parallel and Distributed Successive Convex Approximation Methods for Big-Data Optimization......Page 148
 3.1 Introduction......Page 149
 3.2 Successive Convex Approximation Methods: Basics......Page 152
  3.2.1 Preliminaries......Page 154
  3.2.2 The Majorization-Minimization (MM) Algorithm......Page 160
   3.2.2.1 Discussion on Algorithm 1......Page 163
  3.2.3 The Block Majorization-Minimization Algorithm......Page 170
   3.2.4.1 Nonconvex Sparse Least Squares......Page 172
   3.2.4.2  Nonnegative Least Squares......Page 178
   3.2.4.3 Sparse Plus Low-Rank Matrix Decomposition......Page 179
   3.2.4.4 Multicast Beamforming......Page 187
  3.2.5 Sources and Notes......Page 189
 3.3 Parallel Successive Convex Approximation Methods......Page 191
  3.3.1 Problem Formulation......Page 192
   3.3.1.1 Some Motivating Applications......Page 193
  3.3.2 Parallel SCA: Vanilla Version......Page 195
   3.3.2.1 Discussion on Algorithm 5......Page 198
  3.3.3 Parallel SCA: Selective Updates......Page 202
   3.3.3.1 Discussion on Algorithm 6......Page 205
   3.3.3.2 Convergence Analysis of Algorithm 6......Page 208
   3.3.4.1 Random-Greedy Schemes......Page 219
   3.3.4.2 Parallel-Cyclic Schemes......Page 220
  3.3.5 Applications......Page 221
   3.3.5.1 Resource Allocation in SISO/MIMO Multiuser Systems......Page 222
   3.3.5.2 LASSO Problem......Page 232
   3.3.5.3 The Logistic Regression Problem......Page 239
   3.3.6.2 Proof of Lemma 3.17......Page 242
   3.3.6.3 Proof of Lemma 3.19......Page 244
  3.3.7 Sources and Notes......Page 245
 3.4 Distributed Successive Convex Approximation Methods......Page 249
  3.4.1 Problem Formulation......Page 251
   3.4.1.1 Some Motivating Applications......Page 252
  3.4.2 Preliminaries: Average Consensus and Tracking......Page 253
   3.4.2.1 Average Consensus Over Undirected Graphs......Page 254
   3.4.2.2 Average Consensus Over Directed Graphs......Page 257
   3.4.2.3 Distributed Tracking of Time-Varying Signals' Average......Page 260
   3.4.2.4 Perturbed Condensed Push-Sum......Page 263
   3.4.2.5 Proof of Theorem 4.11......Page 266
  3.4.3 Distributed SCA Over Time-Varying Digraphs......Page 269
   3.4.3.1 SONATA (Algorithm 10) and Special Cases......Page 275
   3.4.3.2 Proof of Theorem 4.16......Page 279
   3.4.4.1 Distributed Robust Regression......Page 292
   3.4.4.2 Target Localization......Page 295
   3.4.5.1 Distributed Convex Optimization......Page 298
   3.4.5.2 Distributed Nonconvex Optimization......Page 300
 References......Page 303