Events Calendar

Center for Systems and Control (CSC@USC) and Ming Hsieh Institute for Electrical Engineering

Speaker: Angelia Nedich, Arizona State University

Talk Title: Fast Distributed Algorithms for Optimization and Resource Sharing in Networks

Abstract: We will discuss the problems of distributed optimization over graphs. For the case of undirected graphs, we introduce a distributed algorithm, referred to as DIGing, which is a combination of a distributed inexact gradient method and a gradient-tracking mechanism. The DIGing algorithm uses doubly stochastic mixing matrices and employs fixed step-sizes and, yet, drives all agents' iterates to a common global minimizer. When the graphs are directed, in which case the implementation of doubly stochastic mixing matrices is unrealistic, we construct an algorithm that incorporates the push-sum protocol into the DIGing structure, thus obtaining Push-DIGing algorithm. Under the strong convexity assumption for the objective function, we prove that both algorithms converge at R-linear (geometric) rates, as long as the step-sizes do not exceed some upper bounds. We establish explicit convergence rate estimates for the convergence rates. When the graph is undirected, we show that the convergence rate of DIGing scales polynomially in the number of agents. We also provide some numerical experiments to demonstrate the efficacy of the proposed algorithms and to validate our theoretical findings. We then discuss the variants of these algorithms for resource allocation problems in graphs.

Biography: Angelia Nedich holds a Ph.D. from Moscow State University, Moscow, Russia, in Computational Mathematics and Mathematical Physics (1994), and a Ph.D. from Massachusetts Institute of Technology, Cambridge, USA in Electrical and Computer Science Engineering (2002). She has worked as a senior engineer in BAE Systems North America, Advanced Information Technology Division at Burlington, MA. She is the recipient of an NSF CAREER Award 2007 in Operations Research for her work in distributed multi-agent optimization. She is a recipient (jointly with her co-authors) of the Best Paper Award at the Winter Simulation Conference 2013 and the Best Paper Award at the International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks (WiOpt) 2015 (with co-authors). She has served as Associate Editor for IEEE Transactions on Automatic Control and Transactions of Control of Network Systems. She is currently serving on Editorial Board of SIAM Journal on Optimization and for INFORMS Operations Research. Her current interest is in large-scale optimization, games, control and information processing in networks.

Host: Mihailo Jovanovic, mihailo@usc.edu

Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248

Audiences: Everyone Is Invited

Contact: Gerrielyn Ramos