A Dynamic Approach to a Proximal-Newton Method for Monotone Inclusions in Hilbert Spaces, with Complexity O(1/n2)

International audienceIn a Hilbert setting, we introduce a new dynamical system and associated algorithms for solving monotone inclusions by rapid methods. Given a maximal monotone operator A, the evolution is governed by the time dependent operator I −(I +λ(t)A) −1, where the positive control parameter λ(t) tends to infinity as t → +∞. The tuning of λ(·) is done in a closed-loop way, by resolution of the algebraic equation λk(I +λA) −1x−xk = θ, where θ 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 = ∂f is the subdifferential of a closed convex function f, we show a O (1/t2) convergence property of 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, SetValued 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 1 minimization problems, the complexity is O (1/n2). In the regular case, we show the global quadratic convergence of an associated proximal-Newton method