RELAXATION METHODS FOR STRICTLY CONVEX REGULARIZATIONS OF PIECEWISE-LINEAR PROGRAMS

We give an algorithm for minimizing the sum of a strictly convex funct ion and a convex piecewise linear function. It extends several dual co ordinate ascent methods for large-scale linearly constrained problems that occur in entropy maximization, quadratic programming, and network flows. In particular, it may solve exact penalty versions of such (po ssibly inconsistent) problems, and subproblems of bundle methods for n ondifferentiable optimization. It is simple, can exploit sparsity, and in certain cases is highly parallelizable. Its global convergence is established in the recent framework of B-functions (generalized Bregma n functions).