DIMACS TR: 94-19

Coordination Complexity of Parallel Price-Directive Decomposition

Authors: Michael D. Grigoriadis, Leonid G. Khachiyan


Parallel price directive decomposition (PDD) methods for the approximate solution of block-angular convex resource sharing problems are considered. This general model in structured optimization consists of $K$ nonempty disjoint compact sets called ``blocks'' and $M$ nonnegative-valued convex ``coupling'' inequalities. It has a number of applications in combinatorial optimization, network flows, scheduling, communication networks, engineering design, and finance.

This paper studies the coordination complexity of PDD approximation methods, i.e., the number of iterations required to solve the general resource sharing problem to a fixed relative accuracy, as a function of $K$ and $M$. First, a simple PDD method based on the classical logarithmic potential function is presented and analyzed. For a fixed accuracy, its coordination complexity is shown to be $O(M\ln M)$, which is within a logarithmic factor of the best possible bound for any PDD method that works with the original blocks. An important property of the logarithmic-potential PDD method is that its coordination complexity depends neither on the ``width'' nor on the dimension of the blocks. Second, polylogarithmically-matching upper and lower coordination complexity bounds are presented for a wider class of PDD methods in which each block can be partially restricted by the coupling constraints. The upper bound for this class of PDD is obtained by a combined method, which uses either the logarithmic or the exponential potential function, depending on the number of coupling constraints per block.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-19.ps

DIMACS Home Page