On the iteration-complexity of a non-Euclidean hybrid proximal extragradient framework and of a proximal ADMM

References

• Chambolle A, Pock T. A first-order primal–dual algorithm for convex problems with applications to imaging. J Math Imaging Vis. 2011;40(1):120–145. doi: 10.1007/s10851-010-0251-1
   Web of Science ®Google Scholar
• Chang X, Liu S. A 2-block semi-proximal ADMM for solving the H-weighted nearest correlation matrix problem. Optimization. 2017;66(1):1–16. doi: 10.1080/02331934.2016.1246547
   Web of Science ®Google Scholar
• Deng W, Yin W. On the global and linear convergence of the generalized alternating direction method of multipliers. J Sci Comput. 2016;66(3):889–916. doi: 10.1007/s10915-015-0048-x
   Web of Science ®Google Scholar
• Eckstein J. Some saddle-function splitting methods for convex programming. Optim Method Softw. 1994;4(1):75–83. doi: 10.1080/10556789408805578
   Google Scholar
• Fang EX, He B, Liu H, et al. Generalized alternating direction method of multipliers: new theoretical insights and applications. Math Program Comput. 2015;7(2):149–187. doi: 10.1007/s12532-015-0078-2
   PubMed 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. doi: 10.1137/16M1055530
   Web of Science ®Google Scholar
• Guo K, Han DR, Wu TT. Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. Int J Comput Math. 2017;94(8):1653–1669. doi: 10.1080/00207160.2016.1227432
   Web of Science ®Google Scholar
• Hager WW, Yashtini M, Zhang H. An O(1/k) convergence rate for the variable stepsize Bregman operator splitting algorithm. SIAM J Numer Anal. 2016;54(3):1535–1556. doi: 10.1137/15100401X
   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. doi: 10.1137/110836936
   Web of Science ®Google Scholar
• Lin T, Ma S, Zhang S. An extragradient-based alternating direction method for convex minimization. Found Comput Math. 2017;17(1):35–59. doi: 10.1007/s10208-015-9282-8
   Web of Science ®Google Scholar
• Ouyang Y, Chen Y, Lan G, et al. An accelerated linearized alternating direction method of multipliers. SIAM J Imaging Sci. 2015;8(1):644–681. doi: 10.1137/14095697X
   Web of Science ®Google Scholar
• Fazel M, Pong TK, Sun D, et al. Hankel matrix rank minimization with applications to system identification and realization. SIAM J Matrix Anal Appl. 2013;34(3):946–977. doi: 10.1137/110853996
   Web of Science ®Google Scholar
• Zhang X, Burger M, Bresson X, et al. Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM J Imaging Sci. 2010;3(3):253–276. doi: 10.1137/090746379
   Web of Science ®Google Scholar
• Zhang X, Burger M, Osher S. A unified primal–dual algorithm framework based on Bregman iteration. J Sci Comput. 2010;46(1):20–46. doi: 10.1007/s10915-010-9408-8
   Web of Science ®Google Scholar
• Wang X, Yuan X. The linearized alternating direction method of multipliers for Dantzig selector. SIAM J Sci Comput. 2012;34(5):A2792–A2811. doi: 10.1137/110833543
   Web of Science ®Google Scholar
• Yang J, Yuan X. Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Math Comput. 2013;82(281):301–329. doi: 10.1090/S0025-5718-2012-02598-1
   Web of Science ®Google Scholar
• Cui Y, Li X, Sun D, et al. On the convergence properties of a majorized ADMM for linearly constrained convex optimization problems with coupled objective functions. J Optim Theory Appl. 2016;169(3):1013–1041. doi: 10.1007/s10957-016-0877-2
   Web of Science ®Google Scholar
• Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput Math Appl. 1976;2:17–40. doi: 10.1016/0898-1221(76)90003-1
   Google Scholar
• Glowinski R, Marroco A. Sur l'approximation, par éléments finis d'ordre un, et la résolution, par penalisation-dualité, d'une classe de problèmes de Dirichlet non linéaires; 1975.
   Google Scholar
• Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn. 2011;3(1):1–122. doi: 10.1561/2200000016
   Google Scholar
• Glowinski R. Numerical methods for nonlinear variational problems. Berlin: Springer-Verlag; 1984. (Springer series in computational physics).
   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. doi: 10.1137/110849468
   Web of Science ®Google Scholar
• He B, Ma F, Yuan X. Convergence study on the symmetric version of ADMM with larger step sizes. SIAM J Imaging Sci. 2016;9(3):1467–1501. doi: 10.1137/15M1044448
   Web of Science ®Google Scholar
• He B, Yuan X. On non-ergodic convergence rate of Douglas–Rachford alternating direction method of multipliers. Numer Math. 2015;130(3):567–577. doi: 10.1007/s00211-014-0673-6
   Web of Science ®Google Scholar
• Wu Z, Liu F, Li M. A proximal Peaceman–Rachford splitting method for solving the multi-block separable convex minimization problems. Int J Comput Math. 2019;96(4):708–728. doi: 10.1080/00207160.2018.1435864
   Web of Science ®Google Scholar
• Shen L, Pan S. Weighted iteration complexity of the sPADMM on the KKT residuals for convex composite optimization. Available from: https://arxiv.org/abs/1611.03167.
   Google Scholar
• Rockafellar RT. Monotone operators and the proximal point algorithm. SIAM J Control Optim. 1976;14(5):877–898. doi: 10.1137/0314056
   Web of Science ®Google Scholar
• 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. doi: 10.1023/A:1008777829180
   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. doi: 10.1137/090753127
   Web of Science ®Google Scholar
• Monteiro RDC, Svaiter BF. Complexity of variants of Tseng's modified F–B splitting and Korpelevich's methods for hemivariational inequalities with applications to saddle-point and convex optimization problems. SIAM J Optim. 2011;21(4):1688–1720. doi: 10.1137/100801652
   Web of Science ®Google Scholar
• Kolossoski O, Monteiro RDC. An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems. Optim Methods Softw. 2017;32(6):1244–1272. doi: 10.1080/10556788.2016.1266355
   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. doi: 10.1287/moor.25.2.214.12222
   Web of Science ®Google Scholar
• He Y, Monteiro RDC. Accelerating block-decomposition first-order methods for solving composite saddle-point and two-player Nash equilibrium problems. SIAM J Optim. 2015;25(4):2182–2211. doi: 10.1137/130943649
   Web of Science ®Google Scholar
• He Y, Monteiro RDC. An accelerated HPE-type algorithm for a class of composite convex–concave saddle-point problems. SIAM J Optim. 2016;26(1):29–56. doi: 10.1137/14096757X
   Web of Science ®Google Scholar
• Marques Alves M, Monteiro RDC, Svaiter BF. Regularized HPE-type methods for solving monotone inclusions with improved pointwise iteration-complexity bounds. SIAM J Optim. 2016;26(4):2730–2743. doi: 10.1137/15M1038566
   Web of Science ®Google Scholar
• Rockafellar RT. On the maximal monotonicity of subdifferential mappings. Pacific J Math. 1970;33:209–216. doi: 10.2140/pjm.1970.33.209
   Web of Science ®Google Scholar
• Burachik RS, Sagastizábal CA, Svaiter BF. ε-enlargements of maximal monotone operators: theory and applications. In: Fukushima M, Qi L, editors. Reformulation: nonsmooth, piecewise smooth, semismooth and smoothing methods. Dordrecht: Kluwer Academic Publishers; 1999. p. 25–43. (Applied optimization; vol. 22).
   Google Scholar