Chambolle-Pock First-Order Primal-Dual Algorithm for Convex Saddle-Point Problems

Chambolle-Pock First-Order Primal-Dual Algorithm for Convex Saddle-Point Problems is a matrix-inversion-free proximal splitting framework introduced by Chambolle and Pock (2011) for solving structured non-smooth convex optimization problems min_{x in X} F(K x) + G(x) via their primal-dual saddle-point formulation min_{x in X} max_{y in Y} <K x, y> + G(x) - F^*(y), where K: X -> Y is a continuous linear operator with operator norm L = ||K|| and F, G are proper, convex, lower-semicontinuous functions with tractable resolvent (proximal) operators (I + sigma partial F^*)^{-1} and (I + tau partial G)^{-1}. Algorithm 1 alternates a dual proximal ascent step y^{n+1} = (I + sigma partial F^*)^{-1}(y^n + sigma K x_bar^n), a primal proximal descent step x^{n+1} = (I + tau partial G)^{-1}(x^n - tau K^* y^{n+1}), and a linear over-relaxation (extrapolation) step x_bar^{n+1} = x^{n+1} + theta*(x^{n+1} - x^n) with theta in [0, 1]. For theta = 1 and tau * sigma * L^2 < 1, Algorithm 1 is algebraically equivalent to a preconditioned Alternating Direction Method of Multipliers (ADMM) with proximal metric M = (1/sigma) I - tau K K^* (Section 4.3) that eliminates linear-system inversions involving K^* K, and Theorem 1 proves that the iterates (x^n, y^n) converge to a saddle point with O(1/N) ergodic primal-dual gap G_{B_1 x B_2}(x_N, y_N) <= D(B_1, B_2) / N, while Algorithms 2 and 3 achieve optimal O(1/N^2) accelerated convergence when G or F^* is uniformly convex (Theorem 2) and O(omega^{N/2}) linear convergence when both G and F^* are uniformly convex (Theorem 3).