Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
Authors:
- Michael D. GrigoriadisMGMichael D. Grigoriadis
- Leonid G. KhachiyanLKLeonid G. Khachiyan
- 1 February 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 4 (1) , 86-107
Abstract
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 potential function reduction technique. It is shown that feasibility as well as min-mix resource-sharing problems for such constraints can be solved to a relative accuracy $\varepsilon$ in $O( K\ln M ( \varepsilon^{ - 2} + \ln 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 flows 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$.
Keywords
This publication has 16 references indexed in Scilit:
- The maximum concurrent flow problemJournal of the ACM, 1990
- A Fast Parametric Maximum Flow Algorithm and ApplicationsSIAM Journal on Computing, 1989
- An O(n) algorithm for quadratic knapsack problemsOperations Research Letters, 1984
- The flow deviation method: An approach to store‐and‐forward communication network designNetworks, 1973
- A partitioning algorithm for the multicommodity network flow problemMathematical Programming, 1972
- Primal partition programming for block diagonal matricesNumerische Mathematik, 1964
- Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of ResourcesOperations Research, 1963
- The Decomposition Algorithm for Linear ProgramsEconometrica, 1961
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956
- An Iterative Method of Solving a GameAnnals of Mathematics, 1951