Convergence of the Chambolle-Pock Algorithm in the Absence of
  Monotonicity
Brecht Evens Puya Latafat Panagiotis Patrinos
The Chambolle-Pock algorithm (CPA), also known as the primal-dual hybrid
gradient method (PDHG), has surged in popularity in the last decade due to its
success in solving convex/monotone structured problems. This work provides
convergence results for problems with varying degrees of (non)monotonicity,
quantified through a so-called oblique weak Minty condition on the associated
primal-dual operator. Our results reveal novel stepsize and relaxation
parameter ranges which do not only depend on the norm of the linear mapping,
but also on its other singular values. In particular, in nonmonotone settings,
in addition to the classical stepsize conditions for CPA, extra bounds on the
stepsizes and relaxation parameters are required. On the other hand, in the
strongly monotone setting, the relaxation parameter is allowed to exceed the
classical upper bound of two. Moreover, sufficient convergence conditions are
obtained when the individual operators belong to the recently introduced class
of semimonotone operators. Since this class of operators encompasses many
traditional operator classes including (hypo)- and co(hypo)monotone operators,
this analysis recovers and extends existing results for CPA. Several examples
are provided for the aforementioned problem classes to demonstrate and
establish tightness of the proposed stepsize ranges.