Abstract

In a Hilbert setting, we introduce a new dynamical system and associated algorithms for solving monotone inclusions by rapid methods. Given a maximal monotone operator AA, the evolution is governed by the time dependent operator I−(I+λ(t)A)−1I -(I + \lambda(t) {A})^{-1}, where the positive control parameter λ(t)\lambda(t) tends to infinity as t→+∞t \to + \infty. The tuning of λ(⋅)\lambda (\cdot) is done in a closed-loop way, by resolution of the algebraic equation λ∥(I+λA)−1x−x∥=θ\lambda \norm{(I + \lambda {A})^{-1}x -x}=\theta, where θ\theta is a positive given constant. The existence and uniqueness of a strong global solution for the Cauchy problem follows from Cauchy-Lipschitz theorem. We prove the weak convergence of the trajectories to equilibria, and superlinear convergence under an error bound condition. When A=∂fA =\partial f is the subdifferential of a closed convex function ff, we show a O (1/t2)\bigo(1/t^2) convergence property of f(x(t))f(x(t)) to the infimal value of the problem. Then, we introduce proximal-like algorithms which can be obtained by time discretization of the continuous dynamic, and which share the same fast convergence properties. As distinctive features, we allow a relative error tolerance for the solution of the proximal subproblem similar to the ones proposed by M. V. Solodov and B. F. Svaiter [A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Analysis 7(4) (1999) 323–345; and: A hybrid projection-proximal point algorithm, J. Convex Analysis 6(1) (1999) 59–70], and a large step condition, as proposed by R. D. C. Monteiro and B. F. Svaiter [On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean, SIAM J. Optim. 20(6) (2010) 2755–2787; and: Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems, SIAM J. Optim. 22(3) (2012) 914–935]. For general convex minimization problems, the complexity is O (1/n2)\bigo(1/n^2). In the regular case, we show the global quadratic convergence of an associated proximal-Newton method.

Author information

Contact details are reproduced from the original publication and may be historical.

Maicon Marques Alves

Dep. de Matemática, Universidade Federal de Santa Catarina, 88040-900 Florianópolis, Brazil

maicon.alves@ufsc.br

Benar Fux Svaiter

Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460-320, Brazil

benar@impa.br

Keywords

  • Complexity
  • convex minimization
  • fast convergent methods
  • large step condition
  • monotone inclusions
  • Newton method
  • proximal algorithms
  • relative error
  • subdifferential operators
  • weak asymptotic convergence

Mathematics Subject Classification

34A12, 34A60, 34G25, 37C65, 37L05,47H05, 47J25, 47J30, 47J35, 47N10, 49J55; 49M15, 49M25, 49M37, 65K05, 65K10, 65K15, 65Y20, 90C25, 90C52, 90C53

References

  1. B. Abbas, H. Attouch, B. F. Svaiter: Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces, J. Optim. Theory Appl. 161(2) (2014) 331–360.https://doi.org/10.1007/s10957-013-0414-5Google Scholar
  2. H. Attouch: Viscosity solutions of minimization problems, SIAM J. Optim. 6(3) (1996) 769–806.https://doi.org/10.1137/S1052623493259616Google Scholar
  3. H. Attouch, J. Bolte, B. F. Svaiter: Convergence of descent methods for semialgebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., Ser. A 137(1) (2013) 91–129.https://doi.org/10.1007/s10107-011-0484-9Google Scholar
  4. H. Attouch, P. Redont, B. F. Svaiter: Global convergence of a closed-loop regularized Newton method for solving monotone inclusions in Hilbert spaces, J. Optim. Theory Appl. 157 (2013) 624–650.https://doi.org/10.1007/s10957-012-0222-3Google Scholar
  5. H. Attouch, B. F. Svaiter: A continuous dynamical Newton-like approach to solving monotone inclusions, SIAM J. Control Optim. 49 (2011) 574–598.https://doi.org/10.1137/100784114Google Scholar
  6. J.-B. Baillon: Un exemple concernant le comportement asymptotique de la solution du problème du dt + ∂φ(u) ∋ 0, J. Funct. Anal. 28 (1978) 369–376.https://doi.org/10.1016/0022-1236(78)90093-9Google Scholar
  7. H. Brézis: Opérateurs Maximaux Monotones et Semi-Groupes de Contractions dans les Espaces de Hilbert, North-Holland, Amsterdam (1973).Google Scholar
  8. R. E. Bruck: Asymptotic convergence of nonlinear contraction semigroups in Hilbert space, J. Funct. Anal. 18 (1975) 15–26.https://doi.org/10.1016/0022-1236(75)90027-0Google Scholar
  9. A. Griewank: The modification of Newton’s method for unconstrained optimization by bounding cubic terms, Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge (1981).Google Scholar
  10. O. Güler: New proximal point algorithms for convex minimization, SIAM J. Optim. 2(4) (1992) 649–664.https://doi.org/10.1137/0802032Google Scholar
  11. B. Martinet: Régularisation d’inéquations variationnelles par approximations successives, Rev. Franç. Inform. Rech. Opér. 4(R-3) (1970) 154–158.https://doi.org/10.1051/m2an/197004R301541Google Scholar
  12. R. D. C. Monteiro, B. F. Svaiter: On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean, SIAM J. Optim. 20(6) (2010) 2755–2787.https://doi.org/10.1137/090753127Google Scholar
  13. R. D. C. Monteiro, B. F. Svaiter: Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems, SIAM J. Optim. 22(3) (2012) 914–935.https://doi.org/10.1137/11083085XGoogle Scholar
  14. Y. Nesterov, B. T. Polyak: Cubic regularization of Newton method and its global performance, Math. Program., Ser. A 108(1) (2006) 177–205.https://doi.org/10.1007/s10107-006-0706-8Google Scholar
  15. Z. Opial: Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc. 73 (1967) 591–597.https://doi.org/10.1090/S0002-9904-1967-11761-0Google Scholar
  16. J. Peypouquet, S. Sorin: Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time, J. Convex Analysis 17(3–4) (2010) 1113–1163.https://doi.org/10.68381/jca17068Google Scholar
  17. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper. Res. 1(2) (1976) 97–116.https://doi.org/10.1287/moor.1.2.97Google Scholar
  18. R. T. Rockafellar: Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14(5) (1976) 877–898.https://doi.org/10.1137/0314056Google Scholar
  19. M. V. Solodov, B. F. Svaiter: A hybrid approximate extragradient-proximal point algorithm using the enlargement of a maximal monotone operator, Set-Valued Anal. 7(4) (1999) 323–345.https://doi.org/10.1023/A:1008777829180Google Scholar
  20. M. V. Solodov, B. F. Svaiter: A hybrid projection-proximal point algorithm, J. Convex Analysis 6(1) (1999) 59–70.https://doi.org/10.68381/jca06005Google Scholar
  21. M. Weiser, P. Deuflhard, B. Erdmann: Affine conjugate adaptive Newton methods for nonlinear elastomechanics, Optim. Methods Softw. 22(3) (2007) 413–431.https://doi.org/10.1080/10556780600605129Google Scholar

Suggested citation

H. Attouch, M. Marques Alves, B. F. Svaiter. “A Dynamic Approach to a Proximal-Newton Method for Monotone Inclusions in Hilbert Spaces, with Complexity 𝒪(1/n^2).” Journal of Convex Analysis 23 (2016), No. 1, 139–180. https://doi.org/10.68381/jca23006

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2016. Rights now held by Banach Press LLC.