Optimization Online


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

Hedy Attouch (hedy.attouch***at***univ-montp2.fr)
Maicon Marques Alves (maicon.alves***at***ufsc.br)
Benar F. Svaiter (benar***at***impa.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


Download: [PDF]

Entry Submitted: 02/15/2015
Entry Accepted: 02/15/2015
Entry Last Modified: 04/16/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society