Convergence Rate of Proximal Inertial Algorithms Associated with Moreau Envelopes of Convex Functions

Hedy Attouch () and Juan Peypouquet ()
Additional contact information
Hedy Attouch: Univ. Montpellier, CNRS, IMAG
Juan Peypouquet: Universidad de Chile, Departamento de Ingeniería Matemática & Centro de Modelamiento Matemático (CNRS UMI2807), FCFM

Chapter Chapter 1 in Splitting Algorithms, Modern Operator Theory, and Applications, 2019, pp 1-44 from Springer

Abstract: Abstract In a Hilbert space setting ℋ $${\mathcal H}$$ , we develop new inertial proximal-based algorithms that aim to rapidly minimize a convex lower-semicontinuous proper function Φ : ℋ → ℝ ∪ { + ∞ } $$\varPhi : \mathcal H \rightarrow {\mathbb R} \cup \{+\infty \}$$ . The guiding idea is to use an accelerated proximal scheme where, at each step, Φ is replaced by its Moreau envelope, with varying approximation parameter. This leads to consider a Relaxed Inertial Proximal Algorithm (RIPA) with variable parameters which take into account the effects of inertia, relaxation, and approximation. (RIPA) was first introduced to solve general maximally monotone inclusions, in which case a judicious adjustment of the parameters makes it possible to obtain the convergence of the iterates towards the equilibria. In the case of convex minimization problems, convergence analysis of (RIPA) was initially addressed by Attouch and Cabot, based on its formulation as an inertial gradient method with varying potential functions. We propose a new approach to this algorithm, along with further developments, based on its formulation as a proximal algorithm associated with varying Moreau envelopes. For convenient choices of the parameters, we show the fast optimization property of the function values, with the order o(k −2), and the weak convergence of the iterates. This is in line with the recent studies of Su-Boyd-Candès, Chambolle-Dossal, Attouch-Peypouquet. We study the impact of geometric assumptions on the convergence rates, and the stability of the results with respect to perturbations and errors. Finally, in the case of structured minimization problems smooth + nonsmooth, based on this approach, we introduce new proximal-gradient inertial algorithms for which similar convergence rates are shown.

Keywords: Inertial proximal algorithms; Lyapunov analysis; Maximally monotone operators; Moreau envelopes; Nesterov accelerated gradient method; Nonsmooth convex minimization; Proximal-gradient algorithms; Relaxation; 37N40; 46N10; 49M30; 65K05; 65K10; 90B50; 90C25 (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-030-25939-6_1

Ordering information: This item can be ordered from
http://www.springer.com/9783030259396

DOI: 10.1007/978-3-030-25939-6_1

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().