A Globally Linearly Convergent Method for Large-Scale Pointwise Quadratically Supportable Convex-Concave Saddle Point Problems
Abstract:
We study the Proximal 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.
Biography:
I grew up outside of Granville, Ohio (near Columbus) and attended college at the University of California, Berkeley, where I graduated with honors in Applied Mathematics in 1991 (thesis advisor Hans Bremermann). After college, I took a break from an academic carreer, part spent making documentary films - "The Ride to Wounded Knee" (1992, post-production manager, assistant editor, sound editor), "29 and 7 Strong" (1995, all but narration) - and part spent as a VISTA volunteer building Self-Help homes in Okanagon County, Washington (grant writer, Spanish translator, real-estate purchaser, and ``documentarist"). I returned to Applied Mathematics at the University of Washington in Seattle, where I recieved a MSc in December of 1997, and PhD in June of 2001 under the guidance of James Burke. I was a NASA/GSFC Graduate Student Research Fellow from 1998 to 2001. This experience grew into the central application of my PhD thesis on the theory and practice of numerical algorithms for adaptive optics to be used with the James Webb Space Telescope, Hubble's replacement. After graduation I moved to the University of Göttingen in Germany to join Roland Potthast and Rainer Kress' group at the Institute for Numerical and Applied Mathematics. There I worked on inverse scattering theory and research cooperation with industry partners (July 2001 to April 2003). I was with the Mathematics Department at Simon Fraser University near Vancouver Canada as a PIMS Fellow teaching and doing research on applications of variational and nonsmooth analysis from December 2002 until August of 2004 with Jonathan Borwein and Adrian Lewis. I joined the University of Delaware in 2004 and earned promotion and tenure in 2009 before moving back to Göttingen. I am presently Professor for Continuous Optimization and Variational Analysis at Institut für Numerische und Angewandte Mathematik at the Universität Göttingen.