GOLDEN RATIO PRIMAL-DUAL ALGORITHM WITH LINESEARCH | |
Chang, Xiao-kai2; Yang, Junfeng3; Zhang, Hongchao1 | |
刊名 | SIAM JOURNAL ON OPTIMIZATION |
2022 | |
卷号 | 32期号:3页码:1584-1613 |
关键词 | saddle point problem golden ratio primal-dual algorithm linesearch acceleration ergodic sublinear convergence linear convergence |
ISSN号 | 1052-6234 |
DOI | 10.1137/21M1420319 |
英文摘要 | The golden ratio primal-dual algorithm (GRPDA) is a new variant of the classical Arrow-Hurwicz method for solving structured convex optimization problems, in which the objective function consists of the sum of two closed proper convex functions, one of which involves a composi-tion with a linear transform. The same as the Arrow-Hurwicz method and the popular primal-dual algorithm (PDA) of Chambolle and Pock, GRPDA is full-splitting in the sense that it does not rely on solving any subproblems or linear system of equations iteratively. Compared with PDA, an im-portant feature of GRPDA is that it permits larger primal and dual stepsizes. However, the stepsize condition of GRPDA requires that the spectral norm of the linear transform is known, which can be difficult to obtain in some applications. Furthermore, constant stepsizes are usually overconservative in practice. In this paper, we propose a linesearch strategy for GRPDA, which not only does not require the spectral norm of the linear transform but also allows adaptive and potentially much larger stepsizes. Within each linesearch step, only the dual variable needs to be updated, and it is thus quite cheap and does not require any extra matrix-vector multiplications for many special yet important applications such as a regularized least-squares problem. Global iterate convergence and O(1/N) ergodic convergence rate results, measured by the function value gap and constraint viola-tions of an equivalent optimization problem, are established, where N denotes the iteration counter. When one of the component functions is strongly convex, faster O(1/N2) ergodic convergence rate results, quantified by the same measures, are established by adaptively choosing some algorithmic parameters. Moreover, when the subdifferential operators of the component functions are strongly metric subregular, a condition that is much weaker than strong convexity, we show that the iterates converge R-linearly to the unique solution. Numerical experiments on matrix game and LASSO problems illustrate the effectiveness of the proposed linesearch strategy. |
WOS研究方向 | Mathematics |
语种 | 英语 |
出版者 | SIAM PUBLICATIONS |
WOS记录号 | WOS:000834106000004 |
内容类型 | 期刊论文 |
源URL | [http://ir.lut.edu.cn/handle/2XXMBERH/159473] |
专题 | 理学院 |
作者单位 | 1.Louisiana State Univ, Dept Math, Baton Rouge, LA 70803 USA 2.Lanzhou Univ Technol, Sch Sci, Lanzhou 730050, Gansu, Peoples R China; 3.Nanjing Univ, Dept Math, Peoples Republ China, Nanjing 210093, Peoples R China; |
推荐引用方式 GB/T 7714 | Chang, Xiao-kai,Yang, Junfeng,Zhang, Hongchao. GOLDEN RATIO PRIMAL-DUAL ALGORITHM WITH LINESEARCH[J]. SIAM JOURNAL ON OPTIMIZATION,2022,32(3):1584-1613. |
APA | Chang, Xiao-kai,Yang, Junfeng,&Zhang, Hongchao.(2022).GOLDEN RATIO PRIMAL-DUAL ALGORITHM WITH LINESEARCH.SIAM JOURNAL ON OPTIMIZATION,32(3),1584-1613. |
MLA | Chang, Xiao-kai,et al."GOLDEN RATIO PRIMAL-DUAL ALGORITHM WITH LINESEARCH".SIAM JOURNAL ON OPTIMIZATION 32.3(2022):1584-1613. |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论