A note on the inertial proximal point method
Abstract
The proximal point method (PPM) for solving maximal monotone operator inclusion problem is a highly powerful tool for algorithm design, analysis and interpretation. To accelerate convergence of the PPM, inertial PPM (iPPM) was proposed in the literature. In this note, we point out that some of the attractive properties of the PPM, e.g., the generated sequence is contractive with the set of solutions, do not hold anymore for iPPM. To partially inherit the advantages of the PPM and meanwhile incorporate inertial extrapolation steps, we propose an iPPM with alternating inertial steps. Our analyses show that the even subsequence generated by the proposed iPPM is contractive with the set of solutions. Moreover, we establish global convergence result under much relaxed conditions on the inertial extrapolation stepsizes, e.g., monotonicity is no longer needed and the stepsizes are significantly enlarged compared to existing methods. Furthermore, we establish certain $o(1/k)$ convergence rate results, where $k$ denotes the iteration counter. These features are new to inertial type PPMs.References
F. Aluffi-Pentini, V. Parisi, and F. Zirilli. Algorithm 617. DAFNE: a differential-equations algorithm for nonlinear equations. ACM Trans. Math. Software, 10(3):317–324, 1984.
F. Alvarez. On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J. Control Optim., 38(4):1102–1119 (electronic), 2000.
F. Alvarez. Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space. SIAM J. Optim., 14(3):773–782 (electronic), 2004.
F. Alvarez and H. Attouch. An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set-Valued Anal., 9(1-2):3–11, 2001. Wellposedness in optimization and related topics (Gargnano, 1999).
A. S. Antipin. Minimization of convex functions on convex sets by means of differential equations. Differentsial Equations, 30(9):1475–1486, 1652, 1994.
H. Attouch, J. Peypouquet, and P. Redont. A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J. Optim., 24(1):232–256, 2014.
R. I. Bot and E. R. Csetnek. An inertial alternating direction method of multipliers. arXiv preprint, arXiv:1404.4582, 2014.
R. I. Bot and E. R. Csetnek. An inertial tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. arXiv preprint, arXiv:1406.0724, 2014.
R. I. Bot, E. R. Csetnek, and C. Hendrich. Inertial douglas-rachford splitting for monotone inclusion problems. arXiv preprint, arXiv:1403.3330, 2014.
R. E. Bruck, Jr. Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. J. Funct. Anal., 18:15–26, 1975.
A. Chambolle and T. Pock. On the ergodic convergence rates of a first-order primal-dual algorithm. preprint, September, 2014.
R. H. Chan, S. Q. Ma, and J. F. Yang. Inertial primal-dual algorithms for structured convex optimization. arXiv preprint, arXiv:1409.2992, 2014.
C. H. Chen, R. H. Chan, S. Q. Ma, and J. F. Yang. Inertial Proximal ADMM for Linearly Constrained Separable Convex Optimization. SIAM Journal on Imaging Sciences, To appear.
C. H. Chen, S. Q. Ma, and J. F. Yang. A general inertial proximal point method for mixed variational inequality problem. arXiv preprint, arXiv:1407.8238, 2014.
J. Douglas, Jr. and H. H. Rachford, Jr. On the numerical solution of heat conduction problems in two and three space variables. Trans. Amer. Math. Soc., 82:421–439, 1956.
J. Eckstein and D. P. Bertsekas. On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Programming, 55(3, Ser. A):293–318, 1992.
D. Gabay and B. Mercier. A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Computers and Mathematics with Applications, 2(1):17–40, 1976.
R. Glowinski and A. Marrocco. l'approximation, par 'el'ements finis d'ordre un, et la r'esolution, par p'enalisation-dualit'e, d'une classe de probl`emes de Dirichlet non lin'eaires. R.A.I.R.O., R2, 9(R-2):41–76, 1975.
O. Guler. New proximal point algorithms for convex minimization. SIAM J. Optim., 2(4):649–664, 1992.
M. R. Hestenes. Multiplier and gradient methods. J. Optimization Theory Appl., 4:303–320, 1969.
D. A. Lorenz and T. Pock. An inertial forward-backward algorithm for monotone inclusions. J. Math. Imaging Vis., 2014.
P. E. Mainge and N. Merabet. A new inertial-type hybrid projection-proximal algorithm for monotone inclusions. Applied Mathematics of Computation, 215:3149–3162, 2010.
P. E. Mainge and A. Moudafi. A proximal method for maximal monotone operators via discretization of a first order dissipative dynamical system. J. Convex Anal., 14(4):869–878, 2007.
B. Martinet. Regularisation d’inequations variationnelles par approximations successives. Rev. Franc¸aise Informat. Recherche Operationnelle, 4(Ser. R-3):154–158, 1970.
J. J. Moreau. Proximite et dualit e dans un espace hilbertien. Bull. Soc. Math. France, 93:273–299, 1965.
A. Moudafi and E. Elissabeth. Approximate inertial proximal methods using the enlargement of maximal monotone operators. International Journal of Pure and Applied Mathemtics, 5(3):283–299, 2003.
P. Ochs, T. Brox, and T. Pock. ipiasco: Inertial proximal algorithm for strongly convex optimization. manuscript, 2014.
P. Ochs, Y. Chen, T. Brox, and T. Pock. ipiano: Inertial proximal algorithm for non-convex optimization. manuscript, 2014.
M. J. D. Powell. A method for nonlinear constraints in minimization problems. In Optimization (Sympos., Univ. Keele, Keele, 1968), pages 283–298. Academic Press, London, 1969.
R. T. Rockafellar. Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res., 1(2):97–116, 1976.
R. T. Rockafellar. Monotone operators and the proximal point algorithm. SIAM J. Control Optimization, 14(5):877–898, 1976.
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
