Local Linear Convergence of an ADMM-Type Splitting Framework for Equality Constrained Optimization

doi:10.1007/s40305-019-00271-y

Abstract

Abstract: We establish local convergence results for a generic algorithmic framework for solving a wide class of equality constrained optimization problems. The framework is based on applying a splitting scheme to the augmented Lagrangian function that includes as a special case the well-known alternating direction method of multipliers (ADMM). Our local convergence analysis is free of the usual restrictions on ADMM-like methods, such as convexity, block separability or linearity of constraints. It offers a much-needed theoretical justification to the widespread practice of applying ADMM-like methods to nonconvex optimization problems.

Key words: Alternating direction method of multipliers, Nonlinear splitting, Stationary iterations, Spectral radius, Local linear convergence

CLC Number:

Jun-Feng Yang, Yin Zhang. Local Linear Convergence of an ADMM-Type Splitting Framework for Equality Constrained Optimization[J]. Journal of the Operations Research Society of China, 2021, 9(2): 308-319.

TrendMD

References

[1] Glowinski, R., Marrocco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de Dirichlet non linéaires. Rev. Française Automat. Informat. Recherche Opérationnelle 9(R–2), 41–76(1975)
[2] Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finiteelement approximations. Comput. Math. Appl. 2, 17–40(1976)
[3] Chan, T.F., Glowinski, R.: Finite Element Approximation and Iterative Solution of a Class of Mildly Nonlinear Elliptic Equations. Technical report, Stanford University, Stanford (1978)
[4] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122(2011)
[5] Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. In: Modeling, Simulation and Optimization for Science and Technology. Computational Mechanics Computer Science, vol. 34, pp. 59–82. Springer, Dordrecht (2014)
[6] Fortin, M., Glowinski, R.: Augmented Lagrangian Methods, vol. 15, Studies in Mathematics and its Applications. North-Holland Publishing Co., Amsterdam. Applications to the numerical solution of boundary value problems, (trans. from the French by B. Hunt and D. C. Spicer.) (1983)
[7] Glowinski, R., Le Tallec, P.: Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM Studies in Applied Mathematics, vol. 9. Society for Industrial and Applied Mathematics, Philadelphia, (1989)
[8] Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, pp. 299–331. North-Holland, Amsterdam (1983)
[9] Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(3, Ser. A), 293–318(1992)
[10] Eckstein, J., Yao, W.: Understanding the convergence of the alternating direction method of multipliers: theoretical and computational perspectives. Pac. J. Optim. 11(4), 619–644(2015)
[11] He, B.S., Yuan, X.M.: On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method. SIAM J. Numer. Anal. 50(2), 700–709(2012)
[12] Monteiro, R.D.C., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23(1), 475–507(2013)
[13] Eckstein, J., Bertsekas, D.P.: An Alternating Direction Method for Linear Programming. Working paper 90-063, Harvard Business School (1990)
[14] Boley, D.: Local linear convergence of admm on quadratic or linear programs. SIAM J. Optim. 23(4), 2183–2207(2013)
[15] Han, D.R., Yuan, X.M.: Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J. Numer. Anal. 51(6), 3446–3457(2013)
[16] Luo, Z.Q., Tseng, P.: Error bound and convergence analysis of matrix splitting algorithms for the affine variational inequality problem. SIAM J. Optim. 2(1), 43–54(1992)
[17] Deng, W., Yin, W.T.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3), 889–916(2016)
[18] Yang, W.H., Han, D.R.: Linear convergence of the alternating direction method of multipliers for a class of convex optimization problems. SIAM J. Numer. Anal. 54(2), 625–640(2016)
[19] Cai, X.J., Han, D.R., Yuan, X.M.: On the convergence of the direct extension of ADMM for threeblock separable convex minimization models with one strongly convex function. Comput. Optim. Appl. 66(1), 39–73(2017)
[20] Han, D.R., Sun, D.F., Zhang, L.W.: Linear rate convergence of the alternating direction method of multipliers for convex composite programming. Math. Oper. Res. 43(2), 622–637(2018)
[21] Hong, M.Y., Luo, Z.Q.: On the linear convergence of the alternating direction method of multipliers. Math. Program. 162(1–2, Ser. A), 165–199(2017)
[22] Xu, Y.Y., Yin, W.T., Wen, Z.W., Zhang, Y.: An alternating direction algorithm for matrix completion with nonnegative factors. Front. Math. China 7(2), 365–384(2012)
[23] Shen, Y., Wen, Z., Zhang, Y.: Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization. Optim. Methods Softw. 29(2), 239–263(2014)
[24] Wen, Z.W., Yang, C., Liu, X., Marchesini, S.: Alternating direction methods for classical and ptychographic phase retrieval. Inverse Problems 28(11), 115010, 18(2012)
[25] Luo, Z.Q., Tseng, P.: Error bounds and convergence analysis of feasible descent methods: a general approach. Ann. Oper. Res. 46/47(1–4), 157–178(1993)
[26] Lojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. In: Les Équations aux Dérivées Partielles (Paris, 1962), pp. 87–89. Éditions du Centre National de la Recherche Scientifique, Paris (1963)
[27] Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier (Grenoble) 48(3), 769–783(1998)
[28] Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka–łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457(2010)
[29] Guo, K., Han, D.R., Wu, T.T.: Convergence of alternating direction method for minimizing sum of two nonconvex functions with linear constraints. Int. J. Comput. Math. 94(8), 1653–1669(2017)
[30] Guo, K., Han, D.R., Wang, David Z.W., Wu, T.T.: Convergence of ADMM for multi-block nonconvex separable optimization models. Front. Math. China 12(5), 1139–1162(2017)
[31] Li, G.Y., Pong, T.K.: Calculus of the exponent of Kurdyka–Lojasiewicz inequality and its applications to linear convergence of first-order methods. Found. Comput. Math. 18, 1199–1232(2018)
[32] Li, G.Y., Pong, T.K.: Global convergence of splitting methods for nonconvex composite optimization. SIAM J. Optim. 25(4), 2434–2460(2015)
[33] Hong, M.Y., Luo, Z.Q., Razaviyayn, M.: Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems. SIAM J. Optim. 26(1), 337–364(2016)
[34] Bot, R.I., Nguyen, D.-K.: The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates (2018). arXiv:1801.01994v1
[35] Zhang, Y.: Convergence of a class of stationary iterative methods for saddle point problems. J. Oper. Res. Soc. China. 7(2), 195–204(2019)
[36] Ortega, J.M., Rheinboldt, W.C.: Iterative Solution of Nonlinear Equations in Several Variables. Academic Press Inc., Cambridge (1970)
[37] Ostrowski, A.M.: Solution of Equations and Systems of Equations, 1st edn (1960), 2nd edn (1966). Pure and Applied Mathematics, Vol. 9. Academic Press, New York (1966)
[38] Ortega, J.M., Rockoff, M.L.: Nonlinear difference equations and Gauss–Seidel type iterative methods. SIAM J. Numer. Anal. 3, 497–513(1966)
[39] Ortega, J.M., Rheinboldt, W.C.: Local and global convergence of generalized linear iterations. In: Studies in Numerical Analysis, 2: Numerical Solutions of Nonlinear Problems (Symposia, SIAM, Philadelphia, PA., 1968), pp. 122–143. The Society for Industrial and Applied Mathematics, Philadelphia, PA (1970)
[40] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320(1969)
[41] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Optimization (Symposium, University of Keele, Keele, 1968), pp. 283–298. Academic Press, London (1969)
[42] Karush, W.: Minima of Functions of Several Variables with Inequalities as Side Conditions. ProQuest LLC, Ann Arbor, MI, (1939). Thesis (SM), The University of Chicago