Chambolle–Pock algorithm

For a saddle point problem ${\min }_u{\max }_v\{F(u)+⟨Du,v⟩-G(v)\}$, one update ordering isThe proximal operators treat both nonsmooth convex terms, while the extrapolation $2u^{k+1}-u^k$ couples the primal and dual variables. The primal objective is $F(u)+G^{\ast }(Du)$, with $G^{\ast }$ the convex conjugate. A dual-first ordering is obtained by exchanging roles; consistent indexing is needed when comparing the formulas.

For proper lower semicontinuous convex functions on finite-dimensional Hilbert spaces, a nonempty saddle point set, and constant positive steps satisfying the displayed inequality, the primal-dual hybrid gradient method with extrapolation parameter one converges to a saddle point. The strict condition controls the bilinear coupling by the operator norm. It does not remove the need for existence of a saddle point. The fixed-step theorem and assumptions are recalled in Malitsky and Pock, A first-order primal-dual algorithm with linesearch, Section 1.