- A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity $\bigo(1/n^2)$ Hedy Attouch (hedy.attouchuniv-montp2.fr) Maicon Marques Alves (maicon.alvesufsc.br) Benar F. Svaiter (benarimpa.br) Abstract: 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)$. Keywords: monotone inclusions; convex minimization; proximal algorithms; fast convergent methods; complexity; relative error; large step condition; subdifferential operators; dissipative dynamics; Lyapunov analysis; weak asymptotic convergence. Category 1: Convex and Nonsmooth Optimization Citation: Download: [PDF]Entry Submitted: 02/15/2015Entry Accepted: 02/15/2015Entry Last Modified: 04/16/2015Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.