A Golden Ratio Primal–Dual Algorithm for Structured Convex Optimization | |
Chang, Xiaokai1; Yang, Junfeng2 | |
2021-05 | |
发表期刊 | Journal of Scientific Computing |
ISSN | 0885-7474 |
卷号 | 87期号:2 |
摘要 | We design, analyze and test a golden ratio primal–dual algorithm (GRPDA) for solving structured convex optimization problem, where the objective function is the sum of two closed proper convex functions, one of which involves a composition with a linear transform. GRPDA preserves all the favorable features of the classical primal–dual algorithm (PDA), i.e., the primal and the dual variables are updated in a Gauss–Seidel manner, and the per iteration cost is dominated by the evaluation of the proximal point mappings of the two component functions and two matrix-vector multiplications. Compared with the classical PDA, which takes an extrapolation step, the novelty of GRPDA is that it is constructed based on a convex combination of essentially the whole iteration trajectory. We show that GRPDA converges within a broader range of parameters than the classical PDA, provided that the reciprocal of the convex combination parameter is bounded above by the golden ratio, which explains the name of the algorithm. An O(1 / N) ergodic convergence rate result is also established based on the primal–dual gap function, where N denotes the number of iterations. When either the primal or the dual problem is strongly convex, an accelerated GRPDA is constructed to improve the ergodic convergence rate from O(1 / N) to O(1 / N2). Moreover, we show for regularized least-squares and linear equality constrained problems that the reciprocal of the convex combination parameter can be extended from the golden ratio to 2 and meanwhile a relaxation step can be taken. Our preliminary numerical results on LASSO, nonnegative least-squares and minimax matrix game problems, with comparisons to some state-of-the-art relative algorithms, demonstrate the efficiency of the proposed algorithms. © 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature. |
关键词 | Convex optimization Game theory Mathematical transformations Matrix algebra Regression analysis Convex combinations Ergodic convergence Matrix vector multiplication Nonnegative least squares Number of iterations Objective functions Regularized least squares Structured convex optimizations |
DOI | 10.1007/s10915-021-01452-9 |
收录类别 | EI ; SCIE |
语种 | 英语 |
WOS研究方向 | Mathematics |
WOS类目 | Mathematics, Applied |
WOS记录号 | WOS:000631706100001 |
出版者 | Springer |
EI入藏号 | 20211310151722 |
EI主题词 | Iterative methods |
EI分类号 | 921 Mathematics ; 922.1 Probability Theory ; 922.2 Mathematical Statistics |
来源库 | WOS |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | https://ir.lut.edu.cn/handle/2XXMBERH/148384 |
专题 | 理学院 |
通讯作者 | Yang, Junfeng |
作者单位 | 1.Lanzhou Univ Technol, Sch Sci, Lanzhou, Gansu, Peoples R China; 2.Nanjing Univ, Dept Math, Nanjing, Peoples R China |
第一作者单位 | 理学院 |
通讯作者单位 | 理学院 |
第一作者的第一单位 | 理学院 |
推荐引用方式 GB/T 7714 | Chang, Xiaokai,Yang, Junfeng. A Golden Ratio Primal–Dual Algorithm for Structured Convex Optimization[J]. Journal of Scientific Computing,2021,87(2). |
APA | Chang, Xiaokai,&Yang, Junfeng.(2021).A Golden Ratio Primal–Dual Algorithm for Structured Convex Optimization.Journal of Scientific Computing,87(2). |
MLA | Chang, Xiaokai,et al."A Golden Ratio Primal–Dual Algorithm for Structured Convex Optimization".Journal of Scientific Computing 87.2(2021). |
条目包含的文件 | 条目无相关文件。 |
个性服务 |
查看访问统计 |
谷歌学术 |
谷歌学术中相似的文章 |
[Chang, Xiaokai]的文章 |
[Yang, Junfeng]的文章 |
百度学术 |
百度学术中相似的文章 |
[Chang, Xiaokai]的文章 |
[Yang, Junfeng]的文章 |
必应学术 |
必应学术中相似的文章 |
[Chang, Xiaokai]的文章 |
[Yang, Junfeng]的文章 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论