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

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 $A$, the evolution is governed by the time dependent operator $I -(I + \lambda(t) {A})^{-1}$, where the positive control parameter $\lambda(t)$ tends to infinity as $t \to + \infty$. The tuning of $\lambda (\cdot)$ is done in a closed-loop way, by resolution of the algebraic equation $\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 =\partial f$ is the subdifferential of a closed convex function $f$, we show a $\bigo(1/t^2)$ 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, 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 $\bigo(1/n^2)$. In the regular case, we show the global quadratic convergence of an associated proximal-Newton method.