FAST APPROXIMATION SCHEMES FOR CONVEX-PROGRAMS WITH MANY BLOCKS AND COUPLING CONSTRAINTS

This paper presents block-coordinate descent algorithms for the approximate solution of large structured convex programming problems. The constraints of such problems consist of K disjoint convex compact sets B-k called blocks, and M nonnegative-valued convex block-separable inequalities called coupling or resource constraints. The algorithms are based on an exponential po- tential function reduction technique. It is shown that feasibility as well as min-max resource-sharing problems for such constraints can be solved to a relative accuracy E in O(K ln M(epsilon(-2) + In K)) iterations, each of which solves K block problems to a comparable accuracy, either sequentially or in parallel. The same bound holds for the expected number of iterations of a randomized variant of the algorithm which uniformly selects a random block to process at each iteration. An extension to objective and constraint functions of arbitrary sign is also presented. The above results yield fast approximation schemes for a number of applications such as problems with additively separable functions, generalized concurrent hows with side constraints, linear and nonlinear supply-sharing transportation networks, and deterministic equivalents of certain two-stage stochastic programs. Another consequence of this analysis is that, for a fixed relative accuracy, the approximate solution of matrix games is in NC.