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

作者：Attouch Hedy^*; Alves M Marques; Svaiter Benar F

来源：Journal of Convex Analysis, 2016, 23(1): 139-180.

• Complexity
• convex minimization
• fast convergent methods
• large step condition
• monotone inclusions
• Newton method
• proximal algorithms
• relative error
• subdifferential operators
• weak asymptotic convergence

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 -> +infinity. The tuning of lambda(.) is done in a closed-loop way, by resolution of the algebraic equation lambda parallel to(I + lambda A)(-1) x - x parallel to = 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 = Of is the subdifferential of a closed convex function f, we show a O(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 in [19, 20], and a large step condition, as proposed in [12, 13]. For general convex minimization problems, the complexity is O(1/n(2)). In the regular case, we show the global quadratic convergence of an associated proximal-Newton method.

• 出版日期2016