DOI: 10.68381/jca23006 ISSN: 0944-6532
A Dynamic Approach to a Proximal-Newton Method for Monotone Inclusions in Hilbert Spaces, with Complexity 𝒪(1/n
2
)
Hedy Attouch, Maicon Marques Alves, Benar Fux Svaiter
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
A
, the evolution is governed by the time dependent operator
I -(I + \lambda(t) {A})^{-1}
I
−
(
I
+
λ
(
t
)
A
)
−
1
, where the positive control parameter
\lambda(t)
λ
(
t
)
tends to infinity as
t \to + \infty
t
→
+
∞
. The tuning of
\lambda (\cdot)
λ
(
⋅
)
is done in a closed-loop way, by resolution of the algebraic equation
\def\bigo{\mathcal{O}\,}\def\norm#1{\|#1\|}\lambda \norm{(I + \lambda {A})^{-1}x -x}=\theta
λ
∥
(
I
+
λ
A
)
−
1
x
−
x
∥
=
θ
, 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
A
=
∂
f
is the subdifferential of a closed convex function
f
f
, we show a
\mathcal{O}\,(1/t^2)
O
(
1
/
t
2
)
convergence property of
f(x(t))
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
\mathcal{O}\,(1/n^2)
O
(
1
/
n
2
)
. In the regular case, we show the global quadratic convergence of an associated proximal-Newton method.