FREE-STEERING RELAXATION METHODS FOR PROBLEMS WITH STRICTLY CONVEX COSTS AND LINEAR CONSTRAINTS

We consider dual coordinate ascent methods for minimizing a strictly c onvex (possibly nondifferentiable) function subject to linear constrai nts. Such methods are useful in large-scale applications (e.g., entrop y maximization, quadratic programming, network flow), because they are simply, can exploit sparsity and in certain cases are highly parallel izable. We establish their global convergence under weak conditions an d a free-steering order of relaxation. Previous comparable results wer e restricted to special problems with separable costs and equality con straints. Our convergence framework unifies to a certain extent the ap proaches of Bregman. Censor and Lent, De Pierro and lusem, and Luo and Tseng, and complements that of Bertsekas and Tseng.