The Developments of Proximal Point Algorithms

doi:10.1007/s40305-021-00352-x

Abstract

Abstract: The problem of finding a zero point of a maximal monotone operator plays a central role in modeling many application problems arising from various fields, and the proximal point algorithm (PPA) is among the fundamental algorithms for solving the zero-finding problem. PPA not only provides a very general framework of analyzing convergence and rate of convergence of many algorithms, but also can be very efficient in solving some structured problems. In this paper, we give a survey on the developments of PPA and its variants, including the recent results with linear proximal term, with the nonlinear proximal term, as well as the inexact forms with various approximate criteria.

Key words: Zero-finding problems, Proximal point algorithms, Variational inequality problems, Optimization, Bregman distance, Approximate criteria

CLC Number:

Xing-Ju Cai, Ke Guo, Fan Jiang, Kai Wang, Zhong-Ming Wu, De-Ren Han. The Developments of Proximal Point Algorithms[J]. Journal of the Operations Research Society of China, 2022, 10(2): 197-239.

TrendMD

References

[1] Minty, G.:Monotone operators in Hilbert space. Duke Mathematical Journal 29, 341-346(1962)
[2] Moreau, J.:Proximité et dualité dans un espace hilbertien. Bulletin de la Socit Chimique de France, 273-299(1965)
[3] Martinet, B.:Regularization d'inequations variationelles par approximations successives. Revue Francaise d'Informatique et de Recherche Opérationelle 4, 154-159(1970)
[4] Fukushima, M., Mine, H.:A generalized proximal point algorithm for certain non-convex minimization problems. International Journal of Systems Science 12(8), 989-1000(1981)
[5] Güler, O.:On the convergence of the proximal point algorithm for convex minimization. SIAM Journal on Control and Optimization 29(2), 403-419(1991)
[6] Güler, O.:New proximal point algorithms for convex minimization. SIAM Journal on Optimization 2(4), 649-664(1992)
[7] Rockafellar, R.T.:Monotone operators and the proximal point algorithm. SIAM Journal on Control and Optimization 14(5), 877-898(1976)
[8] Hestenes, M.R.:Multiplier and gradient methods. Journal of Optimization Theory and Applications 4(5), 303-320(1969)
[9] Powell, M.J.:A Method for Nonlinear Constraints in Minimization Problems. In:Fletcher, R. (ed.) Optimization, pp. 283-298. Academic Press (1969)
[10] Glowinski, R., Marroco, 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. Revue française d'automatique, informatique, recherche opérationnelle. Analyse numérique 9(2), 41-76(1975)
[11] Lions, P.-L., Mercier, B.:Splitting algorithms for the sum of two nonlinear operators. SIAM Journal on Numerical Analysis 16(6), 964-979(1979)
[12] Parikh, N., Boyd, S.:Proximal algorithms. Foundations and Trends in Optimization 1(3), 127-239(2014)
[13] He, B., Fu, X., Jiang, Z.:Proximal-point algorithm using a linear proximal term. Journal of Optimization Theory and Applications 141(2), 299-319(2009)
[14] Cai, X.:A proximal point algorithm with asymmetric linear term. Optimization Letters 13(4), 777-793(2019)
[15] Guo, K., Han, D.:Nonsymmetric proximal point algorithm with moving proximal centers for variational inequalities:convergence analysis. Applied Numerical Mathematics 147, 1-18(2020)
[16] Cai, X., Gu, G., He, B., Yuan, X.:A proximal point algorithm revisit on the alternating direction method of multipliers. Science China Mathematics 56(10), 2179-2186(2013)
[17] Gu, G., He, B., Yuan, X.:Customized proximal point algorithms for linearly constrained convex minimization and saddle-point problems:a unified approach. Computational Optimization and Applications 59(1), 135-161(2014)
[18] Pock, T., Chambolle, A.:Diagonal preconditioning for first order primal-dual algorithms in convex optimization. In:2011 International Conference on Computer Vision, pages 1762-1769(2011)
[19] Bonnans, J., Gilbert, J., Lemaréchal, C., Sagastizábal, C.:A family of variable metric proximal methods. Mathematical Programming 68, 15-47(1995)
[20] Burke, J., Qian, M.:A variable metric proximal point algorithm for monotone operators. SIAM Journal on Control and Optimization 37(2), 353-375(1999)
[21] Burke, J., Qian, M.:On the superlinear convergence of the variable metric proximal point algorithm using Broyden and BFGS matrix secant updating. Mathematical Programming 88(1), 157-181(2000)
[22] Kontogiorgis, S., Meyer, R.R.:A variable-penalty alternating directions method for convex optimization. Mathematical Programming 83(1-3), 29-53(1998)
[23] Rockafellar, R.T., Wets, R.J.-B.:Variational Analysis, vol. 317. Springer Science & Business Media (2009)
[24] Bauschke, H.H., Combettes, P.L.:Convex Analysis and Monotone Operator Theory in Hilbert Spaces, vol. 408. Springer (2011)
[25] Bertsekas, D., Scientific, A.:Convex Optimization Algorithms. Athena Scientific Belmont (2015)
[26] Aragón Artacho, F.J., Geoffroy, M.H.:Characterization of metric regularity of subdifferentials. Journal of Convex Analysis 15(2), 365-380(2008)
[27] Attouch, H., Bolte, J.:On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Mathematical Programming 116(1-2), 5-16(2009)
[28] Absil, P.-A., Mahony, R., Andrews, B.:Convergence of the iterates of descent methods for analytic cost functions. SIAM Journal on Optimization 16(2), 531-547(2005)
[29] Łojasiewicz, S.:Une propriété topologique des sous-ensembles analytiques réels, les Équations auxdérivées partielles. Les Éditions aux Dérivées Partielles 117, 87-89(1963)
[30] Bochnak, J., Coste, M., Roy, M.-F.:Géométrie algébrique réelle. Ergebnisse der Mathematik und ihrer Grenzgebiete (3)[Results in Mathematics and Related Areas (3)], vol. 12. Springer-Verlag, Berlin (1987)
[31] Bolte, J., Daniilidis, A., Lewis, A.:The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM Journal on Optimization 17(4), 1205-1223(2007)
[32] Dong, Y.:Comments on "The proximal point algorithm revisited". Journal of Optimization Theory and Applications 166(1), 343-349(2015)
[33] Dontchev, A.L., Rockafellar, R.T.:Implicit Functions and Solution Mappings, vol. 543. Springer (2009)
[34] Leventhal,D.:Metricsubregularityandtheproximalpointmethod.JournalofMathematicalAnalysis and Applications 360(2), 681-688(2009)
[35] Rockafellar, R.T.:Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Mathematics of Operations Research 1(2), 97-116(1976)
[36] Rockafellar, R.T.:Convex Analysis. Princeton University Press (2015)
[37] Bertsekas, D., Nedic, A.:Convex Analysis and Optimization. Athena Scientific (2003)
[38] Douglas, J., Rachford, H.:On the numerical solution of heat conduction problems in two and three space variables. Transactions of the American Mathematical Society 82(2), 421-439(1956)
[39] Eckstein, J., Bertsekas, D.P.:On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming 55(1-3), 293-318(1992)
[40] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.:Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends^® in Machine Learning 3(1), 1-122(2011)
[41] Fukushima, M.:Application of the alternating direction method of multipliers to separable convex programming problems. Computational Optimization and Applications 1(1), 93-111(1992)
[42] Gabay, D., Mercier, B.:A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers and Mathematics with Applications 2(1), 17-40(1976)
[43] He, B., Liao, L., Han, D., Yang, H.:A new inexact alternating directions method for monotone variational inequalities. Mathematical Programming 92(1), 103-118(2002)
[44] Eckstein, J., Yao, W.:Understanding the convergence of the alternating direction method of multipliers:Theoretical and computational perspectives. Pacific Journal of Optimization 11(4), 619-644(2015)
[45] Fortin, M., Glowinski, R.:Augmented Lagrangian methods:application to the numerical solution of boundary-value problems. Studies in Applied Mathematics 15(3), 165-193(1983)
[46] Glowinski,R.:Onalternatingdirectionmethodsofmultipliers:ahistoricalperspective.In:Modeling, Simulation and Optimization for Science and Technology, pages 59-82. Springer (2014)
[47] He, B., You, Y., Yuan, X.:On the convergence of primal-dual hybrid gradient algorithm. SIAM Journal on Optimization 7(4), 2526-2537(2014)
[48] Jiang, F., Wu, Z., Cai, X.:Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial and Management Optimization 16(2), 835-856(2020)
[49] Li, M., Sun, D., Toh, K.C.:A majorized admm with indefinite proximal terms for linearly constrained convex composite optimization. SIAM Journal on Optimization 26(2), 922-950(2016)
[50] Jiang,F.,Cai,X.,Han,D.:Theindefiniteproximalpointalgorithmsformaximalmonotoneoperators. Optimization 70(8), 1759-1790(2021)
[51] Yang, J., Yuan, X.:Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization. Mathematics of Computation 82(281), 301-329(2013)
[52] He, B., Ma, F., Yuan, X.:Optimal proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems. IMA Journal of Numerical Analysis 40(2), 1188-1216(2020)
[53] Teboulle, M.:Entropic proximal mappings with applications to nonlinear programming. Mathematics of Operations Research 17(3), 670-690(1992)
[54] Csiszár, I.:Information-type measures of difference of probability distributions and indirect observation. Studia Scientiarum Mathematicarum Hungarica 2, 229-318(1967)
[55] Bregman, L.M.:The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Computational Mathematics and Mathematical Physics 7(3), 200-217(1967)
[56] Censor, Y., Zenios, S.A.:Proximal minimization algorithm with D-functions. Journal of Optimization Theory and Applications 73(3), 451-464(1992)
[57] Chen, G., Teboulle, M.:Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization 3(3), 538-543(1993)
[58] Kiwiel, K.C.:Proximal minimization methods with generalized Bregman functions. SIAM Journal on Control and Optimization 35(4), 1142-1168(1997)
[59] Iusem, A.N., Svaiter, B.F., Teboulle, M.:Entropy-like proximal methods in convex programming. Mathematics of Operations Research 19(4), 790-814(1994)
[60] Iusem, A.N., Teboulle, M.:Convergence rate analysis of nonquadratic proximal methods for convex and linear programming. Mathematics of Operations Research 20(3), 657-677(1995)
[61] Teboulle, M.:Convergence of proximal-like algorithms. SIAM Journal on Optimization 7(4), 1069-1083(1997)
[62] Auslender, A., Haddou, M.:An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities. Mathematical Programming 71(1), 77-100(1995)
[63] Eckstein, J.:Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Mathematics of Operations Research 18(1), 202-226(1993)
[64] Bauschke, H.H., Borwein, J.M., Combettes, P.L.:Bregman monotone optimization algorithms. SIAM Journal on Control and Optimization 42(2), 596-636(2003)
[65] Burachik, R.S., Iusem, A.N.:A generalized proximal point algorithm for the variational inequality problem in a hilbert space. SIAM Journal on Optimization 8(1), 197-216(1998)
[66] Burachik, R.S., Scheimberg, S.:A proximal point method for the variational inequality problem in Banach spaces. SIAM Journal on Control and Optimization 39(5), 1633-1649(2000)
[67] Auslender, A., Teboulle, M., Ben-Tiba, S.:A logarithmic-quadratic proximal method for variational inequalities. Computational Optimization and Applications 12(1-3), 31-40(1999)
[68] Auslender, A., Teboulle, M.:Entropic proximal decomposition methods for convex programs and variational inequalities. Mathematical Programming 91(1), 33-47(2001)
[69] Han, D.:A new hybrid generalized proximal point algorithm for variational inequality problems. Journal of Global Optimization 26(2), 125-140(2003)
[70] Han, D.:A hybrid entropic proximal decomposition method with self-adaptive strategy for solving variational inequality problems. Computers and Mathematics with Applications 55(1), 101-115(2008)
[71] He, H., Wang, K., Cai, X., Han, D.:An LQP-based two-step method for structured variational inequalities. Journal of the Operations Research Society of China 5(3), 301-317(2017)
[72] Li, M., Yuan, X.:A strictly contractive Peaceman-Rachford splitting method with logarithmicquadratic proximal regularization for convex programming. Mathematics of Operations Research 40(4), 842-858(2015)
[73] Tao, M., Yuan, X.:On the O(1/t) convergence rate of alternating direction method with logarithmicquadratic proximal regularization. SIAM Journal on Optimization 22(4), 1431-1448(2012)
[74] Yuan, X., Li, M.:An LQP-based decomposition method for solving a class of variational inequalities. SIAM Journal on Optimization 21(4), 1309-1318(2011)
[75] He, H., Cai, X., Han, D.:A class of nonlinear proximal point algorithms for variational inequality problems. International Journal of Computer Mathematics 92(7), 1385-1401(2015)
[76] Han, D., He, B.:A new accuracy criterion for approximate proximal point algorithms. Journal of Mathematical Analysis and Applications 263(2), 343-354(2001)
[77] Yang, Z., He, B.:A relaxed approximate proximal point algorithm. Annals of Operations Research 133(1), 119-125(2005)
[78] Eckstein, J.:Approximate iterations in Bregman-function-based proximal algorithms. Mathematical programming 83(1-3), 113-123(1998)
[79] Solodov, M.V., Svaiter, B.F.:A hybrid projection-proximal point algorithm. Journal of Convex Analysis 6(1), 59-70(1999)
[80] Humes, C., Silva, P.J.:Inexact proximal point algorithms and descent methods in optimization. Optimization and Engineering 6(2), 257-271(2005)
[81] Solodov, M.V., Svaiter, B.F.:An inexact hybrid generalized proximal point algorithm and some new results on the theory of Bregman functions. Mathematics of Operations Research 25(2), 214-230(2000)
[82] He, B., Liao, L., Yang, Z.:A new approximate proximal point algorithm for maximal monotone operator. Science in China Series A:Mathematics 46(2), 200(2003)
[83] He, B., Yang, Z., Yuan, X.:An approximate proximal-extragradient type method for monotone variational inequalities. Journal of Mathematical Analysis and Applications 300(2), 362-374(2004)
[84] Burachik, R.S., Iusem, A.N., Svaiter, B.F.:Enlargement of monotone operators with applications to variational inequalities. Set-Valued Analysis 5(2), 159-180(1997)
[85] Solodov, M.V., Svaiter, B.F.:A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis 7(4), 323-345(1999)
[86] Korpelevich, G.:The extragradient method for finding saddle points and other problems. Matecon 12, 747-756(1976)
[87] Solodov, M.V., Svaiter, B.F.:A unified framework for some inexact proximal point algorithms. Numerical Functional Analysis and Optimization 22(7-8), 1013-1035(2001)
[88] Hager, W., Zhang, H.:Asymptotic convergence analysis of a new class of proximal point methods. SIAM Journal on Control and Optimization 46(5), 1683-1704(2007)
[89] He, B., Yuan, X.:An accelerated inexact proximal point algorithm for convex minimization. Journal of Optimization Theory and Applications 154(2), 536-548(2012)
[90] Bnouhachem, A., Noor, M.A.:Inexact proximal point method for general variational inequalities. Journal of Mathematical Analysis and Applications 324(2), 1195-1212(2006)
[91] Zaslavski, A.J.:Inexact proximal point methods in metric spaces. Set-Valued and Variational Analysis 19(4), 589-608(2011)
[92] Burachik, R., Dutta, J.:Inexact proximal point methods for variational inequality problems. SIAM Journal on Optimization 20(5), 2653-2678(2010)
[93] Salzo, S., Villa, S.:Inexact and accelerated proximal point algorithms. Journal of Convex Analysis 19(4), 1167-1192(2012)
[94] Eckstein, J., Yao, W.:Relative-error approximate versions of Douglas-Rachford splitting and special cases of the ADMM. Mathematical Programming 170(2), 417-444(2018)
[95] Qian, M.:The Variable Metric Proximal Point Algorithm:Theory and Application. PhD thesis, (1992)
[96] Chen, X., Fukushima, M.:Proximal quasi-Newton methods for nondifferential convex optimization. Mathematical Programming 85, 313-334(1999)
[97] Fukushima, M., Qi, L.:A globally and superlinearly convergent algorithm for nonsmooth convex minimization. SIAM Journal on Optimization 6(4), 1106-1120(1996)
[98] Qi, L., Chen, X.:A preconditioning proximal Newton method for nondifferentiable convex optimization. Mathematical Programming 76, 411-430(1995)
[99] Lemaréchal, C., Sagastizábal, C.:An approach to variable metric bundle methods, volume 197 of LNCIS, pages 144-162. Springer, Berlin (1994)
[100] Lemaréchal,C.,Sagastizábal,C.:Variablemetricbundlemethods:fromconceptualtoimplementable forms. Mathematical Programming 76, 393-410(1997)
[101] Mifflin,R.:Aquasi-second-orderproximalbundlealgorithm.MathematicalProgramming 73,51-72(1996)
[102] Mifflin, R., Sun, D., Qi, L.:Quasi-Newton bundle-type methods for nondifferentiable convex optimization. SIAM Journal on Optimization 8, 583-603(1998)
[103] Lemaréchal, C.:Bundle methods in nonsmooth optimization. Pergamon Press, Oxford (1978)
[104] Qian, M., Burke, J.:On the local super-linear convergence of a matrix secant Implementation of the variable metric proximal point algorithm for monotone operators, pp. 317-334. Kluwer Academic Publishers (1999)
[105] Parente, L., Lotito, P., Solodov, M.:A class of inexact variable metric proximal point algorithms. SIAM Journal on Optimization 19(1), 240-260(2008)
[106] Lin, H., Mairal, J., Harchaoui, Z.:An inexact variable metric proximal point algorithm for generic quasi-Newton acceleration. SIAM Journal on Optimization 29(2), 1408-1443(2019)
[107] Combettes, P., Vu, B.-C.:Variable metric forward-backward splitting with applications to monotone inclusions in duality. Optimization 63(9), 1289-1318(2014)
[108] Becker, S., Fadili, J., Ochs, P.:On quasi-Newton forwad-backwad splitting proximal calculus and convergence. SIAM Journal on Optimization 29(4), 2445-2481(2019)
[109] Chouzenoux, E., Pesquet, J.-C., Repetti, A.:Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. Journal of Optimization Theory and Applications 162(1), 107-132(2014)
[110] Salzo, S.:The variable metric forward-backward splitting algorithm unde mild differentiablility assumptions. SIAM Journal on Optimization 27(4), 2153-2181(2017)
[111] Stella, L., Themelis, A., Patrinos, P.:Forward-backward quasi-Newton methods for nonsmooth optimization problems. Computational Optimization and Applications 67, 443-487(2017)
[112] Vu, B.-C.:A variable metric extension of the forward-backward-forward algorithm for monotone operators. Numerical Functional Analysis and Optimization 34(9), 1050-1065(2013)