Block-coordinate primal-dual method for the nonsmooth minimization over linear constraints
arXiv:1801.04782 · doi:10.1007/978-3-319-97478-1_6
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.
arXiv comment25 pages 46 references, 3 tables and 3 figures
References in corpus (11)
- Scikit-learn: Machine Learning in Python
- The Augmented Lagrange Multiplier Method for Exact Recovery of Corrupted Low-Rank Matrices
- Constrained Consensus
- Dual Averaging for Distributed Optimization: Convergence Analysis and Network Scaling
- SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
- ARock: an Algorithmic Framework for Asynchronous Parallel Coordinate Updates
- A first-order primal-dual algorithm with linesearch
- Stochastic Primal-Dual Coordinate Method for Regularized Empirical Risk Minimization
- A Coordinate Descent Primal-Dual Algorithm with Large Step Size and Possibly Non Separable Functions
- The primal-dual hybrid gradient method reduces to a primal method for linearly constrained optimization problems
- Linear convergence of the Randomized Sparse Kaczmarz Method