A note on the inertial proximal point method

  • Zhenguo Mu School of Mathematical Sciences, Nanjing Normal University, Nanjing, China
  • Yang Peng Department of Mathematics, Nanjing University, China.
Keywords: Proximal point method (PPM), inertial PPM, maximal monotone operator, alternating inertial PPM.

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.

Published
2015-08-28
How to Cite
Mu, Z., & Peng, Y. (2015). A note on the inertial proximal point method. Statistics, Optimization & Information Computing, 3(3), 241-248. https://doi.org/10.19139/soic.v3i3.124
Section
Research Articles