A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity $\bigo(1/n^2)$

In a Hilbert setting, we introduce a new dynamic system and associated algorithms aimed at solving by rapid methods, monotone inclusions. Given a maximal monotone operator $A$, the evolution is governed by the time dependent operator $I -(I + \lambda(t) {A})^{-1}$, where, in the resolvent, the positive control parameter $\lambda(t)$ tends to infinity as $t \to + \infty$. The precise 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. We prove the existence and uniqueness of a strong global solution for the corresponding Cauchy problem, and the weak convergence of the trajectories to equilibria. When $A =\partial f$ is the subdifferential of a convex lower semicontinuous proper 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 naturally obtained by time discretization of the continuous dynamic, and which share similar rapid convergence properties. As distinctive features, we allow a relative error tolerance for the solution of the proximal subproblem similar to the ones proposed in [16,17], and a large step condition, as proposed in [10,11]. For general convex minimization problems, we show that the complexity of our method is $\bigo(1/n^2)$.

Article

Download

View PDF