Approximate Structured Optimization by Cyclic Block-Coordinate Descent
Approximate Structured Optimization by Cyclic Block-Coordinate Descent
复制标题
循环块坐标下降的近似结构化优化
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
M. Grigoriadis
中科院分区：
文献类型：
--
作者：
J. Villavicencio;M. Grigoriadis
A uniform randomized exponential-potential block-coordinate descent method for the approximate solution of block-angular convex resource-sharing programs was analyzed in [5] and for the linear case in [14]. The former method is rendered deterministic by replacing its random block selection by arbitrary sweeps of its block coordinates, akin to classical implementations of Gauss-Seidel relaxation and coordinate descent in unconstrained optimization, recently used in concurrent network flows [15]. The general block-angular model consists of K disjoint convex compact sets (“blocks”) and M nonnegative convex block-separable inequalities (“coupling constraints”). It is shown that for linear coupling constraints and for a given but arbitrary relative accuracy e ∈ (0, 1], the proposed derandomized algorithm runs in O(K ln M(e −2 + ln min{K, M}) coordination steps or block optimizations, which is lower than all other existing bounds. It is also shown that this bound on coordination steps also applies to a reformulation of the above general nonlinear problem.
