DUAL ASCENT METHODS FOR PROBLEMS WITH STRICTLY CONVEX COSTS AND LINEAR CONSTRAINTS - A UNIFIED APPROACH

Problems of the form min {f(x)|Ex≥b}, where f is a strictly convex (possibly nondifferentiable) function and E and b are, respectively, a matrix and a vector, are considered. A popular method for solving special cases of this problem is to dualize the constraints Ex≥ b to obtain a differentiable maximization problem and then apply an iterative ascent method to solve it. This method is simple and can exploit sparsity, thus making it ideal for large-scale optimization and, in certain cases, for parallel computation. Despite its simplicity, however, convergence of this method has been shown only under certain very restrictive conditions and only for certain special cases. In this paper a block coordinate ascent method is presented for solving the problem that contains as special cases both dual coordinate ascent methods and dual gradient methods. It is shown, under certain mild assumptions, that this method converges. Also the line searches are allowed to be inexact and, when f is separable, can be done in parallel.