AN EXPONENTIAL-FUNCTION REDUCTION METHOD FOR BLOCK-ANGULAR CONVEX-PROGRAMS

An exponential potential-function reduction algorithm for convex block-angular optimization problems is described. These problems are characterized by K disjoint convex compact sets called blocks and M nonnegative-valued convex block-separable coupling inequalities with a nonempty interior. A given convex block-separable function is to be minimized. Concurrent, minimum-cost, and generalized multicommodity network flow problems are important special cases of this model. The method reduces the optimization problem to two resource-sharing problems. The first of these problems is solved to obtain a feasible solution interior to the coupling constraints. Starting from this solution, the algorithm proceeds to solve the second problem on the original constraints, but with a modified exponential potential function. The method is shown to produce an c-approximate solution in O(K(ln M)(epsilon(-2) + In K)) iterations, provided that there is a feasible solution sufficiently interior to the coupling inequalities. Each iteration consists of solving a subset of independent block problems, followed by a simple coordination step. Computational experiments with a set of large linear concurrent and minimum-cost multicommodity network flow problems suggest that the method can be practical for computing fast approximations to large instances. (C) 1995 John Wiley and Sons, Inc.