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

DOI10.1007/978-3-319-97478-1_6MaRDI QIDQ2415202zbMATH OpenOpenAlexFDO

Authors D. Russell Luke, Yura Malitsky

Publication date 21 May 2019

Full work available at URL https://arxiv.org/abs/1801.04782

zbMATH Keywords

basis pursuitbilevel optimization problemsconstrained optimization problemscoordinate methodsfirst order algorithmsnoisy systemsprimal-dual algorithmsproximal-point methodsrandomized methodssaddle-point problems

Mathematics Subject Classification ID

Numerical methods involving duality (49M29) Numerical optimization and variational techniques (65K10) Complexity and performance of numerical algorithms (65Y20) Convex programming (90C25) Optimality conditions and duality in mathematical programming (90C46)

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.

Recommendations

• A coordinate gradient descent method for nonsmooth separable minimization
• Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
• Block-coordinate and incremental aggregated proximal gradient methods for nonsmooth nonconvex problems
• A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
• A coordinate gradient descent method for nonsmooth nonseparable minimization

Cited in

(11)

• Block-coordinate gradient descent method for linearly constrained nonsmooth separable optimization
• Accelerated primal-dual proximal block coordinate updating methods for constrained convex optimization
• Block coordinate descent for smooth nonconvex constrained minimization
• Randomized primal-dual proximal block coordinate updates
• A coordinate descent homotopy method for linearly constrained nonsmooth convex minimization
• A dual method for minimizing a nonsmooth objective over one smooth inequality constraint
• A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization
• On the convergence of stochastic primal-dual hybrid gradient
• Primal-dual extragradient methods for nonlinear nonsmooth PDE-constrained optimization
• Primal-Dual First-Order Methods for Affinely Constrained Multi-block Saddle Point Problems
• A distributed primal-dual hybrid gradient algorithm for fair resource allocation

This page was built for publication: Block-coordinate primal-dual method for nonsmooth minimization over linear constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2415202)