Relaxation methods for strictly convex regularizations of piecewise linear programs (Q1273445)

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