A globally linearly convergent method for pointwise quadratically supportable convex–concave saddle point problems

摘要

AbstractWe study theProximal Alternating Predictor–Corrector(PAPC) algorithm introduced recently by Drori, Sabach and Teboulle to solve nonsmooth structured convex–concave saddle point problems consisting of the sum of a smooth convex function, a finite collection of nonsmooth convex functions and bilinear terms. We introduce the notion of pointwise quadratic supportability, which is a relaxation of a standard strong convexity assumption and allows us to show that the primal sequence is R-linearly convergent to an optimal solution and the primal-dual sequence is globally Q-linearly convergent. We illustrate the proposed method on total variation denoising problems and on locally adaptive estimation in signal/image deconvolution and denoising with multiresolution statistical constraints.]]>