
Journal of Convex Analysis 23 (2016), No. 1, 139180 Copyright Heldermann Verlag 2016 A Dynamic Approach to a ProximalNewton Method for Monotone Inclusions in Hilbert Spaces, with Complexity O(1/n^{2}) Hedy Attouch IMAG UMR CNRS 5149, Université Montpellier II, Place E. Bataillon, 34095 Montpellier, France hedy.attouch@univmontp2.fr Maicon Marques Alves Dep. de Matemática, Universidade Federal de Santa Catarina, 88040900 Florianópolis, Brazil maicon.alves@ufsc.br Benar Fux Svaiter Instituto de Matemática Pura e Aplicada, Estrada Dona Castorina 110, Jardim Botânico, Rio de Janeiro, RJ 22460320, Brazil benar@impa.br [Abstractpdf] \newcommand{\bigo}{\mathcal{O}\,} \newcommand{\norm}[1]{\#1\} 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 closedloop 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 CauchyLipschitz 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 proximallike 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 extragradientproximal point algorithm using the enlargement of a maximal monotone operator, SetValued Analysis 7(4) (1999) 323345; and: A hybrid projectionproximal point algorithm, J. Convex Analysis 6(1) (1999) 5970], 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) 27552787; and: Iterationcomplexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems, SIAM J. Optim. 22(3) (2012) 914935]. 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 proximalNewton method. Keywords: Complexity, convex minimization, fast convergent methods, large step condition, monotone inclusions, Newton method, proximal algorithms, relative error, subdifferential operators, weak asymptotic convergence. MSC: 34A12, 34A60, 34G25, 37C65, 37L05,47H05, 47J25, 47J30, 47J35, 47N10, 49J55; 49M15, 49M25, 49M37, 65K05, 65K10, 65K15, 65Y20, 90C25, 90C52, 90C53 [ Fulltextpdf (297 KB)] for subscribers only. 