Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints

Abstract

We consider the problem of minimizing a convex, separable, nonsmooth function subject to linear constraints. The numerical method we propose is a block-coordinate extension of the Chambolle-Pock primal-dual algorithm. We prove convergence of the method without resorting to assumptions like smoothness or strong convexity of the objective, full-rank condition on the matrix, strong duality or even consistency of the linear system. Freedom from imposing the latter assumption permits convergence guarantees for misspecified or noisy systems.

25 pages 46 references, 3 tables and 3 figures

References in corpus (3)

• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
• Linear convergence of the Randomized Sparse Kaczmarz Method

Cited by in corpus (2)

• The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
• A privacy-preserving distributed computational approach for distributed locational marginal prices