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

H. Attouch ; M. Marques Alves ; B. F. Svaiter

Journal of convex analysis, Tome 23 (2016) no. 1, pp. 139-18

Résumé

\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 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.

Détail

Classification : 34A12, 34A60, 34G25, 37C65, 37L05,47H05, 47J25, 47J30, 47J35, 47N10, 49J55, 49M15, 49M25, 49M37, 65K05, 65K10, 65K15, 65Y20, 90C25, 90C52, 90C53
Mots-clés : Complexity, convex minimization, fast convergent methods, large step condition, monotone inclusions, Newton method, proximal algorithms, relative error, subdifferential operators, weak asymptotic convergence