A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n^2)
arXiv:1502.04286
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 , the evolution is governed by the time dependent operator , where the positive control parameter tends to infinity as . The tuning of is done in a closed-loop way, by resolution of the algebraic equation $λ\norm{(I + λ{A})^{-1}x -x}=θ$, 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 is the subdifferential of a closed convex function , we show a $\bigo(1/t^2)$ convergence property of 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 in ~\cite{So-Sv1, So-Sv2}, and a large step condition, as proposed in~\cite{MS1,MS2}. 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.
Some minor changes have been made; results on superlinear and quadratic convergence have also been added, on Subsections 3.2 and 7.1, respectively