ShanghaiTech University Knowledge Management System
CONVERGENCE ANALYSIS OF APPROXIMATE PRIMAL SOLUTIONS IN DUAL FIRST-ORDER METHODS | |
2016 | |
发表期刊 | SIAM JOURNAL ON OPTIMIZATION |
ISSN | 1052-6234 |
卷号 | 26期号:4页码:2430-2467 |
发表状态 | 已发表 |
DOI | 10.1137/15M1008956 |
摘要 | Dual first-order methods are powerful techniques for large-scale convex optimization. Although an extensive research effort has been devoted to studying their convergence properties, explicit convergence rates for the primal iterates have essentially only been established under global Lipschitz continuity of the dual gradient. This is a rather restrictive assumption that does not hold for several important classes of problems. In this paper, we demonstrate that primal convergence rate guarantees can also be obtained when the dual gradient is only locally Lipschitz. The class of problems that we analyze admits general convex constraints including nonlinear inequality, linear equality, and set constraints. As an approximate primal solution, we take the minimizer of the Lagrangian computed when evaluating the dual gradient. We first derive error bounds for this approximate primal solution in terms of the errors of the dual variables. Then we establish convergence rates of the dual variables when dual problems with locally Lipschitz gradient are solved using a projected gradient method and when dual problems with Lipschitz gradient over the dual feasible set are solved using fast gradient methods. By combining these results, we show that the suboptimality and infeasibility of the approximate primal solution at iteration k are no worse than O(1/v k) when the projected dual gradient method is used and O(1/root k) when a fast dual gradient method is used. |
关键词 | dual optimization first-order methods primal convergence |
收录类别 | SCI ; EI |
语种 | 英语 |
资助项目 | Shanghai Pujiang Program[16PJ1406400] |
WOS研究方向 | Mathematics |
WOS类目 | Mathematics, Applied |
WOS记录号 | WOS:000391853600018 |
出版者 | SIAM PUBLICATIONS |
EI入藏号 | 20165203190808 |
EI主题词 | Convex optimization ; Error analysis |
EI分类号 | Numerical Methods:921.6 |
WOS关键词 | DECOMPOSITION ; OPTIMIZATION ; ALGORITHM |
原始文献类型 | Article |
引用统计 | |
文献类型 | 期刊论文 |
条目标识符 | https://kms.shanghaitech.edu.cn/handle/2MSLDSTB/1970 |
专题 | 信息科学与技术学院_PI研究组_陆疌组 |
通讯作者 | Lu, Jie |
作者单位 | 1.ShanghaiTech Univ, Sch Informat Sci & Technol, Shanghai 200031, Peoples R China 2.KTH Royal Inst Technol, Sch Elect Engn, ACCESS Linnaeus Ctr, Dept Automat Control, SE-10044 Stockholm, Sweden |
第一作者单位 | 信息科学与技术学院 |
通讯作者单位 | 信息科学与技术学院 |
第一作者的第一单位 | 信息科学与技术学院 |
推荐引用方式 GB/T 7714 | Lu, Jie,Johansson, Mikael. CONVERGENCE ANALYSIS OF APPROXIMATE PRIMAL SOLUTIONS IN DUAL FIRST-ORDER METHODS[J]. SIAM JOURNAL ON OPTIMIZATION,2016,26(4):2430-2467. |
APA | Lu, Jie,&Johansson, Mikael.(2016).CONVERGENCE ANALYSIS OF APPROXIMATE PRIMAL SOLUTIONS IN DUAL FIRST-ORDER METHODS.SIAM JOURNAL ON OPTIMIZATION,26(4),2430-2467. |
MLA | Lu, Jie,et al."CONVERGENCE ANALYSIS OF APPROXIMATE PRIMAL SOLUTIONS IN DUAL FIRST-ORDER METHODS".SIAM JOURNAL ON OPTIMIZATION 26.4(2016):2430-2467. |
条目包含的文件 | 下载所有文件 | |||||
文件名称/大小 | 文献类型 | 版本类型 | 开放类型 | 使用许可 |
个性服务 |
查看访问统计 |
谷歌学术 |
谷歌学术中相似的文章 |
[Lu, Jie]的文章 |
[Johansson, Mikael]的文章 |
百度学术 |
百度学术中相似的文章 |
[Lu, Jie]的文章 |
[Johansson, Mikael]的文章 |
必应学术 |
必应学术中相似的文章 |
[Lu, Jie]的文章 |
[Johansson, Mikael]的文章 |
相关权益政策 |
暂无数据 |
收藏/分享 |
修改评论
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。