Distributed Optimization over Networks
Tuesday, June 3, 2014 - 9:00am - 10:30am
The advances in wired and wireless technology necessitated the development of theory, models and tools to cope with new challenges posed by large-scale optimization problems over networks. The classical optimization works under the premise that all problem data is available to some central entity. This premise does not apply to large networked systems where typically each agent (node) in the network has access to its private local information and has a local view of the network only. The lectures will cover the development of such distributed computational models for time-varying networks, both deterministic and stochastic. For each of these network dynamics, distributed algorithms for convex constrained minimization and Nash-equilibrium problems will be considered including direct primal methods and primal-dual methods, including their extensions for solving the stochastic counterparts of the aforementioned problems. The development of these methods combines optimization techniques with graph theory and the non-negative matrix theory, which model the network aspect. The lectures will provide some basic background theory on graphs, graph Laplacians and their properties, and the convergence results for stochastic matrix sequences. Using the graph models and optimization techniques, the convergence and convergence rate analysis of the methods will be presented, of which the convergence rate results will demonstrate the dependence of the method’s performance with respect to the problem and the network properties, such as the network capability to diffuse the information.