A partially inexact ADMM with o(1/n) asymptotic convergence rate, 𝒪(1/n) complexity, and immediate relative error tolerance

References

• Solodov MV, Svaiter BF. A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Anal. 1999;7(4):323–345.
   Google Scholar
• Solodov MV, Svaiter BF. A hybrid projection-proximal point algorithm. J Convex Anal. 1999;6(1):59–70.
   Web of Science ®Google Scholar
• Solodov MV, Svaiter BF. An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions. Math Oper Res. 2000;25(2):214–230.
   Web of Science ®Google Scholar
• Eckstein J, Svaiter BF. A family of projective splitting methods for the sum of two maximal monotone operators. Math Program. 2008;111(1-2, Ser. B):173–199.
   Web of Science ®Google Scholar
• Eckstein J, Svaiter BF. General projective splitting methods for sums of maximal monotone operators. SIAM J Control Optim. 2009;48(2):787–811.
   Web of Science ®Google Scholar
• Monteiro RDC, Svaiter BF. Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J Optim. 2013;23(1):475–507.
   Web of Science ®Google Scholar
• Attouch H, Bolte J, Svaiter BF. Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss–Seidel methods. Math Program. 2013;137(1–2, Ser. A):91–129.
   Web of Science ®Google Scholar
• Xie J, Liao A, Yang X. An inexact alternating direction method of multipliers with relative error criteria. Optim Lett. 2017;11(3):583–596.
   Web of Science ®Google Scholar
• Eckstein J, Silva PJS. A practical relative error criterion for augmented Lagrangians. Math Program. 2013;141(1-2, Ser. A):319–348.
   Web of Science ®Google Scholar
• Eckstein J, Yao W. Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM. Math Program. 2018;170(2, Ser. A):417–444.
   Web of Science ®Google Scholar
• Eckstein J, Bertsekas DP. On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math Program. 1992;55(3, Ser. A):293–318.
   Web of Science ®Google Scholar
• Eckstein J, Yao W. Approximate ADMM algorithms derived from Lagrangian splitting. Comput Optim Appl. 2017;68(2):363–405.
   Web of Science ®Google Scholar
• Xie J. On inexact ADMMs with relative error criteria. Comput Optim Appl. 2018;71(3):743–765. Fake, uses Eckstein–Silva fake relative error (verify!).
   Web of Science ®Google Scholar
• Adona VA, Gonçalves MLN, Melo JG. A partially inexact proximal alternating direction method of multipliers and its iteration-complexity analysis. J Optim Theory Appl. 2019;182(2):640–666.
   Web of Science ®Google Scholar
• He B, Yuan X. On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method. SIAM J Numer Anal. 2012;50(2):700–709.
   Web of Science ®Google Scholar
• Adona VA, Gonçalves MLN, Melo JG. Iteration-complexity analysis of a generalized alternating direction method of multipliers. J Global Optim. 2019;73(2):331–348.
   Web of Science ®Google Scholar
• Gonçalves MLN, Melo JG, Monteiro RDC. Improved pointwise iteration-complexity of a regularized ADMM and of a regularized non-Euclidean HPE framework. SIAM J Optim. 2017;27(1):379–407.
   Web of Science ®Google Scholar
• Xiao Y, Chen L, Li D. A generalized alternating direction method of multipliers with semi-proximal terms for convex composite conic programming. Math Program Comput. 2018;10:533–555.
   Web of Science ®Google Scholar
• Chang T, Hong M, Wang X. Multi-agent distributed large-scale optimization by inexact consensus alternating direction method of multipliers. In 2014 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP); 2014 May; Florence, Italy. p. 6137–6141.
   Google Scholar
• Chang T, Hong M, Wang X. Multi-agent distributed optimization via inexact consensus ADMM. IEEE Trans Signal Process. 2015 Jan;63(2):482–497.
   Web of Science ®Google Scholar
• Chen L, Defeng Sun XL, Toh K-C. On the equivalence of inexact proximal ALM and ADMM for a class of convex composite programming. Math Program. 2019. Published electronically.
   PubMed Web of Science ®Google Scholar
• Hager WW, Zhang H. Inexact alternating direction methods of multipliers for separable convex optimization. Comput Optim Appl. 2019;73(1):201–235.
   Web of Science ®Google Scholar
• Jian L, Zhao Y, Hu J, et al. Distributed inexact consensus-based ADMM method for multi-agent unconstrained optimization problem. IEEE Access. 2019;7:79311–79319.
   Web of Science ®Google Scholar
• Sun L, Jiang Z, Li X. Inexact generalized proximal alternating direction methods of multipliers and their convergence rates. Pac J Optim. 2018;14(1):101–124.
   Web of Science ®Google Scholar
• Zhang J-J, Zhang J-L, Ye W-Z. An inexact alternating direction method of multipliers for the solution of linear complementarity problems arising from free boundary problems. Numer Algorithms. 2018;78(3):895–910.
   Web of Science ®Google Scholar
• Monteiro RDC, Svaiter BF. On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM J Optim. 2010;20(6):2755–2787.
   Web of Science ®Google Scholar
• Nesterov YE. A method for solving the convex programming problem with convergence rate O(1/k2). Dokl Akad Nauk SSSR. 1983;269(3):543–547.
   Google Scholar
• Nesterov Y. Introductory lectures on convex optimization. Boston (MA): Kluwer Academic Publishers; 2004. (Applied optimization; 87). A basic course.
   Google Scholar
• Solodov MV, Svaiter BF. A unified framework for some inexact proximal point algorithms. Numer Funct Anal Optim. 2001;22(7-8):1013–1035.
   Web of Science ®Google Scholar
• Burachik RS, Iusem AN, Svaiter BF. Enlargement of monotone operators with applications to variational inequalities. Set-Valued Anal. 1997;5(2):159–180.
   Google Scholar
• Solodov MV, Svaiter BF. Error bounds for proximal point subproblems and associated inexact proximal point algorithms. Math Program. 2000;88(2, Ser. B):371–389. Error bounds in mathematical programming (Kowloon, 1998).
   Web of Science ®Google Scholar
• Svaiter BF. A family of enlargements of maximal monotone operators. Set-Valued Anal. 2000;8(4):311–328.
   Google Scholar