A Double Extrapolation Primal-Dual Algorithm for Saddle Point Problems
- PDF / 1,264,905 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 218 Views
A Double Extrapolation Primal-Dual Algorithm for Saddle Point Problems Kai Wang1 · Hongjin He2 Received: 23 January 2020 / Revised: 14 August 2020 / Accepted: 3 October 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The first-order primal-dual algorithms have received much considerable attention in the literature due to their quite promising performance in solving large-scale image processing models. In this paper, we consider a general saddle point problem and propose a double extrapolation primal-dual algorithm, which employs the efficient extrapolation strategy for both primal and dual variables. It is remarkable that the proposed algorithm enjoys a unified framework including several existing efficient solvers as special cases. Another exciting property is that, under quite flexible requirements on the involved extrapolation parameters, our algorithm is globally convergent to a saddle point of the problem under consideration. Moreover, the worst case O(1/t) convergence rate in both ergodic and nonergodic senses, and the linear convergence rate can be established for more general cases, where t counts the iteration. Some computational results on solving image deblurring, image inpainting and the nearest correlation matrix problems further show that the proposed algorithm is efficient, and performs better than some existing first-order solvers in terms of taking less iterations and computing time in some cases. Keywords Saddle point problem · Primal-dual algorithm · Extrapolation · Linear convergence rate · Image deblurring · Image inpainting Mathematics Subject Classification 65K15 · 49J40 · 90C25
1 Introduction In this paper, we consider a saddle-point optimization model frequently arising from machine/statistical learning, zero-sum games, and image processing, e.g., see [3,6,9,13,15,
B
Hongjin He [email protected] Kai Wang [email protected]
1
Department of Mathematics, School of Science, Nanjing University of Science and Technology, Xiaolingwei 200, Nanjing 210094, China
2
Department of Mathematics, School of Science, Hangzhou Dianzi University, Hangzhou 310018, China 0123456789().: V,-vol
123
30
Page 2 of 30
Journal of Scientific Computing
(2020) 85:30
19,25], to name just a few. Mathematically, the saddle-point optimization problem takes the form of min max (x, y) := θ1 (x) − y, Ax − θ2 (y), x∈X y∈Y
(1.1)
where A ∈ Rm×n is a given matrix; X and Y are two nonempty, closed and convex subsets of Rn and Rm , respectively; θ1 (·) : Rn → R ∪ {+∞} and θ2 (·) : Rm → R ∪ {+∞} are proper, lower semicontinuous convex functions; ·, · denotes the standard inner product of vectors; and · is the Euclidean norm. Notice that the solution set of (1.1) is assumed to be nonempty throughout this paper. In the literature, the Primal-Dual Hybrid Gradient (PDHG) proposed in [35] is one of the most popular approaches for solving problem (1.1) with applications to image sciences. Given a pair of starting points (x 0 , y 0 ), the iterative scheme of PDHG reads as
Data Loading...
