Coordination complexity of parallel Lagrangian decomposition
Michael D. Grigoriadis, Leonid Khachiyan · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 1994
We present polylogarithmically-matching upper and lower bounds on the number of parallel iterations (coordination complexity) for two wide classes of Lagrangian decomposition methods for solving general block-angular convex programs to a fixed accuracy. The lower bounds hold for multicommodity flows and even with an all-powerful coordinator. Our near-optimal upper bounds are valid for two Lagrangian decomposition methods based on the classical logarithmic barrier and the exponential potential functions. The coordination step of either method can be implemented to run in almost linear sequential or logarithmic parallel time in the number of coupling constraints. The choice of which function or method to use depends upon a theoretical characterization of an instance as a weakly- or strongly-coupled problem. Some special cases, including multicommodity flows, and a sublinear-time randomized approximation algorithm for matrix games, will be discussed. We shall also summarize computational results for large minimum-cost multicommodity network flow problems.