  


A dynamic approach to a proximalNewton method for monotone inclusions in Hilbert spaces, with complexity $\bigo(1/n^2)$
Hedy Attouch (hedy.attouchunivmontp2.fr) 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 closedloop 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 proximallike 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/2015 Modify/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  