在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2023, Vol. 40 ›› Issue (2): 321-331.doi: 10.3969/j.issn.1005-3085.2023.02.011

• • 上一篇    下一篇

基于序列线性组合的原始–对偶算法

颜鲁林1,   常小凯2   

  1. 1. 甘肃中医药大学理科教学部，定西 743000
    2. 兰州理工大学理学院，兰州 730050
  • 收稿日期:2021-03-15 接受日期:2021-08-13 出版日期:2023-04-15 发布日期:2023-06-20
  • 基金资助:
    国家自然科学基金 (12161053)；甘肃省杰出青年基金 (22JR5RA223)；甘肃省高等学校创新能力提升项目 (2021B-385).

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

PDF (PC)

51

摘要： 双线性鞍点问题及其对应的原问题和对偶问题在信号图像处理、机器学习、统计和高维数据处理等领域具有重要的应用，原始对偶算法是求解该类问题的有效算法。利用序列的线性组合技术，改进了Chambolle-Pock原始对偶算法子问题的求解，提出了一种求解双线性鞍点问题的新原始对偶算法。该算法也是Arrow-Hurwicz算法的修正，在子问题求解中将线性组合和经典的外插技术进行结合，得到了更一般的收敛性。利用变分分析证明了算法的收敛性和遍历$\mathcal{O}(1/N)$收敛率，获得了保证算法收敛的步长和组合参数取值范围，求解非负最小二乘和Lasso问题的数值实验验证了算法的有效性。

关键词: 双线性鞍点问题, 原始–对偶算法, 序列的线性组合, 收敛率

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

中图分类号: