Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
复制标题
具有多块和耦合约束的凸规划的快速逼近方案
DOI：
--
复制
发表时间：
1994
影响因子：
3.1
通讯作者：
L. Khachiyan
中科院分区：
文献类型：
--
作者：
M. Grigoriadis;L. Khachiyan
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( Kln 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 approximatio...
