Acceleration and global convergence of a first-order primal--dual method for nonconvex problems

Abstract

The primal--dual hybrid gradient method (PDHGM, also known as the Chambolle--Pock method) has proved very successful for convex optimization problems involving linear operators arising in image processing and inverse problems. In this paper, we analyze an extension to nonconvex problems that arise if the operator is nonlinear. Based on the idea of testing, we derive new step length parameter conditions for the convergence in infinite-dimensional Hilbert spaces and provide acceleration rules for suitably (locally and/or partially) monotone problems. Importantly, we prove linear convergence rates as well as global convergence in certain cases. We demonstrate the efficacy of these step length rules for PDE-constrained optimization problems.

References in corpus (4)

• Inertial Proximal Alternating Linearized Minimization (iPALM) for Nonconvex and Nonsmooth Problems
• A primal-dual hybrid gradient method for non-linear operators with applications to MRI
• Primal-dual extragradient methods for nonlinear nonsmooth PDE-constrained optimization
• Block-proximal methods with spatially adapted acceleration

Cited by in corpus (8)

• Relaxed Gauss-Newton methods with applications to electrical impedance tomography
• Primal-dual proximal splitting and generalized conjugation in non-smooth non-convex optimization
• First-order primal-dual methods for nonsmooth nonconvex optimisation
• Linearly convergent bilevel optimization with single-step inner methods
• An Extended Primal-Dual Algorithm Framework for Nonconvex Problems with Application to Nonlinear Imaging
• Optimal control of the principal coefficient in a scalar wave equation
• A nonsmooth primal-dual method with interwoven PDE constraint solver
• Online optimisation for dynamic electrical impedance tomography