Association Journal of CSIAM
Supervised by Ministry of Education of PRC
Sponsored by Xi'an Jiaotong University
ISSN 1005-3085  CN 61-1269/O1

Chinese Journal of Engineering Mathematics ›› 2023, Vol. 40 ›› Issue (2): 321-331.doi: 10.3969/j.issn.1005-3085.2023.02.011

Previous Articles     Next Articles

A First-order Primal-dual Algorithm Using Sequence Linear Combination

YAN Lulin1,   CHANG Xiaokai2   

  1. 1. Department of Science Teaching, Gansu University of Chinese Medicine, Dingxi 743000
    2. School of Science, Lanzhou University of Technology, Lanzhou 730050
  • Received:2021-03-15 Accepted:2021-08-13 Online:2023-04-15 Published:2023-06-20
  • Supported by:
    The National Science Foundation of China (12161053); the Natural Science Foundation for Distinguished Young Scholars of Gansu Province (22JR5RA223); the Innovation Ability Improvement Project of Gansu Province (2021B-385).

Abstract:

Bilinear saddle point problem has numerous applications in signal and image processing, machine learning, statistics, high dimensional data analysis, and so on, which be solved efficiently by primal dual algorithms (PDA). By using sequence linear combination, a novel first-order primal-dual algorithm is presented for solving the bilinear saddle point problem. The proposed method improves the Chambolle-Pock PDA and can be seems as a modification of Arrow-Hurwicz method, which combines the linear combination with classic extrapolation technology in subproblems. An $\mathcal{O}(1/N)$ ergodic convergence rate result is derived based on the primal-dual gap function, where $N$ denotes the number of iterations. The preliminary numerical results on the nonnegative least-squares and Lasso problems, with comparisons to some state-of-the-art relative algorithms, demonstrate the efficiency of the proposed algorithm.

Key words: bilinear saddle-point problem, primal-dual algorithm, sequence linear combination, convergence rate

CLC Number: