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.

Review text

The authors propose a randomized block-coordinate extension of the Chambolle-Pock primal-dual proximal-point type algorithm for computationally solving a class of bilevel optimization problems that generalize the optimization problems consisting in minimizing convex and separable nonsmooth functions subject to linear constraints. Some other problems where the algorithm can be applied are mentioned: linear programming, composite minimization, distributed optimization, inverse problems. The convergence of the method is guaranteed under quite weak assumptions that do not involve usually standard additional hypotheses like smoothness or strong convexity of the objective function or full-rank condition on the involved matrix and permit applying the algorithm even to misspecified or noisy systems. Possible generalizations concerning adding strong convexity hypotheses or additional smooth terms to the objective function, or parallelization are briefly discussed, too, being followed by some numerical experiments on basis pursuit with and without noise and robust principal component analysis where the new method outperforms existing ones from the literature. For the entire collection see [Zbl 1407.90006].

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)