×

The generalized proximal point algorithm with step size 2 is not necessarily convergent. (English) Zbl 1393.90088

Summary: The proximal point algorithm (PPA) is a fundamental method in optimization and it has been well studied in the literature. Recently a generalized version of the PPA with a step size in \((0,2)\) has been proposed. Inheriting all important theoretical properties of the original PPA, the generalized PPA has some numerical advantages that have been well verified in the literature by various applications. A common sense is that larger step sizes are preferred whenever the convergence can be theoretically ensured; thus it is interesting to know whether or not the step size of the generalized PPA can be as large as 2. We give a negative answer to this question. Some counterexamples are constructed to illustrate the divergence of the generalized PPA with step size 2 in both generic and specific settings, including the generalized versions of the very popular augmented Lagrangian method and the alternating direction method of multipliers. A by-product of our analysis is the failure of convergence of the Peaceman-Rachford splitting method and a generalized version of the forward-backward splitting method with step size 1.5.

MSC:

90C25 Convex programming
90C30 Nonlinear programming

Software:

GADMM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bai, ZZ; Hadjidimos, A, Optimization of extrapolated Cayley transform with non-Hermitian positive definite matrix, Linear Algebra Appl., 463, 322-339, (2014) · Zbl 1300.65020 · doi:10.1016/j.laa.2014.08.021
[2] Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer, New York (2011) · Zbl 1218.47001 · doi:10.1007/978-1-4419-9467-7
[3] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Academic Press, New York (1982) · Zbl 0572.90067
[4] Cayley, A, On the theory of linear transformations, Camb. J. Math., 4, 1-16, (1845) · JFM 01.0165.01
[5] Chen, GH-G; Rockafellar, RT, Convergence rate in forward-backward splitting, SIAM J. Optim., 7, 1-25, (1997) · Zbl 0884.65053 · doi:10.1137/S1052623493250780
[6] Combetters, PL; Wajs, VR, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4, 1168-1200, (2006) · Zbl 1179.94031 · doi:10.1137/050626090
[7] Corman, E; Yuan, XM, A generalized proximal point algorithm and its convergence rate, SIAM J. Optim., 24, 1614-1638, (2014) · Zbl 1311.90099 · doi:10.1137/130940402
[8] Davis, D., Yin, W.: Convergence rate analysis of several splitting schemes. http://arxiv.org/pdf/1406.4834.pdf · Zbl 1372.65168
[9] Douglas, J; Rachford, HH, On the numerical solution of the heat conduction problem in 2 and 3 space variables, Trans. Am. Math. Soc., 82, 421-439, (1956) · Zbl 0070.35401 · doi:10.1090/S0002-9947-1956-0084194-4
[10] Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. Ph.D. Dissertation, MIT, Cambridge (1989) · Zbl 0067.35801
[11] Eckstein, J, Parallel alternating direction multiplier decomposition of convex programs, J. Optim. Theory Appl., 80, 39-62, (1994) · Zbl 0797.90075 · doi:10.1007/BF02196592
[12] Eckstein, J; Bertsekas, DP, On the Douglas-Rachford splitting method and the proximal points algorithm for maximal monotone operators, Math. Program., 55, 293-318, (1992) · Zbl 0765.90073 · doi:10.1007/BF01581204
[13] Fang, EX; Liu, H; He, BS; Yuan, XM, The generalized alternating direction method of multipliers: new theoretical insights and applications, Math. Prog. Comput., 7, 149-187, (2015) · Zbl 1353.90110 · doi:10.1007/s12532-015-0078-2
[14] Gabay, D; Fortin, M (ed.); Glowinski, R (ed.), Applications of the method of multipliers to variational inequalities, 299-331, (1983), Amsterdam · doi:10.1016/S0168-2024(08)70034-1
[15] Glowinski, R; Kärkkäinen, T; Majava, K; Kuznetsov, Y (ed.); Neittanmaki, P (ed.); Pironneau, O (ed.), On the convergence of operator-splitting methods, 67-79, (2003), Barcelona
[16] Glowinski, R; Marrocco, A, Approximation par \(\acute{e}\)l\(\acute{e}\)ments finis d’ordre un et r\(\acute{e}\)solution par p\(\acute{e}\)nalisation-dualit\(\acute{e}\) d’une classe de probl\(\grave{e}\)mes non lin\(\acute{e}\)aires, RAIRO, R2, 41-76, (1975)
[17] Gol’shtein, EG; Tret’yakov, NV, Modified Lagrangian in convex programming and their generalizations, Math. Progr. Study, 10, 86-97, (1979) · Zbl 0404.90069 · doi:10.1007/BFb0120845
[18] Güler, O, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Optim., 1, 403-419, (1991) · Zbl 0737.90047 · doi:10.1137/0329022
[19] Hestenes, MR, Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320, (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[20] Korpelevich, GM, The extragradient method for finding saddle points and other problems, Ekon. i Mat. Metody, 12, 747-756, (1976) · Zbl 0342.90044
[21] Lions, PL; Mercier, B, Splitting algorithms for the sum of two nonlinear operators, SIAM J. Numer. Anal., 16, 964-979, (1979) · Zbl 0426.65050 · doi:10.1137/0716071
[22] Martinet, B, Regularization d’inequations variationelles par approximations successives, Rev. Fr. d’Inf. et de Rech. Opér., 4, 154-159, (1970) · Zbl 0215.21103
[23] Moreau, JJ, Proximité et dualit ’e dans un espace hilbertien, Bull. Soc. Math. Fr., 93, 273-299, (1965) · Zbl 0136.12101 · doi:10.24033/bsmf.1625
[24] Nemirovski, A, Prox-method with rate of convergence \(O(1/t)\) for variational inequality with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems, SIAM J. Optim., 15, 229-251, (2005) · Zbl 1106.90059 · doi:10.1137/S1052623403425629
[25] Passty, GB, Ergodic convergence to a zero of the sume of monotone operators in Hilbert space, J. Math. Anal. Appl., 72, 383-390, (1979) · Zbl 0428.47039 · doi:10.1016/0022-247X(79)90234-8
[26] Peaceman, DH; Rachford, HH, The numerical solution of parabolic elliptic differential equations, J. Soc. Ind. Appl. Math., 3, 28-41, (1955) · Zbl 0067.35801 · doi:10.1137/0103003
[27] Polyak, B.T.: Introduction to Optimization. Translations Series in Mathematics and Engineering, Optimization Software. Publications Division, New York (1987) · Zbl 0708.90083
[28] Powell, MJD; Fletcher, R (ed.), A method for nonlinear constraints in minimization problems, 283-298, (1969), New York
[29] Rockafellar, R.T.: Convex Analysis. Princeton University Press, Princeton (1970) · Zbl 0193.18401 · doi:10.1515/9781400873173
[30] Rockafellar, RT, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14, 97-116, (1976) · Zbl 0402.90076
[31] Rockafellar, RT, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res., 1, 877-898, (1976) · Zbl 0358.90053 · doi:10.1287/moor.1.2.97
[32] Shen, L., Pan, S.H.: Linear convergence of the generalized PPA and several splitting methods for the composite inclusion problem. http://arxiv.org/abs/1508.05156v2
[33] Teboulle, M, Convergence of proximal-like algorithms, SIAM J. Optim., 7, 1069-1083, (1997) · Zbl 0890.90151 · doi:10.1137/S1052623495292130
[34] Tao, M; Yuan, XM, On the optimal linear convergence rate of a generalized proximal point algorithm, J. Sci. Comput., 74, 826-850, (2018) · Zbl 06858875 · doi:10.1007/s10915-017-0477-9
[35] Wen, Z; Goldfarb, D; Yin, W, Alternating direction augmented Lagrangian methods for semidefinite programming, Math. Progr. Comput., 2, 203-230, (2010) · Zbl 1206.90088 · doi:10.1007/s12532-010-0017-1
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.