## DIMACS TR: 94-19

## Coordination Complexity of Parallel Price-Directive Decomposition

### Authors: Michael D. Grigoriadis, Leonid G. Khachiyan

**
ABSTRACT
**

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