Abstract
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 " 2 (0; 1], the proposed derandomized algorithm runs in O(K lnM("2 + ln minfK; Mg) 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.