2016/01/06 by Goncalves, Max L. N., Melo, Jefferson G., Monteiro, Renato D. C.
#47H05 #47J22 #49M27 #65K10 #90C25 #90C30 #90C60 #FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1601.01140
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 method 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 method 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 +√(5))/2).