IMPROVED POINTWISE ITERATION-COMPLEXITY OF A REGULARIZED ADMM AND OF A REGULARIZED NON-EUCLIDEAN HPE FRAMEWORK

作     者：Goncalves, Max L. N. Melo, Jefferson G. Monteiro, Renato D. C. 

作者机构：Univ Fed Goias Inst Math & Stat Campus 2Caixa Postal 131 BR-74001970 Goiania Go Brazil Georgia Inst Technol Sch Ind & Syst Engn Atlanta GA 30332 USA 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2017年第27卷第1期

页      面：379-407页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：CNPq [406250/2013-8, 444134/2014-0, 309370/2014-0, 200852/2014-0, 201047/2014-4] FAPEG/GO NSF [CMMI-1300221.] Directorate For Engineering Div Of Civil, Mechanical, & Manufact Inn Funding Source: National Science Foundation 

主　　题：alternating direction method of multipliers hybrid proximal extragradient method non-Euclidean Bregman distances convex program pointwise iteration-complexity first-order methods inexact proximal point method regularization 

摘      要：This paper describes a regularized variant of the alternating direction method of multipliers (ADMM) for solving linearly constrained convex programs. It is shown that the pointwise iteration-complexity of the new variant is better than the corresponding one for the standard ADMM method and that, up to a logarithmic term, is identical to the ergodic iteration-complexity of the latter method. Our analysis is based on first presenting and establishing the pointwise iteration-complexity of a regularized non-Euclidean hybrid proximal extragradient framework whose error condition at each iteration includes both a relative error and a summable error. It is then shown that the new ADMM variant is a special instance of the latter framework where the sequence of summable errors is identically zero when the ADMM stepsize is less than one or a nontrivial sequence when the stepsize is in the interval [1, (1 + root 5)/2).