Jorge Cortés
Professor
Cymer Corporation Endowed Chair
Distributed algorithms for convex network optimization under
non-sparse equality constraints
A. Cherukuri, J. Cortés
Allerton Conference on Communications, Control, and Computing,
Monticello, Illinois, USA, 2016,
pp. 452-459
Abstract
This paper studies a class of network optimization problems where the objective function is the summation of individual agents' convex functions and their decision variables are coupled by linear equality constraints. These constraints are not sparse, meaning that they do not match the pattern of the network adjacency matrix. We propose two approaches to design efficient distributed algorithms to solve the network optimization problem. Our first approach consists of transforming the non-sparse equality constraints into sparse ones by increasing the number of the agents' decision variables, yielding an exact reformulation of the original optimization problem. We discuss two reformulations, based on the addition of consensus variables and of constraint-mismatch variables, and discuss the scalability of the strategies resulting from them. Our second approach consists instead of sparsifying the non-sparse constraints by zeroing some coefficients, yielding an approximate reformulation of the original problem. We formally characterize the gap on the distance between the optimizers of the original and approximated problems as a function of the number of entries made zero in the constraints. Various simulations illustrate our results.
Mechanical and Aerospace Engineering,
University of California, San Diego
9500 Gilman Dr,
La Jolla, California, 92093-0411
Ph: 1-858-822-7930
Fax: 1-858-822-3107
cortes at ucsd.edu
Skype id:
jorgilliyo