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

Understand

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.