Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Approximate first-order primal-dual algorithms for saddle point problems


Authors: Fan Jiang, Xingju Cai, Zhongming Wu and Deren Han
Journal: Math. Comp. 90 (2021), 1227-1262
MSC (2020): Primary 65K05, 65K10, 90C25
DOI: https://doi.org/10.1090/mcom/3610
Published electronically: February 4, 2021
MathSciNet review: 4232223
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: We propose two approximate versions of the first-order primal-dual algorithm (PDA) to solve a class of convex-concave saddle point problems. The introduced approximate criteria are easy to implement in the sense that they only involve the subgradient of a certain function at the current iterate. The first approximate PDA solves both subproblems inexactly and adopts the absolute error criteria, which are based on non-negative summable sequences. Assuming that one of the PDA subproblems can be solved exactly, the second approximate PDA solves the other subproblem approximately and adopts a relative error criterion. The relative error criterion only involves a single parameter in the range of $[0, 1)$, which makes the method more applicable. For both versions, we establish the global convergence and $O(1/N)$ convergence rate measured by the iteration complexity, where $N$ counts the number of iterations. For the inexact PDA with absolute error criteria, we show the accelerated $O(1/N^2)$ and linear convergence rate under the assumptions that a part of the underlying functions and both underlying functions are strongly convex, respectively. Then, we prove that these inexact criteria can also be extended to solve a class of more general problems. Finally, we perform some numerical experiments on sparse recovery and image processing problems. The results demonstrate the feasibility and superiority of the proposed methods.


References [Enhancements On Off] (What's this?)

References

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2020): 65K05, 65K10, 90C25

Retrieve articles in all journals with MSC (2020): 65K05, 65K10, 90C25


Additional Information

Fan Jiang
Affiliation: School of Mathematical Sciences, Jiangsu Key Lab for NSLSCS, Nanjing Normal University, Nanjing 210023, People’s Republic of China
MR Author ID: 1266812
Email: 15905154902@163.com

Xingju Cai
Affiliation: School of Mathematical Sciences, Jiangsu Key Lab for NSLSCS, Nanjing Normal University, Nanjing 210023, People’s Republic of China
ORCID: 0000-0002-6957-477X
Email: caixingju@njnu.edu.cn

Zhongming Wu
Affiliation: School of Management Science and Engineering, Nanjing University of Information Science and Technology, Nanjing 210044, People’s Republic of China
MR Author ID: 1246723
Email: wuzm@nuist.edu.cn

Deren Han
Affiliation: LMIB, School of Mathematical Sciences, Beihang University, Beijing 100191, People’s Republic of China
MR Author ID: 664477
Email: handr@buaa.edu.cn

Keywords: First-order primal-dual algorithm, saddle point problems, convex optimization, inexact criteria, global convergence
Received by editor(s): June 16, 2019
Received by editor(s) in revised form: March 14, 2020, May 28, 2020, and October 5, 2020
Published electronically: February 4, 2021
Additional Notes: The first author was supported by the Postgraduate Research & Practice Innovation Program of Jiangsu Province (No. KYCX20_1163). The second author was partially supported by the Natural Science Foundation of China (Nos. 11871279, 11571178). The third author was partially supported by the Natural Science Foundation of China (No. 12001286) and the Startup Foundation for Introducing Talent of NUIST (No. 2020r003). The fourth author was partially supported by the Natural Science Foundation of China (Nos. 11625105, 11926358).
Article copyright: © Copyright 2021 American Mathematical Society