# Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

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

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

by Fan Jiang, Xingju Cai, Zhongming Wu and Deren Han
Math. Comp. 90 (2021), 1227-1262 Request permission

## 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
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
• 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
• 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).