Optimisation et systèmes dissipatifs en mathématiques
Optimisation et systèmes dissipatifs en mathématiques
Composition du jury:
iv
Abstract
This thesis is devoted to the study of dissipative dynamical systems and to the
design of algorithms related to optimization problems (such as convex minimization,
and more generally, the computation of zeros of monotone operators) in a real Hilbert
framework.
In a first step, we propose and study, in a continuous framework, fast Newton-like
dynamics related to these problems. The considered dynamical system is first inspired
by the reformulation of a (stabilized) second order Nesterov-type equation (by adding
a geometric Hessian damping) for the minimization of convex functions. This strategy
is then extended to the case of general monotone operators. This allows us to treat
simultaneously the two considered optimization problems, via first-order dissipative
system that only involves the gradient of the objective function and the Yosida
approximation of a general operator. This last formulation constitutes a particularly
well-adapted framework for the design of numerical schemes based upon discrete
variants of our continuous model. Indeed, it allows us to get rid of the temporal
discretization of constraining terms which could lead to computationally expensive
and/or processes of limited applications.
Next, we focus on convex and non-smooth structured minimization problems,
by using new class of algorithms derived from a temporal discretization of our first-
order model. The process AFB (Accelerated Forward-Backward), which was recently
proposed as a convergent variant of FISTA (Fast Iterative Shrinkage-Thesholding
Algorithm), is obtained as a special case of our numerical scheme. In addition to the
well-known convergence properties for AFB, we prove the fast convergence to zero of
the subgradients of the objective function. This last feature was established so far
for sufficiently smooth functions only.
Finally, regarding the numerical approach to more general structured monotone
inclusions, we propose and study a Forward-Backward algorithm incorporating an
inertial term, a relaxation factor and a correction term. In addition to the convergence
of the method, we prove similar properties to those obtained for convex structured
minimization in term of discrete velocity and fixed-point residual.
Notations ix
Introduction 1
vii
4 Algorithmes forward-backward accélérés pour la résolution d’inclu-
sions monotones structurées 125
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.2 Propriétés de type Lyapunov . . . . . . . . . . . . . . . . . . . . . . . 132
4.3 Analyse de la convergence de la méthode. . . . . . . . . . . . . . . . . 141
4.4 Une variante plus générale de l’algorithme proposé . . . . . . . . . . . 152
4.5 Simulations numériques . . . . . . . . . . . . . . . . . . . . . . . . . . 156
4.6 Annexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
Bibliographie 167
viii
Notations
Ensembles
∅ : désigne l’ensemble vide.
N := {0, 1, 2, 3 . . . } désigne l’ensemble des entiers naturels.
N∗ := {1, 2, 3 . . . } désigne l’ensemble des entiers naturels non nuls.
Z := {. . . − 2, −1, 0, 1, 2 . . . } désigne l’ensemble des entiers relatifs.
R : l’ensemble des nombres réels.
R+ : l’ensemble des nombres réels positif.
L1 ([a, b], H) : ensemble des fonctions Lebesgue-intégrables sur [a, b] à valeurs dans H.
L∞ [0, ∞) : ensemble des fonctions essentiellement bornées sur [0, +∞[.
2X : ensemble des parties de l’ensemble X .
Espace de Hilbert
H : espace de Hilbert réel.
⟨., .⟩ : produit scalaire sur H.
∥.∥ : norme induite par le produit scalaire sur H.
→ : convergence forte dans H.
⇀ : convergence faible dans H.
I : désigne l’opérateur identité sur H.
Opérateurs multivoques
A : H → 2H : opérateur multivoque sur H.
gr A := {(x, u) ∈ H × H, u ∈ Ax} : graphe de A.
dom A := {x ∈ H, Ax ̸= ∅} : domaine de A.
ran A := A(H) : l’image de A.
zer A := {x ∈ H | 0 ∈ Ax} : ensemble des zéros de A.
A−1 := H → 2H : u 7→ {x ∈ H, u ∈ Ax} : inverse de A.
JλA := (I + λA)−1 : résolvante de A d’indice λ > 0.
Aλ := λ1 (I − Jλ A) : approximation de Yosida de A
d’indice λ > 0.
ix
Fonctions
gr f := {(x, y) ∈ H × R | f (x) = y} : graphe de f : H → [−∞, +∞].
epi f := {(x, y) ∈ H × R | y ≥ f (x)} : épigraphe de f : H → [−∞, +∞].
dom f := {x ∈ H | f (x) < ∞} : domaine effectif de f : H → [−∞, +∞].
∇f : gradient de f : H → R.
argmin f : ensemble des minimiseurs de f .
proxµf : opérateur proximal de f d’indice µ > 0.
∂f (u) : sous-différentiel de Fenchel de f en u.
∀(x, y) ∈ gr A, ∀(y, y ′ ) ∈ gr A, ⟨y − y ′ , x − x′ ⟩ ≥ 0
x
Introduction
1
Introduction
2
qui a été récemment discutée comme une variante améliorée de FISTA (« Fast Itera-
tive Thresholding Algorithm ») est retrouvée comme cas particulier de l’algorithme
proposé pour un certain jeu de paramètres. Sur la base d’une suite de type énergie,
nous montrons que l’algorithme étudié dans ce chapitre jouit des propriétés bien
connues de AFB, à savoir que celui-ci génère des suites convergentes (xn ) qui mi-
nimisent les valeurs de la fonction objectif avec un taux de o(n−2 ). Notre méthode
offre, cependant, quelques degrés de liberté supplémentaires comparée à AFB grâce
à un réglage approprié des paramètres qui peuvent être utilisés pour influencer
(accélérer) la convergence des itérés. Une autre spécificité importante du schéma
proposé est qu’il peut être considéré comme un modèle discret issu d’une formulation
du premier ordre du système dynamique de type Newton étudié au chapitre 2. Ceci
nous permet d’étendre au cadre non lisse, une propriété de convergence rapide vers
zéro des sous-gradients, établie jusqu’à présent pour les dynamiques discrètes de
type Newton avec des potentiels lisses uniquement. En particulier, comme nouveau
résultat, nous montrons que cette dernière propriété s’applique également à AFB.
Des simulations numériques sont en outre réalisées afin d’illustrer les propriétés des
algorithmes considérés par rapport à d’autres algorithmes existants.
Le chapitre 4 est consacré à l’étude d’une généralisation, au cas des inclusions
monotones structurées, de l’algorithme étudié au chapitre 3 dans le cadre de la
minimisation convexe structurée. Plus précisément, nous développons un algorithme
de type Forward-Backward pour le calcul des zéros de la somme d’un nombre fini
d’opérateurs maximaux monotones. On considère, en premier lieu, une modification de
la méthode classique Forward-Backward pour deux opérateurs monotones généraux,
en incorporant un terme inertiel (proche des techniques d’accélération introduites
par Nesterov), un terme de relaxation constant ainsi qu’un terme correcteur. Dans
un cadre Hilbertien réel, nous démontrons la convergence faible des itérés générés par
notre méthode ainsi que des taux o(n−1 ) en termes de vitesse discrète et de résidu du
point fixe au lieu des taux classiques de O(n−1 ). Dans un second temps, l’algorithme
proposé est ensuite adapté à des inclusions monotones plus générales.
Le chapitre 5 présente, quant à lui, les conclusions de cette thèse ainsi que quelques
perspectives de recherches en lien avec ce travail.
3
Chapitre 1
1.1 Contexte
Dans ce chapitre, H désigne un espace de Hilbert réel pour lequel on note ⟨., .⟩
le produit scalaire et ∥ . ∥ := ⟨., .⟩, la norme associée. Considérons le problème
p
Nous supposons que S := argminH Θ(x) ̸= ∅ et nous passons en revue les algorithmes
de minimisation classiques ainsi que leurs avantages et inconvénients suivant leur
domaine d’applications et les hypothèses requises sur les fonctions f et g.
5
Chapitre 1 – Rappels : travaux séminaux
Notons que les points d’équilibres des trajectoires x(.) générées par (1.2.4) sont
exactement les éléments qui minimisent de f . D’un point de vue pratique, une
discrétisation de (1.2.4) donne pour λk > 0
xk+1 − xk
(1.2.5) + ∇f (xk ) = 0 ⇐⇒ xk+1 = xk − λk ∇f (xk ).
λk
Cette méthode générale est connue sous le nom de « méthode de la plus grande pente »
ou « méthode de descente de gradient ». Il existe plusieurs variantes basées sur la
descente de gradient (à pas fixe, à pas optimal, etc.) suivant les valeurs prises par la
suite (λk ). Lorsque f est à gradient lipschitzien, la méthode de descente du gradient
associée au problème (1.2.3) possède un taux de convergence en valeurs suivant
6
1.2. Minimisation de fonctions convexes
pour un certain 0 < ρ < 1 (voir [83, Theorem 2.1.15]), ce qui représente une
convergence linéaire.
Définition 1.2.1. Soit f : H → R ∪ {+∞} une fonction convexe propre. On dit que
u ∈ H est un sous-gradient de f en x ∈ dom f si
Cette dernière a été étudiée par plusieurs auteurs (voir [21, 35]). Ceux-ci ont notam-
ment démontré la convergence faible des trajectoires vers un élément de argminH f ,
7
Chapitre 1 – Rappels : travaux séminaux
la suite (fk∗ )k≥0 ainsi générée est clairement décroissante. Sous certaines conditions
sur la suite de pas (λk )k∈N et en supposant que la fonction f soit lipschitzienne, il a
été démontré (voir [23, Theorem 8.13] et [83, Theorem 3.2.2]) que
√
(1.2.13) fk∗ − f (x∗ ) = O(1/ k),
On constate alors que la méthode des sous-gradients se révèle être moins performante
que la descente de gradient. Ainsi l’utilisation des sous-gradients pour résoudre le
problème (1.1.2) ne permet pas d’avoir une convergence comparable à la descente de
gradient donné par l’algorithme 1. Une autre approche s’avère donc nécessaire.
8
1.2. Minimisation de fonctions convexes
Une méthode développée vers 1970 par Martinet [75, 76] (voir aussi [69, 89])
consiste à choisir x0 ∈ H ainsi qu’une suite (λk ) ⊂]0, +∞[ et effectuer pour k ≥ 0
Remarque 1.2.3. Rappelons que l’opérateur proximal peut être vu comme une
généralisation de l’opérateur de projection [22, 45]. En effet, lorsque f := ιC est la
fonction indicatrice d’un convexe fermé C ⊂ H alors pour tout λ > 0 on a
1 1
proxλf (x) = argmin ιC (v) + 2λ
∥v − x∥22 = argmin 2λ
∥v − x∥22 = PC (x),
v∈H v∈C
Remarque 1.2.4. L’opérateur proximal peut aussi être vu comme un moyen de créer
un schéma de descente de gradient implicite. En effet, en supposant que la fonction f
introduite dans la Définition 1.2.2 soit continûment différentiable, une discrétisation
implicite en temps de l’équation différentielle (1.2.4) donne pour λk > 0
xk+1 − xk
(1.2.19) + ∇f (xk+1 ) = 0.
λk
9
Chapitre 1 – Rappels : travaux séminaux
où (λk ) est une suite réelle strictement positive et où l’application prox est définie par
(1.2.17). À l’aide de la Remarque 1.2.4, on observe que le schéma (1.2.20) combine
une étape de descente explicite (forward) concernant la fonction régulière f et une
étape implicite (backward) concernant la fonction g.
Notons que le schéma (1.2.20) peut s’écrire sous la même forme que (1.2.5),
Il a été démontré, sous les hypothèses (A1), (A3) et (A3) ainsi que pour
λk := λ ∈]0, 1/L[, que les itérés xk générés par l’algorithme de la descente de gradient
10
1.2. Minimisation de fonctions convexes
Remarque 1.2.5. De nombreux auteurs [2, 6, 10, 61, 56] ont analysé le modèle
continu général provenant de (1.2.22) donné, pour une fonction réelle positive λ, par
Cette dernière peut être vue comme une amélioration du système (1.2.4) par l’ajout
d’un terme d’amortissement λ(t)ẋ(t). Dans le cas où λ(t) = λ > 0, Alvarez [2]
11
Chapitre 1 – Rappels : travaux séminaux
Bien que les schémas (1.2.24) et (1.2.22) fassent tous les deux intervenir un terme
inertiel, la différence majeure se situe dans l’évaluation du gradient. En effet, celle-ci
se fait en yk dans (1.2.24) et en xk pour (1.2.22). Cette différence peut être vu comme
une correction de la direction à prendre pour le calcul de l’itéré xk+1 suivant. Il a été
démontré [24, Theorem 4.4], sous les hypothèses (A1), (A2) et (A3), que la suite
(xk )k≥0 produite par l’algorithme (1.2.24) avec un pas constant λk := λ ∈]0, 1/L]
vérifie (f + g)(x) − minH (f + g) = O(k −2 ) (lorsque k → +∞).
12
1.3. Minimisation stochastique : cas du machine learning
Attouch-Peypouquet [14] ont démontré, pour α > 3, que la suite (xk )k générée par
(1.2.25) satisfait Θ(xk ) − Θ(x∗ ) = o(k −2 ) (où x∗ ∈ S) ainsi que ∥xk+1 − xk ∥ = o(k −1 )
où k désigne le nombre d’itérations.
Notons que plusieurs auteurs [16, 19, 20, 105] ont étudié le modèle continu associé
à (1.2.25) (dans le cas non proximal) donné par
α
(1.2.26) ẍ(t) + ẋ(t) + ∇f (x(t)).
t
Cette équation est à rapprocher de (1.2.23) dans le cas particulier où λ(t) = αt−1
avec α > 0, ce dernier terme agissant comme un amortissement visqueux (autrement
dit qui tend lentement vers 0). Il a notamment été prouvé (voir [16]) que, pour α ≥ 3,
les trajectoires générées par (1.2.26) vérifient f (x(t)) − minH f = O(t−2 ) lorsque
t → +∞.
différentiables,
(B2) g : H → R ∪ {−∞, +∞} est une fonction convexe propre et inférieurement.
On retrouve couramment ce type de problème en statistique et en machine
learning pour effectuer des régressions ou des classifications régularisées. Pour des
données d’entraînement (ai , bi ), les fonctions fi les plus couramment utilisées sont
— Lasso : avec fi (w) := 21 (bi − ⟨x, ai ⟩)2 et g(x) := µ∥x∥1 ,
— Ridge régularisée : fi (x) := 21 (bi − ⟨x, ai ⟩)2 et g(w) := µ∥w∥22 ,
— Logistique régularisée : fi (x) := ln(1 + exp(−bi ⟨x, ai ⟩)), et g(x) = µ∥x∥1
(ou alors g(w) = µ∥x∥22 ),
— Elastic net : fi (x) := ln(1 + exp(−bi ⟨x, ai ⟩)), et g(x) = µ1 ∥x∥1 + µ2 ∥x∥22 .
13
Chapitre 1 – Rappels : travaux séminaux
1. [Link]
2. [Link]
14
1.3. Minimisation stochastique : cas du machine learning
constitué des n gradients ∇fi . Cela conduit alors à effectuer beaucoup d’opération
et de calculs à chaque itération, et de plus cette complexité s’accroît linéairement
à mesure que n augmente. Ce schéma se révèle alors être mal adapté au problème
(1.3.30). Une méthode devenue classique permettant de surmonter cette difficulté,
tout en gardant la forme générale et la simplicité du schéma (1.3.29), consiste à
remplacer le gradient ∇f par un estimateur sans biais ∇k de celui-ci, de telle sorte
que E(∇k ) = ∇f (xk ). Il s’agit là de l’idée générale des méthodes de gradient dites
« stochastiques ».
Les méthodes de type gradient stochastiques ne sont pas récentes et remontent
aux années 1950 [64, 96], mais elles se sont beaucoup développées ces dernières
années compte tenu du développement du machine-learning et de la simplicité de
leur implémentation [27, 28, 102].
15
Chapitre 1 – Rappels : travaux séminaux
16
1.3. Minimisation stochastique : cas du machine learning
b
1X
(1.3.33) ∇k := fi .
c j=1 j
Plutôt que d’utiliser une suite (λk )k∈N décroissante afin de diminuer la variance,
il s’avère plus judicieux d’avoir un meilleur estimateur du gradient ∇f , i.e, remplacer
∇k := ∇fik dans (1.3.30) par un nouvel estimateur de telle sorte que la variance de
ce nouvel estimateur diminue (en moyenne) au fil des itérations. D’abord Johnson et
Zhang [63] pour le cas d’une seule fonction f puis Xiao et Zhang [109] pour la version
proximale (correspondant au problème (1.3.27)) proposèrent de choisir l’estimateur
On constate alors que les tentatives de réduction de la variance pour les algorithmes
de type stochastiques induisent une quantité de travail et un coût supplémentaire.
17
Chapitre 1 – Rappels : travaux séminaux
Si l’on fait le choix d’utiliser des pas (λk ) constant au lieu de pas décroissant,
alors la convergence de la méthode stochastique (1.3.30) peut se décomposer en
deux cas (voir [67] et [79, Proposition 2.4]). Le premier cas va dépendre de k et
converger linéairement vers 0 tandis que le deuxième cas sera indépendant de k mais
ne convergera pas vers 0. Ainsi, avec un pas λk = λ constant, l’itération (1.3.30) aura
une convergence linéaire jusqu’a un certain point pour lequel les valeurs oscilleront
et en général les itérations n’iront pas plus loin, car, la convergence de la méthode
(1.3.30) avec un pas constant n’a été démontrée que sous des hypothèses très fortes
sur les fonctions fi (voir [104]).
18
1.4. Cas général des inclusions monotones
Une des méthodes parmi les plus couramment utilisées pour résoudre (1.4.36) est la
méthode du point proximal qui consiste à effectuer pour x0 ∈ H et (λk ) ⊂]0, +∞[
l’algorithme suivant
19
Chapitre 1 – Rappels : travaux séminaux
qui correspond au cas général de (1.2.10). La méthode (1.4.37) a, par la suite, fait
l’objet de nombreuses variantes relaxées et inertielles (voir [3, 8, 12, 13, 46]) dans le
but d’obtenir des taux de convergence similaires à ceux atteints dans le cadre de la
minimisation convexe.
Algorithme de Douglas-Rachford
Sous la condition zer(A + B) ̸= ∅, l’algorithme de D-R génère des suites (xk ) qui
convergent faiblement vers un élément x∗ ∈ H vérifiant JλB (x∗ ) ∈ zer(A + B) (voir
[22, Theorem 26.11]). Cependant, bien que la méthode (1.4.39) ne nécessite pas
d’hypothèses particulières sur les opérateurs A et B, celle-ci requiert néanmoins le
calcul des résolvantes de A et de B, ce qui peut s’avérer coûteux en pratique, voire
restrictif lorsque la résolvante d’un des opérateurs est difficile à calculer.
Algorithme Forward-Backward
Lorsque l’opérateur B est univoque, une autre approche pour résoudre (1.1.1)
consiste effectuer l’algorithme « Forward-Backward » [69, 89]
20
1.4. Cas général des inclusions monotones
Algorithme Forward-Backward-Forward
21
Chapitre 2
23
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
(2.1.1) ẍ(t) + τ (t)ẋ(t) + β dtd (∇Φ(x(t)) + εAλ(t) x(t)) + η(t)(∇Φ(x(t)) + εAλ(t) x(t)) = 0,
(2.1.2) ε ≥ 0, β = 1, τ (.) = κ − θ − θ̇
θ
et η(.) = κ − θ̇θ ,
κν(t) − ν̇(t)
(2.1.3) θ(t) = ,
ν(t) + e
1
avec x(0) = x0 et y(0) = − θ(0) (ẋ0 + ∇Φ(x0 ) + εAλ(0) x0 ) + x0 .
24
2.1. Résumé et principaux résultats
25
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
(2.1.10a) 0< 2M
ρ(0)
< e, où ρ(0) = κ − ν̇(0)
ν(0)
.
(ν + e)2
(2.1.10b) λ = λc , pour une constante λc > ( 4ϵ ) inf s∈( 2M ,e) 1
s(e−s)
.
θ ρ(0)
S’agissant du cas ϵ > 0 (autrement dit lorsque Aλ est pris en compte dans (2.1.4))
nous considérons les hypothèses supplémentaires suivantes :
Z +∞
ϵ
(2.1.11) ϵν ∈ L ([0, +∞[) et
(3) ∞
3
dt < +∞.
0 ν (t)
26
2.1. Résumé et principaux résultats
Enfin, en effectuant une discrétisation en temps pour h > 0, nous suggérons deux
algorithmes selon les cas suivants :
– Dans le cas où A = 0 et Φ := Θsm + Θns avec Θsm : H → R une fonction
convexe différentiable et Θns : H → R ∪ {+∞} une fonction convexe et semi-continue
inférieurement, on obtient (pour h > 0)
1+hθk−1
(2.1.28a) zk−1 = yk−1 + κh
(yk − yk−1 ),
λk−1
(2.1.28a) xk = z
λk−1 +h k−1
+ h
JA (z ),
λk−1 +h λk−1 +h k−1
Notons qu’une seule évaluation du gradient est nécessaire pour effectuer l’algorithme
(2.1.27) et une seule évaluation proximale de A est requise pour (2.1.28).
27
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Abstract
In a Hilbert framework, we discuss a continuous Newton-like model that is well-
adapted in view to numerical purposes for solving convex minimization and more
general monotone inclusion problems. Algorithmic solutions to these problems were
recently inspired by implicit temporal discretizations of the (stabilized) continuous
version of Nesterov’s accelerated gradient method with an additional Hessian damping
term (so as to attenuate the oscillation effects). Unfortunately, due to the presence
of the Hessian term, these discrete variants require several gradients or proximal
evaluations (per iteration). An alternative methodology can be realized by means
of a first-order model that no more involves the Hessian term and that can be
extended to the case of an arbitrary maximally monotone operator A. Our first-
order model originates from the reformulation of a closely related variant to the
Nesterov-like equation. Its dynamics are studied (simultaneously) with regard to
convex minimization and monotone inclusions by considering it when governed by
the sum of the gradient of a convex differentiable function and (up to a multiplicative
constant) the Yosida approximation of a maximally monotone operator, with an
appropriate adjustment of the regularization parameter. It turns out that our model,
offers a new framework for discrete variants, while keeping the main asymptotic
features of the (stabilized) Nesterov-like equation. Two new algorithms are then
suggested relative to the considered optimization problems.
1. Labarre, F., Maingé, PE. First-Order Frameworks for Continuous Newton-like Dynamics
Governed by Maximally Monotone Operators. Set-Valued Var. Anal (2021). [Link]
1007/s11228-021-00593-1
28
2.2. Article en anglais
2.2.1 Introduction
Let H be a real Hilbert space with inner product and induced norm denoted by ⟨., .⟩
and ∥.∥, respectively. The purpose of this paper is to propose fast continuous Newton-
like dynamics that are intended to offer a well-adapted framework for the design of
new performing (reliable and computationally cheap) approximation methods for
two particular problems : the minimization of a convex function Φ : H → R and the
computation of a zero of an arbitrary maximally monotone operator A : H → 2H .
These are issues of great importance that encompass many real-world problems
arising in equilibrium theory and game theory (in the economic field) but also in
partial differential equations to name but a few [25, 33, 50, 95] (also see [26, 48, 98,
105] for related topics).
The above methodology is commonly used in optimization, by considering appro-
priate discrete counterparts of evolution equations whose trajectories are anchored to
the solution set of some considered problem. Nonetheless, such a continuous model
is required to have a nice form so as to avoid the presence of some constraining
terms that can lead to numerical methods that are computationally expensive or of
limited effectiveness in applications. This applies even more now that most of the
pertinent models (dedicated to the development of speed up optimization processes)
rely upon second-order Newton-like dynamics that involves the Hessian of an objec-
tive function (see, e.g., Attouch-Chbani-Fadili-Riahi [18], Shi-Du-Jordan-Su [103],
for convex minimization) or the derivative of a time-dependent operator (see, e.g.,
Attouch-László [12, 11], for monotone inclusions).
Specifically, we propose simultaneously (from a mathematical viewpoint), for
both the considered problems, a continuous framework with a view to designing
accelerated variants of (existing) related algorithms, without any embarrassing terms
or restrictive assumptions on the involved operators. Two simple algorithms are then
suggested from this setting. In particular, only one proximal evaluation of A, for
approximating its zeroes, will be required per iteration compared with the discrete
model proposed in [12] with the same acceleration purposes. A similar advantage
is also obtained relative to convex differentiable minimization problems. Only one
evaluation of the gradient of Φ will be required per iteration in comparison with the
29
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Our strategy consists first of considering, when Φ is C 2 and for some β > 0 and
some real-valued functions τ (.) and η(.), the following second-order equation :
d
(2.2.1) ẍ(t) + τ (t)ẋ(t) + β Ψ(t, x(t)) + η(t)Ψ(t, x(t)) = 0,
dt
d
(2.2.3) ẍ(t) + αt−1 ẋ(t) + β
Aλ(t) x(t) + Aλ(t) x(t) = 0.
dt
30
2.2. Article en anglais
- The model (2.2.3) has been recently studied by Attouch-László [11]. Its trajecto-
ries, under the conditions α > 1, β ≥ 0 and λ(t) = λ̄t2 with λ̄ > (α−1)−2 , were shown
to be weakly convergent, along with the rates ∥ẋ(t)∥ = o(t−1 ), ∥Aλ(t) x(t)∥ = o(t−2 ),
and the integral estimates
R +∞ R +∞
t0
t∥ẋ(t)∥2 dt < ∞, t0
t−1 (λ(t)∥Aλ(t) x(t)∥)2 dt < ∞ (for t0 > 0).
Let us mention that the numerical process considered by Attouch-László [12] comes
from a temporal implicit discretization of (2.2.3).
It would be interesting to obtain similar results that in [11, 15] by using different
parameters τ and η that primarily lead to a better suited framework for discrete
models.
The sequel of our strategy consists of using the appropriate set of parameters :
(2.2.4) β = 1, τ (.) = κ − θ − θ̇
θ
and η(.) = κ − θθ̇ ,
for some κ > 0 and some positive mapping θ(.). Let us discuss the motivations for
these parameters :
- On the one hand, we show (see Proposition 2.2.1) that (2.2.1) can be rewritten
as the first-order differential system
(2.2.5a)
ẋ(t) + ∇Φ(x(t)) + ϵAλ(t) x(t) + θ(t)(y(t) − x(t)) = 0,
(2.2.5b) ẏ(t) + κ(y(t) − x(t)) = 0,
which still makes sense when Φ is only C 1 and which can be easily generalized to
the non-smooth case of Φ.
- On the other hand, via (2.2.5) we can obtain closely related models to (2.2.2)
and (2.2.3) when choosing the specific parameter
κν(t) − ν̇(t)
(2.2.6) θ(t) = ,
ν(t) + e
along with some constant e > 0 and some positive and differentiable mapping ν.
Indeed, taking (for instance) ν(t) = M t + ν0 with M > 0 and ν0 > 0, we obtain (see
31
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Remark 2.2.3) that the second-order system (2.2.1) holds with parameters τ and η
−1
such that τ (t) ∼ (1+κe)M
t
and η(t) ∼ κ (as t → ∞). This observation suggests that
(2.2.1) with parameters given by (2.2.4) and (2.2.6) (together with an appropriate
choice of ν) asymptotically behaves like (2.2.2) and (2.2.3), while its equivalent
first-order formulation (2.2.5) is highly suitable for numerical purposes.
32
2.2. Article en anglais
where λ(t) ∼ λ̄t2 as t → ∞ (for some constant λ̄). The proof of our convergence
results relies on Lyapunov properties for the functional Es,q related to (2.2.6)-(2.2.5)
and defined for (s, q) ∈ [0, ∞) × S, by
where Φ̃ = Φ − inf H Φ.
[Link] Assumptions
Given some positive parameters κ and ν(.) we set ρ := κ − νν̇ (if ν is differentiable)
and we assume that the following conditions are satisfied :
The parameter λ(.) and the constant e involved in (2.2.6) are assumed to be such
that :
(2.2.12a) 0< 2M
ρ(0)
< e, where ρ(0) = κ − ν̇(0)
ν(0)
.
(ν + e)2
(2.2.12b) λ = λc , with some constant λc > ( 4ϵ ) inf s∈( 2M ,e) 1
s(e−s)
.
θ ρ(0)
33
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Regarding the case ϵ > 0 (which means that Aλ is taken into account in our
problem) we need the supplementary requirements on ν :
Z +∞
ϵ
(2.2.15) ϵν (3) ∞
∈ L [0, ∞), dt < ∞
0 ν 3 (t)
The present paper is organized as follows. Section 2 exposes some specific results
regarding our model (equivalence between the first and second order systems, existence
and uniqueness of trajectories and basic properties regarding the involved parameters).
Section 3 is devoted to the construction of a Lyapunov functional associated with
our first order system. Section 4 presents our main convergence results. In Section
5 we suggest algorithms issued from discrete variants of our continuous model for
monotone inclusion problems and convex minimization.
Let us expose the equivalence between the two systems (2.2.1) and (2.2.5).
Remark 2.2.1. Let z ∈ (ϵA)−1 (0) (from (H3)), let x : [0, ∞) → H, and assume
that λ(t) ≥ λm > 0 (for t ≥ 0). Then, by Lemma A.1, for any {t1 , t2 } ⊂ [0, ∞) we
readily obtain
∥ϵAλ(t1 ) x(t) − ϵAλ(t2 ) x(t)∥ ≤ 3ϵ |λ(t1 )−λ(t
λ2m
2 )|
∥x(t) − z∥.
Consequently, it is readily checked that the mapping A : t → ϵAλ(t) x(t) is Lipschitz
continuous on bounded intervals of [0, ∞), provided that x and λ are so. This gua-
rantees that A is absolutely continuous on [0, ∞), hence, that it is also differentiable
almost everywhere on [0, ∞).
34
2.2. Article en anglais
(2.2.16) ẍ + τ ẋ + d
dt
Ψ(., x) + ηΨ(., x) = 0,
1
with x(0) = x0 and y(0) = − θ(0) (ẋ0 + Ψ(0, x0 )) + x0 .
with initial conditions (x(0), z(0)) = (x0 , −(ẋ0 + Ψ(0, x0 )). Multiplying (2.2.18a) by
η, and adding the resulting equality to (2.2.18b) allows us to get rid of the term
η(t)Ψ(t, x(t)) in (2.2.18b), so as to obtain
Let us now define y = 1θ z + x. It follows that z = θ(y − x) and ż = θ(ẏ − ẋ) + θ̇(y − x).
35
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Using also τ = κ − θ − θ̇
θ
and η = κ − θθ̇ , we can successively rewrite (2.2.19b) as
follows :
0 = η ẋ + ηz + ż − τ ẋ
= κ − θ̇θ ẋ + κ − θ̇θ θ(y − x) + θ(ẏ − ẋ) + θ̇(y − x) − 1θ (θ(κ − θ) − θ̇)ẋ
Some useful observation regarding the considered parameters are made through
the following remarks.
νρ
(2.2.22) θ= ,
ν+e
36
2.2. Article en anglais
(2.2.23) τ (t) ∼ 1
ν(t)
(l + κe) and η(t) ∼ κ (as t → +∞).
Indeed, by Remark 2.2.2, we know that θ is well-defined and positive on [0, ∞) under
condition (2.2.11). Moreover, from ν ∈ C 2 , ν > 0 and θ = κν−
ν+e
ν̇
(hence θ = κ − ν̇+κe
ν+e
),
we can see that θ ∈ C 1 ([0, ∞)) and we readily get
Consequently, by these observations, we deduce that the functions τ (.) and η(.) (in
light of their definitions) belong to C 1 ([0, ∞)) and we obtain
τ= 1
κν−ν̇
(ν̇ + κe) (κν−2
ν+e
ν̇)
+ ν̈ and η =κ− 1
(κν−ν̇)
ν̇(ν̇+κe)
ν+e
− ν̈ .
So, under the the additional condition (2.2.13), we obviously obtain (2.2.23).
(j2) Let us recall that λ(.) (defined in (2.2.12b)) is of the form λ = λθc (ν + e)2 (for
some λc > 0). So it is easily seen under condition (2.2.11) that λ(.) is differentiable
on [0, ∞). Moreover it can be checked that condition (2.2.13) ensures that λ satisfies
the following properties :
(2.2.25a) λc
λ(t) ∼ κ
ν 2 (t) (as t → ∞);
(2.2.25b) |λ̇(t)| ≤ k2 ν(t), for t ≥ 0 (k2 being some positive constant);
(2.2.25c) ∃t0 > 0 s.t. λ is non-decreasing on [t0 , ∞).
37
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
(ν+e) 2
λ̇(t) = λc (κν− ν̇)2
(3ν̇(κν − ν̇) − (ν + e)(κν̇ − ν̈))
(ν+e)2
= λc (κν− ν̇)2
(ν(2κν̇ + ν̈) − 3ν̇ 2 − e(κν̇ − ν̈)) .
Then, by ν̇(t) → l and ν̈(t) → 0 (as t → ∞), we can see that λ̇ν → 2lλ κ
c
is bounded,
which ensures (2.2.25b) and (2.2.25c) (as λ̇(t) is positive for t large enough).
(j3) For ϵ > 0, under the supplementary conditions (2.2.14)-(2.2.15), the function
η(.) is continuously differentiable on [0, ∞) and we show that (e + ν)η̇ is bounded on
[0, ∞).Indeed, by an easy computation, for ν ∈ C 3 ([0, ∞)) we obtain η̇ = θ12 (θ̇2 − θθ̈),
2 +κeν̇
together with θ̇ = ν̇(ν+e) ν̈
2 − (ν+e) (in light of (2.2.24)), which gives us
2ν̇ (ν̇+κe) (3)
θ̈ = 2ν̈(ν+e)
ν̇+κeν̈
2 − 2 (ν+e)3
ν
− (ν+e) ν̇ ν̈
+ (ν+e) 2,
where ν (3) stands for the third derivative of ν. Clearly, by these formulations of η̇,
θ̇ and θ̈, along with the boundedness of ν̇, ν̈ and ν (3) (under condition (2.2.13) and
(2.2.15)), while recalling that θ is positive and non-decreasing [0, ∞) (from Remark
2.2.2), we infer that
(ν + e)|η̇| ≤ θ21(0) (ν + e)|θ̇2 | + θ(0)
1
(ν + e)|θ̈|) ≤ k1 , for some constant k1 ≥ 0.
(2.2.26) λ ∈ C 0 ([0, ∞)) and, for t ≥ 0, λ(t) ∈ [λm , ∞) (for some constant λm > 0) ;
(2.2.27) θ ∈ C 0 ([0, ∞)) and, for t ≥ 0, θ(t) ∈ [0, θM ] (for some constant θM > 0).
Then for any Cauchy data (x0 , y0 ) ∈ H2 , there exists a unique global classical
solution (x, y) to (2.2.5) verifying the initial condition (x(0), y(0)) = (x0 , y0 ).
38
2.2. Article en anglais
where U = (x, y), while Φ̄ : H2 → H2 and E(t, .) : H2 → H2 are defined for any
t ≥ 0 and for any (u, v) ∈ H2 by
!T !T
Φ(u) ϕ1 (t, u, v)
(2.2.29) Φ̄(u, v) = , E(t, (u, v)) = ,
0 ϕ2 (t, u, v)
along with ϕ1 (t, u, v) = ϵAλ(t) u + θ(t)(v − u) and ϕ2 (t, u, v) = κ(v − u). Note that
(2.2.28) is governed by the sum of the convex subdifferential operator ∂ Φ̄ = ∇Φ̄ and
the operator E : [0, ∞) × H2 → H2 . In view of applying [31, Proposition 3.12] (see
also [60, Proposition 6.2.1]) we prove that E satisfies the following properties (a)
and (b) :
(a) E(t, .) is globally Lipschitz continuous on H2 . Clearly, given t ≥ 0 and
(ui , vi ) ∈ H2 (for i = 1, 2), and invoking the boundedness of θ in (2.2.27) we readily
obtain
∥ϕ1 (t, u1 , v1 ) − ϕ1 (t, u2 , v2 )∥ ≤ ϵ∥(Aλ(t) u1 − Aλ(t) u2 )∥ + θM ∥(v1 − u1 ) − (v2 − u2 )∥.
Moreover, recalling that Aλ is λ−1 -Lipschitz continuous and assuming that
λ(t) ≥ λm > 0 (for some constant λm ), we also have
∥(Aλ(t) u1 − Aλ(t) u2 )∥ ≤ λ1m ∥u1 − u2 ∥.
Then, by the previous two inequalities we get
ϵ
∥ϕ1 (t, u1 , v1 ) − ϕ1 (t, u2 , v2 )∥ ≤ λm + θM (∥v1 − v2 ∥ + ∥u1 − u2 ∥) ;
while an easy computation gives us
∥ϕ2 (t, u1 , v1 ) − ϕ2 (t, u2 , v2 )∥ ≤ κ (∥v1 − v2 ∥ + ∥u1 − u2 ∥) .
It follows that E(t, .) is globally Lipschitz continuous on H2 .
(b) For any T ∈ (0, ∞), (u, v) ∈ H2 , E(., u, v) ∈ L2 (0, T ; H2 ). Taking z ∈
(ϵA)−1 (0) (under condition (H3)), by Lemma A.1 and recalling that λ(t) ≥ λm > 0,
we obtain
∥ϵAλ(t1 ) u − ϵAλ(t2 ) u∥ ≤ 3 |λ(t1 )−λ(t
λ2m
2 )|
∥u − z∥.
Then, the continuity of λ on [0, ∞) yields that the mapping t 7→ ϵAλ(t) u is also
continuous on [0, ∞). So, in light of the definition of ϕ1 and ϕ2 , we infer that
E(., u, v) is continuous on [0, ∞) (as are ϕ1 and ϕ2 ). It follows immediately the
desired result of item (b).
39
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
1 s(e − s)
(2.2.31) Gs,q := ||s(q − x) + ν(y − x)||2 + ∥x − q∥2 .
2 2
(e+ν)2
(2.2.32) Ġs,q + s(e + ν)⟨ψ, x − q⟩ + ρ
⟨ψ, ẋ⟩ = −ν 2 T˜s ,
Proof. Observe that (2.2.31) can be written as Gs,q = seb + sνa + ν 2 c, where
b(.) := 12 ∥x − q∥2 , a(.) := ⟨q − x, y − x⟩ and c(.) := 12 ∥y − x∥2 . Consequently, the
40
2.2. Article en anglais
The rest of the proof can be divided into the following steps (A1)-(A3) :
(A1) In order to estimate the time derivative Ġs,q , we evaluate separately each
of the terms occurring on the right side of (2.2.34). Let us prove the following basic
results on a(.) and c(.) :
(2.2.36) ν̇
Ġs,q = − (ν 2 + sν) ⟨ẋ, u⟩ − s(ν + e)W − ν 2 κ − ν
∥u∥2 ,
41
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
In this section we state our main result regarding the Lyapunov-like function Es,q
introduced in (2.2.10).
42
2.2. Article en anglais
Lemma 2.2.2. Let (H1)-(H3) hold, and let (x, y) : [0, +∞[→ H2 be a classical
solution to (2.2.5)-(2.2.6), with positive constants {κ, e}, a function ν(.) verifying
(2.2.11), and a positive mapping λ(.). Then, for (s, q) ∈ [0, e] × S, on [0, ∞), we have
(2.2.37)
2
Ės,q + (s − ec )v Φ̃(x) + ϵsλv∥Aλ x∥2 + ϵ vρ ⟨Aλ x, ẋ⟩ ≤ −ν 2 T˜s .
2M
where ec = ρ(0)
, v = e + ν, ρ = κ − νν̇ , and T̃s is defined in (2.2.33).
Proof. Note that (2.2.5)-(2.2.6) enters the setting of (2.2.30) with ψ = ∇Φ(x)+ϵAλ x.
Take q ∈ S (hence ϵAλ (q) = 0 and ∇Φ(q) = 0). In light of Lemma 2.2.1, with this
particular expression of ψ, we obtain
2
Ġs,q + svW + vρ Z = −ν 2 T˜s ,
where W = ⟨∇Φ(x)+ϵAλ x, x−q⟩ and Z = ⟨∇Φ(x)+ϵAλ x, ẋ⟩. Let us estimate W and
Z. Using the convexity of Φ and the λ-co-coerciveness of Aλ , by Φ̃(x) = Φ(x) − Φ(q)
we get ⟨∇Φ(x), x − q⟩ ≥ Φ̃(x) and ⟨ϵAλ x, x − q⟩ ≥ ϵλ∥Aλ x∥ . It follows immediately
2
that W ≥ Φ̃(x) + ϵλ∥Aλ x∥2 . Moreover, noticing that dtd Φ̃(x) = ⟨∇Φ(x), ẋ⟩, we
2
simply have Z = dtd Φ̃(x) + ϵ⟨Aλ x, ẋ⟩. Setting µ = vρ (or equivalently µ = ν(ν+e) θ
,
as θ = ν+eνρ
(from (2.2.22))), by these two results in light of the previous estimate on
Ġs,q , we are led to
43
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
2M
where ec = ρ(0) , v = e + ν, ρ = κ − νν̇ , while Ts is defined, for some sc ∈ (ec , e) and
some δ > 0 (occurring in Remark 2.2.4) verifying ϵδ ∈ [0, 4), by
2
1 e−s
Ts = ρ y − x + 1− ẋ
(2.2.40) θ 2(e+ν)
1 s+3e
+ 4 − ϵδ + ϵδs (s
+ 4ρν (e − s) ν
− sc )(e − sc − s) ∥ẋ∥2 .
Proof. It can be noticed that (2.2.39) reduces to (2.2.37) when ϵ = 0. Now, we let
ϵ > 0 and we consider the quantity C(.) := sλv∥Aλ x∥2 + µ⟨Aλ x, ẋ⟩ that arises in the
left side of (2.2.37). To estimate C, we take s ∈ (0, e) and we set ks = 2sλv
µ
. So, by
∥Aλ x∥2 = ∥Aλ x + ks ẋ − ks ẋ∥2 we simply have
∥Aλ x∥2 = ∥Aλ x + ks ẋ∥2 − 2ks ⟨Aλ x, ẋ⟩ − ks2 ∥ẋ∥2 .
Hence, by µ = 2sλvks (from definition of ks ) along with the definition of C, we get
C = sλv ||Aλ x + ks ẋ||2 + (µ − 2sλvks ) ⟨Aλ x, ẋ⟩ − sλvks2 ∥ẋ∥2
= sλv ||Aλ x + ks ẋ||2 − sλvks2 ∥ẋ∥2 ,
or equivalently C = sλv ||Aλ x + ks ẋ||2 − ν 2 γ∥ẋ∥2 , where γ := ν −2 (sλvks2 ). This, in
light of (2.2.37), amounts to
Ės,q + [s − ec ] v Φ̃(x) + sλvϵ ||Aλ x + ks ẋ||2 ≤ −ν 2 (T˜s − ϵγ∥ẋ∥2 ).
Observe from Remark 2.2.4 that λ = νsc (e−s µv
c )δ
, for some sc ∈ (ec , e) and some δ > 0
such that ϵδ ∈ [0, 4). In addition, by the definition of γ we get γ = ν −2 (sλvks2 ) =
µ2
ν −2 4sλv (since ks = 2sλv µ
), hence, from λ = νsc (e−s µv
c )δ
, we get
44
2.2. Article en anglais
2
µ
γ = ν −2 4sv × νsc (e−s
µv
c )δ
= sc (e−s
4sρν
c )δ
.
Therefore, setting u = y − x and using the definition of T˜s in Lemma 2.2.1, we have
2
T˜s − ϵγ∥ẋ∥2 − ρ u + 1θ ẋ − e−s 2ρν
ẋ
= e−s s+3e sc δ
+ 4 ∥ẋ∥2 − ϵ 4sρν (e − sc )∥ẋ∥2
4ρν ν
sc (e−sc )
= e−s s+3e δ
2
+ 4 − ϵδ ∥ ẋ∥ + ϵ(e − s) − ϵ ∥ẋ∥2
4ρν ν 4ρν
s
= e−s s+3e δ ϵ
2
4ρν ν
+ 4 − ϵδ ∥ ẋ∥ + 4ρν s
(s − sc )(e − sc − s)∥ẋ∥2 .
It follows from our previous estimate on Ės,q that
Ės,q + [s − ec ] v Φ̃(x) + sλvϵ ||Aλ x + ks ẋ||2 ≤ −ν 2 Ts ,
where Ts = T˜s + ( sϵ )(s − sc )(e − sc − s) 4ρν δ
∥ẋ∥2 . This leads to (2.2.39). The
remainder of the proof is obvious. ■
45
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Proof. It can be checked in this setting that conditions (2.2.11) holds whenever
ν0 > M κ−1 . Conditions (2.2.13)-(2.2.15) are also obviously satisfied, while (2.2.12a)
reduces to e > κν2M ν0
0 −M
. Theorem 2.2.2 is then directly deduced from Theorem 2.2.1.
■
There we specialize our convergence results to the two systems (2.2.7) and (2.2.8)
separately.
46
2.2. Article en anglais
47
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
where the coefficients γ, β : [t0 , +∞[→ R+ (for some t0 > 0) take account of the
viscous and Hessian-driven damping, respectively, and where b : R+ → R+ is a
time scale parameter. Note that (2.2.64) reduces to (2.2.2) when β(t) = β (for
some constant β > 0) and b(t) = 1. Contrary to Theorem 2.2.1, the studies in
[17, 18, 103] do not prove the convergence of the trajectories, and no estimates
are given regarding the velocity. Only convergence rates of the gradient and the
function values are estimated, depending on the involved parameters. It turns out
for bounded temporal scaling that the optimal estimates reached by the authors are
R +∞ 2
t0
t ∥∇Φ(x(t))∥2 dt < ∞ (fast decay of the gradient) and Φ(x(t))−inf H Φ = O(t−2 )
(for the function values), which are obtained as a particular case of Theorem 2.2.1,
with an even better rate Φ(x(t)) − inf H Φ = o(t−2 ). These optimal properties were
found out in [103, Theorem 5 and Corollary 4.2], in Euclidean spaces, for (2.2.64)
when γ(t) = 3t−1 , β(t) = β (for some β > 0) and b(t) = 1 + 3βt−1 , relative to
smooth C 2 convex and Lipschitz continuous functions Φ. The same properties were
stated in [18, Theorem 2.3], in Hilbert spaces, regarding (2.2.64) when γ(t) = αt−1
48
2.2. Article en anglais
(for some α ≥ 3), β(t) = β (with β > 0) and b(t) = 1 + βt−1 , relative to smooth
C 2 convex functions Φ with locally Lipschitz continuous gradient. Other significant
accelerations are proposed in [18, 17], based upon reparametrization in time of
non-autonomous dissipative dynamical systems. This comes into play when using
unbounded temporal scaling b(.). An major concern with this latter approach is to
lead to discrete counterparts of proximal-types with unbounded proximal indexes.
Indeed the resulting algorithms appear to be somewhat difficult to adapt to the
context of structured minimization problems.
This first part of the proof can be divided into the following steps (B1)-(B3) :
(B1) Let us prove (2.2.41)-(2.2.42) and other useful estimates. As an immediate
consequence of Proposition 2.2.3 we establish the following results :
Esc ,q (0)κ
(2.2.65a) Φ(x(t)) − inf H Φ ≤ v 2 (t)
,
(2.2.65b) sc (e−sc )
2
∥x − q∥2 ≤ Esc ,q (0),
R +∞
(2.2.65c) 0
v(t)(Φ(x(t)) − inf H Φ)dt ≤ Esscc−e
,q (0)
c
,
R +∞ 2 Esc ,q (0)
(2.2.65d) 0
ϵλ(t)v(t) Aλ(t) x(t) + ksc (t)ẋ(t) dt < sc
,
R +∞ 4κEsc ,q (0)
(2.2.65e) 0
ν(t)∥ẋ(t)∥2 dt ≤ (4−ϵδ)(e−sc )
,
R +∞ Esc ,q (0)κ2
(2.2.65f) 0
ν 2 (t)∥θ(t)u(t) + 1 − e−sc
2v(t)
ẋ(t)∥2 dt ≤ ρ(0)
,
R +∞
2κEsc ,q (0)
(2.2.65g) 0
ν(t)∥u(t)∥2 dt ≤ θ2 (0)
4
(4−δ)(e−sc )
+ κ
ρ(0)
.
Note that estimates (2.2.41)-(2.2.42) follow directly from (2.2.65c), (2.2.65e) and
(2.2.65g).
Let (s, q) ∈ [0, e] × S. By the definition of Es,q in (2.2.10), we have µΦ̃(x) ≤ Es,q ,
2
where µ := vρ and Φ̃ := Φ − Φ(q), as well as sc (e−s) 2
∥x − q∥2 ≤ Es,q . Moreover,
49
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
with ksc = 2scvλρ and Tsc = ρ∥u + θ−1 g ẋ∥2 + 4ρϵ e−sc
∥ẋ∥2 ,
sc +3e
ν ν
+ 4 − ϵδ
where g(t) = 1 − 2v(t)
e−sc
. So, recalling that sc − ec > 0 and that Φ̃ and Tsc are non-
negative mappings, by passing to the limit as t → +∞ in the previous inequality
R +∞ R +∞
yields 0 v(r)Φ̃(x(r)) dr < ∞ and 0 ϵλ(r)v(r)∥Aλ(r) x(r) + ksc (r)ẋ(r)∥2 dr < ∞,
namely (2.2.65c) and (2.2.65d). It is also immediate from (2.2.66) that
R +∞
(2.2.67) 0
ν 2 (r)Tsc (r) dr ≤ Esc ,q (0).
On the one hand, by definition of Tsc and by ρ ≤ κ (from Remark 2.2.2), we have
ν 2 Tsc ≥ (e−sc4κ
)(4−ϵδ)
ν∥ẋ∥2 ,
which, in light of (2.2.67) and recalling that sc ∈ (ec , e) and that ϵδ ∈ [0, 4), entails
R +∞
0
ν(r)∥ẋ(r)∥2 dr ≤ (e−sc4κ E (0), that is (2.2.65e). On the other hand, again
)(4−ϵδ) sc ,q
using the above definition of Tsc while reminding that ρ(0) ≤ ρ and θ ≤ κ (from
Remark 2.2.2), we readily get
ν 2 Tsc ≥ ρ(0)
κ2
ν 2 ∥θu + g ẋ∥2 .
R +∞ 2
This, by (2.2.67), gives us 0 ν 2 (t)∥θ(t)u(t) + g(t)ẋ(t)∥2 dt ≤ κ Eρ(0) sc ,q (0)
, that is
(2.2.65f). Let us prove (2.2.65g). It is not difficult to check that 0 ≤ g ≤ 1 as
e − sc > 0, while we know that θ is positive and that θ ≥ θ(0) (as θ is non-decreasing).
So, by convexity of the square norm and by ν∥u∥2 = 4ν ∥ 1 (θu + g ẋ) − 12 g ẋ∥2 we
θ2 2
obtain
ν∥u∥2 ≤ 2ν
θ2
(∥θu + g ẋ∥2 + g 2 ∥ẋ∥2 ) ≤ θ22(0) (ν∥θ + g ẋ∥2 + ν∥ẋ∥2 ).
Combining this last inequality with (2.2.65e) and (2.2.65f) entails (2.2.65g).
50
2.2. Article en anglais
51
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
(B3) Let us prove (2.2.44)-(2.2.45). In this regard, we prove the following results :
v 2 (t)
(2.2.72) Ė0,q (t) ≤ ec v(t)Φ̃(x(t)) − ρ(t)
⟨Aλ(t) x(t), ẋ(t)⟩,
where Φ̃ = Φ − Φ(q). Moreover, using the Holder inequality and recalling that
ρ(t) ≥ ρ(0) (for t ≥ 0), we get
R +∞ v2 (t)
0 ρ(t)
⟨Aλ(t) x(t), ẋ(t)⟩ dt
R 12 R 21
1 +∞ 3 2 +∞ 2
≤ ρ(0) 0 v (t)∥Aλ(t) x(t)∥ dt · 0 v(t)∥ẋ(t)∥ dt ,
R +∞ R +∞
as 0 v(t)∥ẋ(t)∥2 dt < ∞ (by (2.2.65e)) and 0 v 3 (t)∥Aλ(t) x(t)∥2 dt < ∞ (by
(2.2.68a) and (2.2.71a)). This trivially yields (2.2.71b).
R +∞
We also know that 0 v(t)Φ̃(x(t))dt < ∞ (from (2.2.65c)). Then by these last two
results, in light of (2.2.72), we classically deduce that lim E0,q (t) exists. It can also
t→+∞
be checked that E0,q verifies
1 1 v 2 (t)
E0,q (t) = ν(t)∥u(t)∥2 + Φ̃(x(t)),
ν(t) 2 ν(t)ρ(t)
2
Furthermore, as t → ∞, we simply have ν(t)ρ(t) v (t)
∼ ( κ1 )v(t), because ν(t) ∼ v(t) and
R +∞
ρ(t) → κ (in light of Remark 2.2.2 -(i2)) . Therefore, by 0 v(t)Φ̃(x(t)) dt < ∞ (from
R +∞ R +∞ 1
(2.2.65c)) and 0 ν(t)∥u(t)∥2 dt < +∞ (from (2.2.65g)), we get 0 ν(t) E0,q (t) dt <
R +∞ 1
∞. Whence, as lim E0,q (t) exists and 0 ν(t) dt = ∞ (from Remark 2.2.2), we
t→+∞
deduce that lim E0,q (t) = 0. This in view of the definition of E0,q entails (2.2.71c)
t→+∞
and (2.2.71d). It remains to prove (2.2.71e). From (2.2.5), we simply have ∥ẋ +
52
2.2. Article en anglais
∇Φ(x) + ϵAλ x∥ = ∥θu∥. It follows from θ ∈ (0, κ) (see Remark 2.2.2) that
ν∥u∥ ≥ κν ∥θu∥ = κν ∥ẋ + ∇Φ(x) + ϵAλ x∥.
Hence, (2.2.71e) is straightforwardly deduced from (2.2.71d).
In this second part of the proof we assume that ν(.) satisfies the additional
conditions (2.2.13)-(2.2.15) and we divide the rest of the proof into the following
steps (C1)-(C3) :
(C1) (Estimate (2.2.46)). At once we prove that
1 d
(ν 2 ∥∆h x∥2 ) − M ν∥∆h x∥2 + ν 2 ⟨∆h θ(yh − xh ), ∆h x⟩
(2.2.75) 2 dt
+ν 2 θ⟨∆h y − ∆h x, ∆h x⟩ + ν 2 ⟨∆h Ψ(., x), ∆h x⟩ ≤ 0.
Moreover, by Ψ(., x(.)) = ∇Φ + ϵAλ (x) and thanks to the monotonicity of ∇Φ, we
get
⟨∆h Ψ(., x), ∆h x⟩ ≥ ϵ⟨Aλh (xh ) − Aλ (x), ∆h x⟩,
53
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
1 d
(ν 2 ∥∆h x∥2 ) − M ν∥∆h x∥2 + ν 2 ⟨∆h θ(yh − xh ), ∆h x⟩
(2.2.76) 2 dt
+ν 2 θ⟨∆h y − ∆h x, ∆h x⟩ − ν 2 λ3ϵ2 ∥x − z∥ × |∆h λ| × ∥∆h x∥ ≤ 0.
54
2.2. Article en anglais
ẋ, θ̇ and ẏ, respectively, (as h → 0). It is also readily checked that ∥ ∆hh x ∥ converges
uniformly on [s, t] to ∥ẋ∥ (as ∆hh x → ẋ on [s, t]), while noticing that λ is C 2 on
[0, ∞), which guarantees that ∆hh λ and | ∆hh λ | converge uniformly on [s, t] to λ̇ and |λ̇|,
respectively (as h → 0). Hence, passing to the limit in (2.2.77), as h → 0, amounts to
1
Rt
2
∥ν(t)ẋ(t)∥2 − 21 ∥ν(s)ẋ(s)∥2 − M s ν(r)∥ẋ(r)∥2 dr
Rt Rt
(2.2.78) + s ν 2 (r)θ̇(r)⟨y(r) − x(r), ẋ(r)⟩dr + s ν 2 θ(r)⟨ẏ(r) − ẋ(r), ẋ(r)⟩dr
Rt 2
−3ϵ s λν 2 (r)
(r)
|λ̇(r)| × ∥x(r) − z∥ × ∥ẋ(r)∥ dr ≤ 0.
1
Rt
2
∥ν(t)ẋ(t)∥2 − 21 ∥ν(s)ẋ(s)∥2 − M s ν(r)∥ẋ(r)∥2 dr
Rt Rt
(2.2.79) + s τ (r)ν 2 (r)∥ẋ(r)∥2 dr + s ην 2 ⟨Ψ(r, x(r)), ẋ(r)⟩dr
Rt 2
−3ϵ s λν 2 (r)
(r)
|λ̇(r)| × ∥x(r) − z∥ × ∥ẋ(r)∥ dr ≤ 0.
It is clear from (2.2.79) that Γ(t) ≤ Γ(s) for t0 ≤ s < t, and so Γ(.) is non-increasing
on [t0 , ∞). In order to conclude that Γ is convergent we prove the convergence (as
t → +∞) of each of the four integrals involved in (2.2.80) through the following
items (r1)-(r4) :
R +∞
(r1) : From (2.2.65e), we directly obtain t0 ν(r)∥ẋ(r)∥2 dr < ∞.
(r2) : Since τ (t) ∼ (l + κe) ν(t)
1
as t → ∞ (from Remark 2.2.3) we immediately
55
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Let us evaluate separately the two quantities arising on the right-side of the previous
equality. On the one hand, integrating by parts the first integral gives us
(2.2.82)
Rt 2 d
Rt d
t0
(ην )(r) dr
Φ̃(x) (r)dr = η(t)ν 2 (t)Φ̃(x(t)) − t0 dr (ην 2 )(r)Φ̃(x(r))dr.
Note that, as t → +∞, we have η(t) ∼ κ (from Remark 2.2.3) and ν 2 (t)Φ̃(x(t)) → 0,
and so η(t)ν 2 (t)Φ̃(x(t)) → 0. In addition, by a simple computation we have dr d
(ην 2 ) =
η̇ν 2 + 2ην ν̇, hence, by boundedness of ν̇, η and ν η̇ (from Remark 2.2.3), we infer
that there exists a positive constant K2 verifying (for r ≥ 0)
d
| dr (ην 2 )(r)Φ̃(x(r))| ≤ K2 ν(r)Φ̃(x(r)).
R +∞
So, in light of 0 ν(r)Φ̃(x(r))dr < ∞ (from (2.2.65c)), we deduce the convergence
Rt d
of the term t0 dr (ην 2 )(r)Φ̃(x(r))dr (as t → ∞). These last two results in light of
(2.2.82) entail the convergence (as t → ∞) of first integral on the right side of (2.2.81).
R∞
On the other hand, by η(t) ∼ κ (as t → ∞) and by t0 ϵν 2 (r)|⟨Aλ x(r), ẋ(r)⟩|dr < ∞
(according to (2.2.71b)), we obviously get the convergence (as t → ∞) of the second
term on the right side of (2.2.81). Therefore, in light of (2.2.81), we conclude that
Rt
the term t0 (ην 2 )(r)⟨Ψ(r, x(r)), ẋ(r)⟩dr is convergent (as t → ∞).
(r4) : Remark 2.2.3 tells us that λ̇ satisfies |λ̇| ≤ k2 ν (for some constant k2 )
3 3
and (as t → ∞) that λ(t) ∼ λκc ν 2 (t) (or equivalently λν 2 (t) ∼ ( λκc )2 ν(t)
1
). So, λν 2 |λ̇| is
(t)
bounded, while we know that x(.) is bounded (from (2.2.65b)), hence there exists
some constant Cz ≥ 0 such that
(2.2.83)
2
ϵ λν 2 |λ̇| × ∥x − z∥ × ∥ẋ∥ ≤ Cz ϵν −1 ∥ẋ∥.
56
2.2. Article en anglais
Rt R 1/2 R 1/2
−1 t 1 t 2
t0
ϵν (r)∥ ẋ(r)∥dr ≤ t ν 3 (r)
dr · t0
ν(r)∥ ẋ(r)∥ dr .
R +∞ ϵ 0 Rt
This, according to 0 ν 3 (r) dr < ∞ (by hypothesis) and t0 ν(r)∥ẋ(r)∥2 dr < ∞
R +∞
(from (r1)) yields t0 ν −1 (r)∥ẋ(r)∥ dr < ∞. As a consequence, by (2.2.83), we get
R +∞ ν 2 (r)
0
ϵ λ2 (r) |λ̇(r)| × ∥x(r) − z∥ × ∥ẋ(r)∥ dr < ∞.
Finally, we have shown that all the integrals involved in (2.2.80) are convergent.
So, recalling that Γ is non-increasing on [t0 , ∞) yields the boundedness of Γ. Hence,
it is deduced that lim Γ(t) exists, which obviously implies that ν 2 (t)∥ẋ(t)∥2 → ℓ
t→+∞
(for some constant ℓ ≥ 0) as t → +∞. Let us prove by contradiction that ℓ = 0.
Suppose that ℓ > 0. This clearly implies that ν(t)∥ẋ(t)∥2 ∼ ν(t)
ℓ
(as t → +∞), which,
R +∞ R +∞ 1
by 0 ν(t)∥ẋ(t)∥ dt < ∞ (according to (2.2.65e)) yields 0 ν(t) dt < ∞. This
2
Proof. Let q ∈ (ϵA)−1 (0). Given s ≥ 0 and t ≥ 0, and using Lemma A.1 with
γ = λ(t), δ = λ(s), x = x(t) and y = x(s), we get
∥ϵλ(t)Aλ(t) x(t) − ϵλ(s)Aλ(s) x(s)∥ ≤ 2ϵ∥x(t) − x(s)∥ + 2ϵ∥x(t) − q∥ |λ(t)−λ(s)|
λ(t)
.
Dividing by t − s with t > s and letting s tends to t, we obtain
d |λ̇(t)|
(2.2.85) (ϵλ(t)Aλ(t) x(t)) ≤ 2ϵ∥ẋ(t)∥ + 2ϵ∥x(t) − q∥ ,
dt λ(t)
readily checked that there exists some constant c1 ≥ 0 such that |λλ̇| ≤ cν1 . Moreover,
from (2.2.73), we can see that there exists c2 ≥ 0 such that ∥ẋ∥ ≤ cν2 . So, combining
(2.2.85) with these last two estimates, we obtain, for some constant c ≥ 0,
(2.2.86) d
dt
(ϵλ(t)Aλ(t) x(t)) ≤ ϵc
ν(t)
for a.e. t ≥ 0.
Note that, setting ω(t) := ∥ϵλ(t)Aλ(t) (x(t))∥2 , we classically have (for a.e t ≥ 0)
(2.2.87) d
dt
ω(t) ≤2 d
dt
(ϵλ(t)Aλ(t) x(t)) · ∥ϵλ(t)Aλ(t) x(t)∥.
57
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
58
2.2. Article en anglais
where Θns is a convex and proper lower semi-continuous function and Θsm is a convex
differentiable function. Given (xk , yk ) ∈ H2 and based upon an approximate finite
difference of (2.2.7), we seek for (xk+1 , yk+1 ) ∈ H2 verifying the numerical scheme
(
1
h
(xk+1 − xk ) + ∂Θns (xk+1 ) + ∇Θsm (xk ) + θk (yk − xk ) ∋ 0,
1
h
(yk+1 − yk ) + κ(yk − xk ) = 0,
where ∂Θns denotes the Fenchel sub-differential of the (possibly non-smooth)
convex function Θns . This can be simply rewritten as
( ∂(Θ )
xk+1 = Jh ns (xk − h∇(Θsm )(xk ) − hθk (yk − xk ))
yk+1 = yk − hκ(yk − xk ),
∂(Θ )
where Jh ns = (I + h∂(Θns ))−1 is the resolvent operator of ∂(Θns ) with index h.
Consequently, in light of Theorem 2.2.3, a good candidate for approximating (2.2.89)
59
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
is probably given by
Note that when hκ = 1, by (2.2.90c) we have yk+1 = xk (for k ≥ 0), hence, for k ≥ 1,
(2.2.90) reduces to
This is nothing but the form of the well-known "heavy ball with friction" method
(see, e.g., [86]. Other variants of (2.2.90) can be obtained by replacing xk by zk in the
gradient of Θsm , which leads to some Nesterov-type accelerated forward-backward
algorithm (see [9, 14, 82, 83, 84]) or by swapping xk and zk in the operator Jh∂(Θns )
(see [74]).
1
(xk+1 − xk ) + Aλk xk+1 + θk (yk − xk ) = 0,
performing h
1
(y − y ) + κ(yk − xk ) = 0,
h k+1 ( k
Aλ
xk+1 = Jh k (xk − hθk (yk − xk )),
which is equivalent to
yk+1 = yk − hκ(yk − xk ),
Aλ
where Jh k = (I + hAλk )−1 is the resolvent operator of the maximally monotone
operator Aλk with index h. Set zk = (1 + hθk )xk − hθk yk . Then we alternatively have
60
2.2. Article en anglais
Moreover, using Proposition A.1 (f), we have (Aλ )µ = Aλ+µ . Then by (2.2.93b) we
simply deduce that
Aλ
xk+1 = Jh k (zk ) = λkλ+h
k
zk + λkh+h JλAk +h zk .
Furthermore, by (2.2.93c) we readily have xk = κh 1
yk+1 − 1−κh
κh
yk , which by (2.2.93a)
amounts to zk = yk + κh (yk+1 − yk ). Finally, using the above expressions of xk+1
1+hθk
1+hθk−1
(2.2.94a) zk−1 = yk−1 + κh
(yk − yk−1 ),
λk−1
(2.2.94b) xk = z
λk−1 +h k−1
+ h
JA (z ),
λk−1 +h λk−1 +h k−1
2.2.7 Appendix
[Link] The Yosida approximation
The Yosida approximation enjoys numerous nice properties which often facilitating
and simplifying calculations. Some of them are recalled below (see [31, 30]) :
61
Chapitre 2 – Un modèle général du premier ordre pour des dynamiques continues de type Newton
gouvernées par des opérateurs maximaux monotones
Lemma A.1. Let γ, δ > 0 and x, y ∈ H. Then for z ∈ A−1 ({0}), we have
Proof. The proof of (2.2.95) can be found in [13]. Let us prove (2.2.96). To get this
we simply have
Aγ x − Aδ y = 1δ (δAγ x − δAδ y)
= 1δ ((δ − γ)Aγ x + (γAγ x − δAδ y) ,
hence
∥Aγ x − Aδ y∥ ≤ 1δ (|δ − γ| × ∥Aγ x∥ + ∥γAγ x − δAδ y∥) .
Consequently, by ∥Aγ x∥ ≤ γ1 ∥x − z∥ and using (2.2.95), we obtain
1 |δ−γ| |γ−δ|
∥Aγ x − Aδ y∥ ≤ δ γ
× ∥x − z∥ + 2∥x − y∥ + 2 γ ∥x − z∥
|δ−γ|
= 1δ 3 γ × ∥x − z∥ + 2∥x − y∥ ,
that is the desired inequality. ■
Lemma B.2 ([13] Lemma A.5). Let ω, η : [0, +∞[→ [0, +∞[ be absolutely continuous
R +∞
functions such that η ∈ / L1 (0, +∞) and which satisfy 0 ω(t)η(t)dt < ∞, along
with |ω̇(t)| ≤ η(t) for almost every t > 0. Then lim ω(t) = 0.
t→+∞
Acknowledgements
The authors would like to thank the two anonymous referees for their careful
readings of the manuscript and their insightful comments and observations.
62
Chapitre 3
3.1 Introduction
Dans ce chapitre, H désigne un espace de Hilbert réel muni d’un produit scalaire
noté ⟨., .⟩ et de la norme induite notée ∥ . ∥. Nous nous intéressons à des méthodes du
premier ordre pour la résolution de problèmes de minimisation structurés non lisses.
Ce type d’algorithme a gagné en popularité, en raison de ses caractéristiques remar-
quables qui en font une alternative intéressante aux méthodes de points intérieurs,
coûteuses en calcul. Le contenu de ce chapitre est basé sur l’article [72].
63
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
RIPGA
▶ Initialisation : Soient {x0 , y0 } ⊂ H, (νn ) ⊂]0, +∞[ et e > 0.
▶ Étape principale : Pour n ≥ 1 et {yn−1 , yn } donnés, on effectue
νn + (1 − κ)e
(3.1.4) αn = κ −1
.
νn+1 + e
64
3.1. Introduction
Il sera démontré (voir Section 3.2.2) que ce schéma peut être vu comme une
variante discrète d’un système dynamique du premier ordre récemment étudié.
Il convient de noter qu’un algorithme inertiel de type Forward-Backward relaxé
semblable à (3.1.3) a été récemment étudié par Attouch-Cabot [8], en utilisant
toutefois des paramètres variables (κn ) et (µn ) au lieu des valeurs constantes κ et µ.
De plus, ce dernier incorpore un terme de relaxation de la forme (1 − κn )zn−1 à la
place de (1 − κ)yn dans l’algorithme proposé (3.1.3)-(3.1.4). En outre, le paramètre
d’extrapolation αn de [8] est compris entre 0 et 1, tandis que pour la méthode proposée
(3.1.3)-(3.1.4), le terme αn peut être supérieur à 1 pour κ ∈]0, 1[ (car αn → κ−1 , dès
lors que νn → +∞ quand n → +∞). Une approche similaire combinant relaxation et
terme inertiel a aussi été étudiée par Iutzeler-Hendrickx [62] concernant les opérateurs
moyennés (averaged).
Rappelons que (3.1.5) est l’un des premiers algorithmes célèbres permettant de
résoudre (3.1.1)-(3.1.2). Ce dernier génère des suites (faiblement) convergentes (yn )
qui vérifient le taux de convergence Θ(yn ) − minH Θ = O(n−1 ) pour la minimisation
des valeurs de la fonction objectif Θ := f + g (voir chapitre 1, Section 1.2.3). La
méthode FB (3.1.5) a par la suite été améliorée via, notamment, l’algorithme Fast
Iterative Soft Thresholding Algorithm (FISTA) proposé par Beck-Teboulle [24], sur la
base des idées de Nesterov [81] et de Güler [57]. Il a été démontré que FISTA génère
des itérés (yn ) qui garantissent le taux de convergence Θ(yn ) − minH Θ = O(n−2 ).
Cependant la convergence des itérés n’a pas été établie.
65
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
n−1
zn−1 = yn + n+α−1 (yn − yn−1 ),
(3.1.7)
yn+1 = proxµg (zn−1 − µ∇f (zn−1 )),
pour une certaine constante α > 0. Rappelons (voir chapitre 1, Section 1.2.4),
sous la condition (3.1.6) et pour α > 3, que l’algorithme AFB génère des suites
(yn ) faiblement convergentes vérifiant le taux Θ(yn ) − minH = o(n−2 ), au lieu des
taux O(n−1 ) et O(n−2 ) obtenu respectivement pour (3.1.5) et FISTA. Des liens
intéressants entre AFB et les systèmes dynamiques continus du second ordre ont
été établis (voir, par exemple, May [77], Attouch-Chbani-Peypouquet-Redont[16]).
Ces liens se révèlent utiles pour comprendre le phénomène d’accélération résultant
de la présence du terme inertiel dans (3.1.7). En particulier, il a été prouvé que
AFB provient d’une discrétisation du modèle continu du second ordre suivant, qui
fait intervenir un amortissement linéaire isotrope et un paramètre « visqueux »,
c’est-à-dire qui tend lentement vers 0 (voir [16])
Les schémas de type inertiel ont été considérablement développés ces dix dernières
années dans le cadre de problèmes d’optimisation structurés : par exemple, les
algorithmes pour la minimisation convexe [9], ceux intégrant des procédures de
recherche linéaire (Cruz-Nghia [47], Nesterov [82], Scheinberg-Goldfarb-Bai [101]),
mais aussi ceux pour la résolution d’inclusions monotones (Moudafi-Oliny [78],
Lorentz-Pock [70]).
66
3.1. Introduction
où κ > 0 et où θ est défini, pour e > 0 et pour une fonction ν différentiable strictement
positive, par
κν(t) − ν̇(t)
(3.1.12) θ(t) = ,
ν(t) + e
ν̇ étant la dérivée de ν.
Un premier point important établi dans [66] (voir également la Proposition 3.2.2)
est que (3.1.10) peut être étendu au cas non lisse de Θ via le système différentiel du
67
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
premier ordre
(
ẋ(t) + ∂Θ(x(t)) + θ(t)(y(t) − x(t)) ∋ 0,
(3.1.13)
ẏ(t) + κ(y(t) − x(t)) = 0.
Un deuxième point essentiel mentionné dans [66] est que (3.1.10) (avec un choix
approprié de ν) se comporte asymptotiquement comme un système sur-amorti de la
forme (3.1.9). Les auteurs ont montré, dans le cas particulier où ν(t) = t + ν0 (avec
ν0 > 0), que les fonctions a, b et θ définies respectivement par (3.1.11) et (3.1.12)
satisfont
1 + κe
(3.1.14) θ(t) → κ, a(t) ∼ et b(t) → κ (lorsque t → +∞).
t
68
3.1. Introduction
que l’algorithme (3.1.3)-(3.1.4) génère des suites (faiblement) convergentes (xn ) qui
vérifient un o(n−2 ) pour la minimisation des valeurs de la fonction. Notons que ces
propriétés sont bien connue pour AFB lorsque e > 2 (voir chapitre 1, Section 1.2.4).
De plus, nous étendons au cadre non lisse la propriété de convergence rapide
vers zéro des sous-gradients de la fonction objectif, établie jusqu’à présent pour les
potentiels lisses uniquement. Plus précisément, toujours pour des paramètres vérifiant
(3.1.15), nous prouvons l’existence de sous-gradients ξn∗ ∈ ∂Θ(xn ) qui satisfont
Comme souligné dans [103], l’estimation (3.1.17) est moins fine que (3.1.16) selon
laquelle on obtient
3
(3.1.18) min ∥ξk∗ ∥ = O n− 2 .
0≤k≤n
Nous montrons que ce résultat reste valable dans le cas particulier de AFB, avec une
condition plus restrictive que (3.1.6). Néanmoins, notre algorithme offre quelques
degrés de liberté supplémentaires grâce aux paramètres κ et νn qui peuvent être
utilisés pour influencer (accélérer) la convergence des itérés.
69
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
3.2 Préliminaires
70
3.2. Préliminaires
Proposition 3.2.2 ([66], Proposition 2.1). Soit κ ∈]0, +∞[. Supposons que Θ ∈
C 2 (H) et que θ :]0, +∞[→]0, +∞[ soit une fonction différentiable. Alors les proposi-
tions suivantes sont équivalentes :
(i1) x est une solution classique du système du second ordre (3.1.10) ;
(i2) (x, y) est une solution classique du système du premier ordre (3.1.13).
Les commentaires suivants sont destinés à souligner le lien entre le modèle continu
(3.1.13)-(3.1.12) et l’algorithme (3.1.3)-(3.1.4). Ce dernier provient en fait d’une
reformulation d’une variante discrète du modèle continu (3.1.13)-(3.1.12). En effet,
71
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
(3.2.4a) zn = xn + θn (xn − yn ),
(3.2.4b) xn+1 = proxµg (zn − µ∇f (zn )),
(3.2.4c) yn+1 = (1 − κ)yn + κxn ,
où κ ∈]0, +∞[ et où θn est défini, pour une certaine suite croissante strictement
positive (νn ), par
κνn+1 − ν̇n+1
(3.2.5) θn = .
νn+1 + e
(3.2.6a) zn = xn − θn (yn − xn ),
(3.2.6b) ẋn+1 + µ(∂g(xn+1 ) + ∇f (zn )) + θn (yn − xn ) ∋ 0,
(3.2.6c) ẏn+1 + κ(yn − xn ) = 0.
Ainsi, en remplaçant µ et κ par µ∆t et κ∆t respectivement dans (3.2.6) (pour une
certaine quantité positive ∆t), on observe que (3.2.4)-(3.2.5) peut être vu comme
une discrétisation par différences finies du modèle (3.1.13)-(3.1.12). Notons que ce
modèle discret fait intervenir le terme explicite ∇f (zn ) au lieu du terme ∇f (xn+1 ).
Nous montrons ensuite que (3.1.3)-(3.1.4) entre dans le cas du modèle (3.2.4)-(3.2.5).
κνn+1 −ν̇n+1
(3.2.7a) zn = xn − θn (yn − xn ), où θn = e+νn+1
,
(3.2.7b) xn+1 = Jµ∂g (zn − µ∇f (zn )),
(3.2.7c) yn+1 = (1 − κ)yn + κxn .
ẏn+1 = κ(xn − yn ),
72
3.3. Résultats généraux pour une analyse de Lyapunov
(3.3.1) ρn := 1 − (1 − κ) νn+1
νn
(pour n ≥ 0) et ρ−1 := ρ0 .
73
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Notons que la forme de cette suite de type énergie est bien connue dans la littérature
(voir, par exemple, [5, 16, 40, 105]).
Un résultat préliminaire important concernant la suite (En (s, q)) est donné par le
lemme suivant :
Lemme 3.3.1. Supposons que les conditions (3.1.2) soient vérifiées. Soient
{xn , yn }n≥0 ⊂ H des suites générées par (3.2.4)-(3.2.5) avec des paramètres {κ, e, µ}
strictement positifs. Soit (νn ) vérifiant les conditions suivantes :
(3.3.3c) (1 − κ) νn+1
νn
< 1, (pour n ≥ 0).
(3.3.5) β0 = 2
ν̇ ,
ρ0 1
(3.3.6) βn = 2
ν̇
ρn n+1
+ (κ−1)+
ρn ρn−1
νn
νn−1
− νn+1
νn
(e + νn ) (si n ≥ 1),
74
3.3. Résultats généraux pour une analyse de Lyapunov
Une égalité importante concernant la suite (Gn (s, q)) est établie par la proposition
suivante.
Proposition 3.3.1. Soient p ∈ N. Soient {xn , yn , χ∗n }n≥p ⊂ H des suites vérifiant
(3.3.8) pour n ≥ p. Soient {θn , νn }n≥p ⊂]0, +∞[ et {κ, e} ⊂]0, +∞[. Supposons que
la condition suivante soit vérifiée pour n ≥ p
νn+1
(3.3.10) (1 − κ) < 1.
νn
75
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
La remarque suivante nous montre le lien entre RIGPA et le modèle plus général
introduit précédemment.
(3.3.12a) zn = xn − θn (yn − xn ),
(3.3.12b) ẋn+1 + µ(x∗n+1 + ∇f (zn )) + θn (yn − xn ) = 0, avec x∗n+1 ∈ ∂g(xn+1 ),
(3.3.12c) ẏn+1 + κ(yn − xn ) = 0.
On peut également établir une formulation plus précise de la suite (χ∗n )n . En effet,
par (3.3.12a) et (3.3.12b) nous avons
ainsi que zn − xn+1 = µMµ (zn ) (d’après (3.2.2a)). On en déduit alors que
On obtient, de plus
Nous appliquons la Proposition 3.3.1 dans le cas des suites {zn , xn , yn } générées
par (3.2.4)-(3.2.5). De cette façon, et en exploitant les caractéristiques spécifiques de
la fonction objectif Θ := f + g (comme fait dans [14]), nous établissons des propriétés
76
3.3. Résultats généraux pour une analyse de Lyapunov
Ainsi, comme (νn ) est strictement positive, cette dernière inégalité se réduit à
On observe alors que l’inégalité (3.3.20) sera satisfaite pour tout n ≥ 0 dès lors
qu’elle l’est pour n = 0 (car (νn ) est supposée être croissante).
(B1) Montrons, par souci d’exhaustivité, que pour tout (x, z) ∈ H2 nous avons
(3.3.21) Lµ
Θ(z − µMµ (z)) ≤ Θ(x) + ⟨Mµ (z), z − x⟩ − µ 1 − 2
∥Mµ (z)∥2 .
77
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Par ailleurs, sachant que Mµ (z) = µ−1 z − proxµg (z − µ∇f (z)) et y = z − µMµ (z),
78
3.3. Résultats généraux pour une analyse de Lyapunov
(3.3.26a) Θ(xn+1 ) ≤ Θ(q) + ⟨Mµ (zn ), xn+1 − q⟩ + 21 Lµ2 ∥Mµ (zn )∥2 ,
(3.3.26b) Θ(xn+1 ) ≤ Θ(xn ) + ⟨Mµ (zn ), ẋn+1 ⟩ + 12 Lµ2 ∥Mµ (zn )∥2 .
Lµ2
2
Rn ≥ sτn Θ̄(xn+1 ) − ∥Mµ (zn )∥
2
Lµ2
−1 2
+ τn (ρn τn − s) Θ̄(xn+1 ) − Θ̄(xn ) − ∥Mµ (zn )∥
2
2
−1
−1 2 Lµ 2
= sτn Θ̄(xn+1 ) + τn (ρn τn − s) Θ̄(xn+1 ) − Θ̄(xn ) − ρn τn ∥Mµ (zn )∥
2
Lµ2 −1 2
= sτn Θ̄(xn ) + ρ−1 2
n τn Θ̄(xn+1 ) − Θ̄(xn ) − ρn τn ∥Mµ (zn )∥2
2
Lµ2 −1 2
= Fn − ρ τ ∥Mµ (zn )∥2 ,
2 n n
ce qui, avec (3.3.17) et ∥Mµ (zn )∥2 = µ−2 ∥ẋn+1 + θn un ∥2 (d’après (3.3.16)), entraîne
1
Tn (s) + Ġn+1 (s, q) = − ρ−1 τ 2 ∥ẋn+1 + θn un ∥2 − µRn
2 n n
1 1
≤ − ρ−1 2 2 −1 2
n τn ∥ẋn+1 + θn un ∥ − µFn + Lµρn τn ∥ẋn+1 + θn un ∥
2
2 2
1
= −µFn − (1 − Lµ) ρ−1 2 2
n τn ∥ẋn+1 + θn un ∥ .
2
79
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
où τn = e + νn+1 et où βn est défini dans (3.3.5)-(3.3.6). Rappelons que νn+1 νn−1 est
décroissante pour κ ≤ 1. Ainsi, un rapide calcul nous donne
ρn−1 − ρn (1 − κ) (κ − 1)+
νn+1 νn νn νn+1
(3.3.28) = − ≤ − .
ρn ρn−1 ρn ρn−1 νn νn−1 ρn ρn−1 νn−1 νn +
(3.3.30) 1
(e + ν1 )2 − (e + ν0 )2 ≤ 2
ϑ̇0 = ρ0
ν̇
ρ0 1
(e + ν1 ) = β0 τ0 .
(3.3.31) ϑ̇n ≤ βn τn .
ce qui d’après (3.3.31) nous donne (3.3.27). L’inégalité souhaitée découle alors de
(3.3.24) et (3.3.27). ■
80
3.4. Analyse de la convergence de la méthode
(κ − 1)+
νn νn+1
(3.4.1a) βn = 2ρ−1
n ν̇n+1 + − (e + νn ) ,
ρn ρn−1νn−1 νn
ν̇n+1
(3.4.1b) γn = (2 − κ − Lµ) + (1 − κ) .
νn
Proposition 3.4.1. Supposons que (3.1.2) soit vérifié. Soient {κ, e, µ} ⊂]0, +∞[
ainsi que (νn )n≥0 vérifiant (3.3.3). Supposons que les conditions suivantes soient
satisfaites :
Alors, pour toutes suites {zn , xn , yn }n≥0 ⊂ H générées par (3.1.3)-(3.1.4) et pour
q ∈ S, la suite de type énergie (En (e, q))n≥1 (donnée par (3.3.2)) est décroissante. De
plus, nous avons les estimations suivantes :
81
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
(3.4.3) ρn−1
Θ(xn ) − min Θ ≤ µ(e+ν n)
2 E1 (e, q) (pour n ≥ 2),
(3.4.4) −1 2 2
P
n≥1 γn ρn (e + νn+1 ) ∥ẋn+1 + θn (yn − xn )∥ ≤ 2E1 (e, q),
(3.4.5) −1
P
n≥1 (e − βn )(e + νn+1 ) (Θ(xn ) − min Θ) ≤ µ E1 (e, q),
(3.4.6) −1 2 2 −2
P
n≥1 γn ρn (e + νn+1 ) ∥Mµ (zn )∥ ≤ 2µ E1 (e, q),
1
En+1 (e, q) − En (e, q) + γn ρ−1 2 2
n τn ∥ẋn+1 + θn un ∥ + µ (e − βn ) τn Θ̄(xn ) ≤ 0.
2
N
X −1 N
X −1
(3.4.9) EN (e, q) + 2
γn ∥ẋn+1 + θn un ∥ + µ τn (e − βn ) Θ̄(xn ) ≤ E1 (e, q).
n=1 n=1
82
3.4. Analyse de la convergence de la méthode
2
(3.4.10a) 1
2
∥e(q − xN ) + νN uN ∥2 + µ (νρNN+e)
−1
Θ̄(xN ) ≤ E1 (e, q),
PN −1
(3.4.10b) −1 2 2
n=1 γn ρn τn ∥ẋn+1 + θn un ∥ ≤ 2E1 (e, q),
P −1
(3.4.10c) µ Nn=1 (e − βn )τn Θ̄(xn ) ≤ E1 (s, q),
Proposition 3.4.2. Supposons que (3.1.2) soit vérifié. Soient {xn , yn } ⊂ H des
suites générées par (3.1.3)-(3.1.4) avec κ ∈]0, 2[, ainsi que des paramètres strictement
positifs {µ, e, νn } vérifiant les conditions ci-dessous
83
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
(3.4.11a) ∗
(ν̇n )n≥0 ⊂ [ν̄m ∗
, ν̄M ] ∗
(avec ν̄m ∗
> 0 et ν̄M > 0),
(3.4.11b) (νn+1 νn−1 )n≥0 est décroissante (si κ ∈]0, 1]),
(3.4.11c) (1 − κ)νn+1 νn−1 < 1 (pour n ≥ 0)
(3.4.11d) (νn )n≥0 ⊂](κ − 1)+ e, +∞[,
(3.4.11e) e > supn≥1 βn .
(3.4.12a) µ ∈ 0, L1 ,
κ=1 et
(3.4.12b) κ ∈]0, 1[ et µ ∈ 0, 2−κ
L
,
∗
(κ−1)+ ν̄M
(3.4.12c)
2−κ
κ ∈]1, 2[, µ ∈ 0, L et ν0 > 2−κ−µL
.
Alors, pour q ∈ S, la suite de type énergie (En (e, q))n≥1 (donnée par (3.3.2)) est
décroissante. De plus, les suites (xn ) et (yn ) convergent faiblement vers un élément
z̄ ∈ S et nous avons :
(3.4.13b) 2 −1
P
n n∥ẋn ∥ < +∞, ∥ẋn ∥ = o(n ),
(3.4.13c) 2 −1
P
n n∥ẏn ∥ < +∞, ∥ẏn ∥ = o(n ).
- Si κ ∈]0, 2[ et µ ∈ 0, 2−κ
L
, alors
Démonstration. Nous savons, d’après (3.4.11a), qu’il existe deux constantes stric-
84
3.4. Analyse de la convergence de la méthode
(3.4.16) ∗
∀n ≥ 0, ν̄m ∗
n + ν0 ≤ νn ≤ ν̄M n + ν0 .
νn+1
(3.4.19) lim = 1.
n→+∞ νn
Par conséquent, les estimations (3.4.17) et (3.4.19), nous donne, par définition de
(θn ) et de (ρn ) (introduits dans (3.2.5) et (3.3.1)),
ν̄ ∗
(3.4.21) γn ≥ 2 − κ − µL − (κ − 1)+ νMn .
(3.4.22a) et µ ∈ 0, 2−κ
κ ∈]0, 1] L
⇒ inf n≥0 γn ≥ 0,
(3.4.22b) κ ∈]0, 1] et µ ∈ 0, 2−κ
L
⇒ inf n≥0 γn > 0,
∗
(κ−1)+ ν̄M
(3.4.22c) κ ∈]1, 2[, µ ∈ 0, 2−κ et ν0 >
L 2−κ−µL
⇒ inf n≥0 γn > 0.
85
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
(C0)-(C4) suivantes :
(C0) Considérons les plages de paramètres suivantes :
Montrons que si l’une des conditions (ha) ou (hb) est vérifiée alors les propriétés
suivantes sont obtenues :
(3.4.24d)
P
n nΘ(xn ) < +∞;
(3.4.24e) 2 2
P
n γn n ∥Mµ (zn )∥ < +∞;
En effet, sous les conditions (ha) et (hb), les éléments (3.4.24a)-(3.4.24f) pro-
viennent directement de la Proposition 3.4.1, ainsi que des conditions (3.4.11),
inf n≥0 γn ≥ 0 (d’après (3.4.22), et des estimations νn−1 = O(n−1 ) (d’après (3.4.17) et
ρn ∼ κ (lorsque n → +∞).
(C1) Considérons les plages de paramètres suivantes
etµ ∈ 0, 2−κ
(ha1) : κ ∈]0, 1] L
,
∗
(κ−1)+ ν̄M
κ ∈]1, 2[, µ ∈ 0, L et ν0 >
2−κ
(hb) : 2−κ−µL
.
Montrons que, sous chacune des conditions (ha1) et (hb), nous avons :
En effet, d’après (3.4.22), on a inf n≥0 γn > 0. Ainsi, en utilisant (ha1)-(hb), ainsi
que (3.4.24c), (3.4.24e) et (3.4.24f), nous obtenons directement (3.4.26a), (3.4.26b)
et (3.4.26c).
86
3.4. Analyse de la convergence de la méthode
et
µ ∈ 0, L1 ,
(ha2) : κ=1
(ha3) : κ ∈]0, 1[ et µ ∈ 0, 2−κ
L
,
∗
(κ−1)+ ν̄M
(hb) : κ ∈]1, 2[, µ ∈ 0, L et ν0 >
2−κ
2−κ−µL
.
Montrons que si l’une des conditions (ha2), (ha3) ou (hb) est vérifiée, alors :
(3.4.28a) (En (s, q))n est convergente, pour tout (s, q) ∈ [β̄, e[×S où β̄ = supj≥1 βj ;
(3.4.28b) n∥ẋn ∥2 < +∞ ;
P
n
87
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
1 −1 νn+1
− 2 (e − s) hn (s) − 2(κ − 1)+ (e − s)ρn νn ∥ẋn+1 ∥2 .
(3.4.31a) β̄ = supj≥1 βj ,
(3.4.31b) νn+1
ln = (κ − 1)+ νn + 2 (Lµ − 1)+ ρ−1
1 2
n τn ,
(3.4.31c) rn = 1 + 2ρ−1
n
νn+1
νn
(1 − κ)+ .
hn (s) − hn (e) − (e
− s)(rn − 1)
νn+1
(3.4.33) = −(e − s) 1 + 2ρ−1
(1 − κ + (κ − 1)+ )
n νn
νn+1
= −(e − s) 1 + 2ρ−1
n νn
(1 − κ) + ,
88
3.4. Analyse de la convergence de la méthode
Ėn+1 (s, q) + µ s − β̄ τn Θ̄(xn )
(3.4.35) ≤ ln ∥ẋn+1 + θn un ∥2 − 12 (e − s) (hn (s) − (e − s)(rn − 1)) ∥ẋn+1 ∥2
= ln ∥ẋn+1 + θn un ∥2 − 12 (e − s0 ) (hn (e) − (e − s0 )rn ) ∥ẋn+1 ∥2 .
89
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Par conséquent, on déduit de (3.4.39) et de (3.4.38) que la suite (En (s0 , q)) est
convergente. De plus, en utilisant (3.4.38) et (3.4.40), on obtient n n∥ẋn ∥2 < +∞.
P
- Supposons que (ha3) ou (hb) soit vérifié. D’après (3.4.36), nous avons
1
PN −1
(e − s0 ) (hn (e) − (e − s0 ) rn ) ∥ẋn+1 ∥2
(3.4.42) 2 n=1
P −1
≤ E1 (s0 , q) + N 2
n=1 ln ∥ẋn+1 + θn un ∥ .
On déduit alors des estimations (3.4.41) et (3.4.43) que (En (s0 , q)) est convergent.
De plus, il résulte de (3.4.38) et de (3.4.42) que l’on a n n∥ẋn ∥2 < +∞
P
2
(3.4.44) En (0, q) = 12 ∥νn un ∥2 + µ (νρnn−1
+e)
Θ̄(xn ).
2
(3.4.46) hn (e) − ern ∼ νn+1 ≥ 0 (lorsque n → +∞).
κ
90
3.4. Analyse de la convergence de la méthode
et τn = e + νn+1 ), on a aussi
X
(3.4.47) τn Θ̄(xn ) < +∞,
n
tandis que (comme indiqué dans (3.4.43)) chacune des conditions (ha3) ou (hb)
garantit que
X
(3.4.48) ln ∥ẋn+1 + θn un ∥2 < +∞.
n
Il en résulte d’après (3.4.45), (3.4.46), (3.4.47) et (3.4.48), que la suite (En (0, q))
converge lorsque n → +∞. De plus, en supposant que n n∥un ∥ < +∞, on
2
P
Par conséquent, sachant que la suite (En (0, q))n est convergente et en remarquant
que n n−1 = +∞, on en déduit que En (0, q) → 0 lorsque n → +∞. Ce dernier
P
91
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
(e + νn )2
(3.4.52) Θ̄(xn ) → 0 et νn ∥yn − xn ∥ → 0 (lorsque n → +∞).
ρn−1
s2
1
(3.4.53) lim En (s, q) = + s(e − s) lim ∥xn − q∥2 .
n→+∞ 2 2 n→+∞
Il en résulte que (∥xn − q∥) converge lorsque n → +∞. De plus, l’estimation (3.4.50b)
assure que Θ(xn ) − Θ(q) → 0 lorsque n → +∞. Par ailleurs, pour toute sous-suite de
92
3.4. Analyse de la convergence de la méthode
ce qui implique que Θ(x∗ ) = Θ(q). Ceci prouve que x∗ ∈ S, assurant ainsi que tout
point d’accumulation faible de (xn ) appartient à S. En appliquant le lemme d’Opial
[87] nous concluons que la suite (xn ) converge faiblement vers un élément z̄ ∈ S.
Par conséquent, comme ∥xn − yn ∥ → 0 lorsque n → +∞ (d’après (3.4.50c)), nous
déduisons notre résultat de convergence.
(C5) Convergence de Θ(yn ). Démontrons que, les propriétés suivantes sont
obtenues sous chacune des conditions (ha2) et (ha3), :
(3.4.55a)
P
n n(Θ(yn ) − min Θ) < +∞;
(3.4.55b) limn n2 (Θ(yn ) − min Θ) = 0.
93
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Rappelons à présent le lemme suivant (voir [73, Lemma 4.3] pour une preuve),
Lemme 3.4.2. Soit (an ) une suite de réels positifs telle que
(3.4.63) lim sup n2 Γn ≤ lim sup κ−1 (2(1 − κ)(n + 1)Γn + κ(n + 1)2 ∆n ).
n→+∞ n→+∞
Ainsi, comme limn→+∞ νn2 ∆n = 0 (d’après (3.4.50b)) et n≥0 nΓn < +∞ (d’après
P
Lemme 3.4.3. Supposons que (3.1.2) soit vérifiée et soient {zn , xn , yn } ⊂ H générées
par (3.1.3)-(3.1.4) avec κ ∈]0, 2[, µ ∈]0, 2−κ
L
[, e > 0. Soit (νn ) une suite strictement
positive. Alors pour n ≥ 1, on a les inégalités suivantes :
2
(3.4.64a) ∥ẏn+1 − ẏn ∥2 ≤ 2 κe+ν̇n
∥ẏn ∥2 + 2(κµ)2 ∥Mµ (zn−1 )∥2 ,
e+νn
2
(3.4.64b) ∥zn−1 − yn+1 ∥2 ≤ 2∥ẏn − ẏn+1 ∥2 + 2 κe+ ν̇n
e+νn
∥ẏn ∥2 ,
94
3.4. Analyse de la convergence de la méthode
κe+ν̇n
1 − καn−1 = e+νn
.
Proposition 3.4.3. Supposons que les conditions (3.1.2) soient vérifiées et soient
{zn , xn , yn } ⊂ H des suites générées par (3.1.3)-(3.1.4). Soit e > supn≥0 βn et
∗
(κ−1)+ ν̄M
supposons que (νn ) satisfait (3.4.11) avec ν0 > 2−κ−µL . Alors, sous chacune des
conditions (3.4.12a), (3.4.12b) et (3.4.12c), nous avons
(3.4.67) n2 ∥ẏn+1 − ẏn ∥2 < +∞, n2 ∥Mµ (xn )∥2 < +∞.
P P
n n
Ainsi, comme αn est bornée et que n∥ẏn ∥2 < +∞ (d’après (3.4.50a)) ainsi que
P
n
95
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
n∥Mµ (zn )∥2 < +∞, on obtient n n∥Mµ (yn )∥2 < +∞. Par ailleurs, la condition
P P
n
e > supn≥0 βn assure que n∥ẋn+1 ∥ → 0 et n∥un ∥ → 0 (lorsque n → +∞), d’après
(3.4.50c)-(3.4.50d). Ainsi sachant que θn est borné (car θn = κ + καn − 1), on déduit
de (3.4.64c) que l’on a n∥Mµ (zn )∥ → 0 lorsque n → +∞. On obtient alors d’après
l’estimation (3.4.68), que n∥Mµ (yn )∥ → 0, car αn est borné et n∥ẏn ∥ → 0 (d’après
(3.4.50c)).
Prouvons (3.4.67). En utilisant la relation (3.2.3), on obtient
ẏn+1 − ẏn + (1 − καn−1 )ẏn + (κµ)Mµ (zn−1 ) = 0,
où 1 − καn−1 = κe+ ν̇n
e+νn
. Donc, comme ν̇n ≤ β, on obtient
2
∥ẏn+1 − ẏn ∥2 ≤ 2 κe+βe+νn
∥ẏn ∥2 + 2(κµ)2 ∥Mµ (zn−1 )∥2 ,
Par conséquent, la première estimation de (3.4.67) est déduite des deux estimations
n n∥ẏn ∥ < +∞ et n n ∥Mµ (zn )∥ < +∞ (d’après (3.4.50a) et (3.4.6)).
2
P P 2 2
Remarque 3.4.6. Notons que, pour toute suite (νn ) vérifiant νn+1 − νn ∼ β lorsque
n → +∞ (pour un certain β > 0), la méthode (3.1.3)-(3.1.4) ne dépend que de β
via le terme inertiel αn = (1−κ)e+ν n
κ(e+νn+1 )
(donné par (3.1.4)). Ce dernier peut, en effet,
(1−κ)e∗ +ν̄n
se réécrire αn = κ(e∗ +ν̄n+1 ) avec e∗ = (1/β)e et où ν̄n = (νn /β) vérifie ν̄n+1 − ν̄n ∼ 1.
Ainsi, choisir β ̸= 1 ne présente aucun intérêt dans notre étude.
96
3.4. Analyse de la convergence de la méthode
Supposons en outre que l’une des conditions (3.4.71a) et (3.4.71c) soit satisfaite
(3.4.71a) κ = 1 et µ ∈ 0, L1 ,
Alors les suites (xn ) et (yn ) convergent faiblement vers un élément z̄ ∈ S et nous
avons les estimations suivantes :
(3.4.72b) 2 −1
P
n n∥xn+1 − xn ∥ < +∞, ∥xn+1 − xn ∥ = o(n ),
(3.4.72c) 2 −1
P
n n∥yn+1 − yn ∥ < +∞, ∥yn+1 − yn ∥ = o(n ).
- Si κ ∈]0, 2[ et si µ ∈ 0, 2−κ
L
, alors
97
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
tel que 2κ−1 − ϵ > βn (pour n ≥ p). Par conséquent, la condition e > 2κ−1 entraîne
que e > ϵ + βn (pour n ≥ p), ce qui implique que e ≥ ϵ + supn≥p βn > supn≥p βn .
Il en résulte que l’on a, pour p suffisamment grand
Remarque 3.4.7. Il est clair que le Théorème 3.4.1 couvre les résultats proposés
par Attouch-Peypouquet [14] concernant la méthode AFB (3.1.7), à savoir le cas
particulier de (3.1.3)-(3.1.4) lorsque κ = 1 et e = α−1 (pour un certain α strictement
positif ). Par conséquent, l’application du Théorème 3.4.1 pour e > 2 nous donne les
résultats de convergence de [14] qui ont été obtenus pour α > 3.
Le second résultat concerne le cas κ > 1 et où (νn ) est donné pour n ≥ 1 par
la formule récursive
κ + (1 − 2ϵn )ρn−1
(3.4.76) νn+1 = νn 1 + ,
2νn ρn−1 − (κ − 1)
pour une certaine suite (ϵn ) positive décroissant lentement vers 0, et où ν0 et ν1 sont
des paramètres strictement positifs vérifiant
Remarque 3.4.8. Une accélération de la méthode semble avoir été obtenue concer-
nant la suite récursive (νn ) donnée par (3.4.76) au lieu du choix classique νn = n + ν0 .
Cependant, nous n’étudions pas cette question d’un point de vue théorique.
La remarque suivante montre que la formule récursive (3.4.76) est bien définie.
98
3.4. Analyse de la convergence de la méthode
Remarque 3.4.9. Rappelons que pour κ > 1, la propriété νn+1 ≥ νn > 0 (pour
un certain n ≥ 0) entraîne ρn ≥ κ. On peut alors vérifier par récurrence, qu’en
prenant ν0 et ν1 vérifiant (3.4.77), la suite (νn ) donnée par (3.4.76) est bien définie
et satisfait, pour n ≥ 1,
(3.4.78) ρn−1 ≥ κ,
(3.4.79) 2νn ρn−1 ≥ 2κν0 > 2(κ − 1),
(3.4.80) νn+1 ≥ νn .
Il en résulte que (3.4.76) génère une suite (νn ) croissante et strictement positive.
Proposition 3.4.4. Pour toute suite (νn ) générée par (3.4.76), ainsi que pour (ϵn ),
ν0 et ν1 vérifiant (3.4.77), nous avons les propriétés suivantes
(3.4.81) 1−ϵ̄
2
≤ ν̇n ≤ 2 pour n ≥ 2, donc νn−1 = O(n−1 ) et νn = O(n),
(3.4.82) νn+1 − νn ∼ 1 (lorsque n → +∞).
κ−1
νn νn+1
(3.4.83) 2ν̇n+1 + − = 2(1 − ϵn )
ρn−1 νn−1 νn
99
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Les inégalités (3.4.86) et (3.4.87) nous donnent alors (1/2)(1 − 2ϵ̄) ≤ ν̇n+1 ≤ 2
et νn → +∞ (lorsque n → +∞). On en déduit donc que νn+1 νn−1 → 1 (lorsque
n → +∞). Ceci implique que ρn ∼ κ (lorsque n → +∞), ce qui entraine, d’après
(3.4.85) et ϵn → 0, que
κ−1 (κ − 1) νn
νn+1 2 − = 2(1 − ϵn ) + 2νn − .
νn ρn−1 ρn−1 νn−1
Théorème 3.4.2. Supposons que les conditions (3.1.2) soient vérifiées. Soient
{xn , yn } ⊂ H des suites générées par (3.1.3)-(3.1.4) avec κ ∈]1, 2[. Soit (νn )n≥0 définie
de façon récursive par (3.4.76)-(3.4.77b) et soient des paramètres {ν0 , ν1 , e, µ} ⊂
100
3.4. Analyse de la convergence de la méthode
Alors les suites (xn ) et (yn ) convergent faiblement vers un élément z̄ ∈ S et nous
obtenons
(3.4.93b) 2
∥xn+1 − xn ∥ = o(n−1 ),
P
n n∥xn+1 − xn ∥ < +∞,
(3.4.93c) 2
∥yn+1 − yn ∥ = o(n−1 ),
P
n n∥yn+1 − yn ∥ < +∞,
(3.4.94) 2(κ−1)
ν1 > ν0 > max e(κ − 1), 2−κ−µL
,
Par conséquent, comme la suite (νn ) est croissante (et donc, ρn ≥ κ, car κ > 1),
on obtient d’après (3.4.83) que βn = 2ρ−1
n ≤ 2κ . Ainsi, à partir de la condition
−1
e > 2κ−1 (d’après (3.4.92)), on en déduit que e > 2κ−1 ≥ supn≥1 βn . Il en résulte
alors que
101
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
chaque ai est divisé par leur norme, afin d’obtenir L = 1/4. Les autres paramètres
sont d = 8, N = 768 et λ = 1/768. Rappelons que e doit être tel que e > 2κ−1 pour
la convergence de RIGPA.
102
3.5. Simulations numériques
100 100
RIGPA (κ = 1) RIGPA (κ = 1)
RIGPA (κ = 0.3) RIGPA (κ = 1.3)
10−2 RIGPA (κ = 0.7) 10−2 RIGPA (κ = 1.9)
10−4 10−4
Θ(xn ) − Θ(x∗ )
Θ(xn ) − Θ(x∗ )
10−6 10−6
10−8 10−8
10−10 10−10
10−12 10−12
10−14 10−14
100 101 102 103 104 100 101 102 103 104
Iterations Iterations
103
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
100 100
RIGPA (κ = 1) RIGPA (κ = 1)
RIGPA (κ = 0.3) RIGPA (κ = 1.3)
10−2 RIGPA (κ = 0.7) 10−2 RIGPA (κ = 1.9)
10−4 10−4
Θ(xn ) − Θ(x∗ )
Θ(xn ) − Θ(x∗ )
10−6 10−6
10−8 10−8
10−10 10−10
10−12 10−12
10−14 10−14
100 101 102 103 100 101 102 103
Iterations Iterations
100 100
RIGPA (κ = 1) RIGPA (κ = 1)
RIGPA (κ = 0.3) RIGPA (κ = 1.3)
10−2 RIGPA (κ = 0.7) 10−2 RIGPA (κ = 1.9)
10−4 10−4
Θ(xn ) − Θ(x∗ )
Θ(xn ) − Θ(x∗ )
10−6 10−6
10−8 10−8
10−10 10−10
10−12 10−12
10−14 10−14
100 101 102 103 100 101 102 103
Iterations Iterations
104
3.5. Simulations numériques
100 100
RIGPA-(C1) RIGPA-(C1)
RIGPA-(C2) RIGPA-(C2)
10−2 10−2
10−4 10−4
Θ(xn ) − Θ(x∗ )
Θ(xn ) − Θ(x∗ )
10−6 10−6
10−8 10−8
10−10 10−10
10−12 10−12
10−14 10−14
100 101 102 103 104 100 101 102 103
Iterations Iterations
Figure 3.5.4 – Évolution de Θ(xn ) − minH Θ pour RIPGA avec e = 1.5 (gauche),
e = 7 (droite), κ = 1.9 et νn = n + ν0 pour (C1), la formule récursive de (νn ) pour
(C2), avec ν1 = ν0 + 1 et ϵn = (ln(n + 55))−0.5 . Les autres paramètres sont les mêmes
que pour la Figure 3.5.1.
La convergence des valeurs de la fonction objectif avec un taux de o(n−2 ) ainsi que la
propriété de convergence rapide vers 0 des gradients (à savoir, n n2 ∥∇Θ(xn )∥2 <
P
105
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
√
(3.5.3) α ≥ 3, 0 ≤ β < 2 µ et µ ≤ L−1
Θ .
Bien que IGAHD n’a pas encore été étendu au cas de la minimisation structurée,
nous l’utilisons pour résoudre le problème (3.5.2) en suivant la même méthodologie
que dans [18] pour laquelle nous rappelons les grandes lignes via la Remarque suivante.
Remarque 3.5.11. Pour une matrice symétrique définie positive M ∈ Rd×d , les
auteurs de [18] ont montré que argminRd Θ = Fix(proxMΘ ) = argminRd ΘM , où ΘM et
M
proxΘ (x) sont respectivement l’enveloppe de Moreau et l’application proximale de Θ
dans la métrique ⟨M ·, ·⟩, définis par
∗
proxM
Θ (x) = proxrg (x + rA (y − Ax)).
Considérons ici une matrice réelle aléatoire de taille 100 × 100 ainsi qu’un
vecteur aléatoire y tel que chacune des composantes soit dans [−1, 1]. La Figure 3.5.5
décrit l’évolution de Θ(xn ) − min Θ obtenus pour RIPGA (pour diverses valeurs de e)
et IGAHD (avec diverses valeurs de α). Sur cette Figure, les valeurs de Θ(xn ) − min Θ
ont été fixées à 10−10 lorsqu’elles sont inférieures à 10−10 . Il semble que IGAHD
surpasse RIPGA pour des valeurs de κ dans ]0, 1]. Ceci n’est cependant plus le cas
pour des valeurs de κ dans ]1, 2[ suffisamment grandes.
106
3.5. Simulations numériques
104
RIGPA (κ = 0.7) RIGPA (κ = 0.7)
104
RIGPA (κ = 1.9) RIGPA (κ = 1.9)
102 IGAHD (β = 0) IGAHD (β = 0)
IGAHD (β = 0.63) 102 IGAHD (β = 0.63)
100
100
Θ(xn ) − Θ(x∗ )
Θ(xn ) − Θ(x∗ )
10−2
10−2
10−4
10−4
10−6 10−6
10−8 10−8
10−10 10−10
100 101 102 103 104 105 100 101 102 103 104 105
Iterations Iterations
Figure 3.5.5 – Profils de Θ(xn )−minH Θ pour RIPGA et IGAHD avec (e, α) = (7, 8)
(gauche) et (e, α) = (15, 16) (droite). Les conditions initiales sont y0 = y1 = x0 =
x1 = (1, 1, ..., 1) avec r = (1/2)||A||−2 , ν0 = 1, νn = n + ν0 et µ = 0.01.
107
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Dans le cas discret, une image en noir et blanc de taille n × m pixels peut être
vue sous la forme d’une matrice (ui,j ) avec 1 ≤ i ≤ n et 1 ≤ j ≤ m ou d’un vecteur
u ∈ Rn×m pour lequel les éléments de ce vecteurs sont la concaténation des colonnes
de la matrice (ui,j ). Pour λ > 0 et en désignant toujours par u⋄ l’image issue de u
après ajout d’un bruit blanc, le modèle de ROF discret propose de débruiter l’image
u⋄ à l’aide du problème de minimisation suivant :
λ
(3.5.10) min ∥u − u⋄ ∥22 + TV(u)
u∈Rn×m 2
avec (Du)i,j = ((Du)i,j,1 , (Du)i,j,2 ) donnés par l’application D : Rn×m 7→ Rn×m ×Rn×m
définie par
u
i+1,j − ui,j si 1 ≤ i < n
(3.5.12) (Du)i,j,1 =
0 si i = n
u
i,j+1 − ui,j si 1 ≤ j < m
(3.5.13) (Du)i,j,2 =
0 si j = m
108
3.5. Simulations numériques
L’approche duale du problème (3.5.10) proposée dans cette section est classique
est en grande partie basée sur celles développées par Chambolle-Pock dans [42]
et Li-Han-Wang-Tiande-Guo dans [68] pour laquelle nous détaillons chacune des
différentes étapes.
Commençons tout d’abord par présenter le lemme suivant.
Lemme 3.5.4. Soit H un espace de Hilbert réel de produit scalaire ⟨., .⟩ et de norme
p
|.| = ⟨., .⟩. Soient (a, b) ∈ H2 alors on a
|a| = max⟨a, b⟩
|b|≤1
À l’aide de la variable duale p = (p1 , p2 ) ∈ Rn×m ×Rn×m que l’on peut écrire pixel
par pixel sous la forme vectorielle pi,j = (pi,j,1 , pi,j,2 ) pour 1 ≤ i ≤ n et 1 ≤ j ≤ m,
on peut définir un produit scalaire sur Rn×m × Rn×m en posant
n X
X m
(3.5.15) ⟨pi,j , qi,j ⟩ et ||p|| = ⟨p, p⟩,
p
⟨p, q⟩ =
i=1 j=1
pour tout p, q ∈ Rn×m × Rn×m . Ainsi, grâce au Lemme 3.5.4, on peut réécrire
l’opérateur TV défini par (3.5.11) sous la forme
n X
X m
(3.5.16) TV(u) = max ⟨(Du)i,j , pi,j ⟩ = max⟨Du, p⟩,
|pi,j |≤1 p∈P
i=1 j=1
109
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
où P désigne l’ensemble
λ
(3.5.18) min ⋄ 2
||u − u ||2 + max⟨Du, p⟩ .
u∈Rn×m 2 p∈P
On observe que le premier terme de (3.5.18) ne contient pas la variable duale p, nous
pouvons alors reformuler le problème primal (3.5.10) en un problème min max de la
façon suivante
λ
(3.5.19) min max ⋄ 2
||u − u ||2 + ⟨Du, p⟩ .
u∈Rn×m p∈P 2
110
3.5. Simulations numériques
nous donne
1
(3.5.22) u = u⋄ + div p.
λ
Enfin, cette dernière équation peut se réécrire sous la forme d’un problème de
minimisation sans contrainte en définissant δP comme étant la fonction indicatrice
de P où P est défini par (3.5.17) :
1
(3.5.25) min ⋄ 2
|| div p + λu ||2 + δP (p) .
p∈Rn×m×2 2
avec
0 si p ∈ P
(3.5.26) δP (p) = .
+∞ sinon
On observe alors que le problème (3.5.25) est bien de la forme (3.5.14) et que
cette fois-ci, l’opérateur proximal de l’application δP de paramètre τ > 0 se calcule
facilement. En effet, ce dernier n’est autre que la projection orthogonal sur l’ensemble
P, et peut être donné pixel par pixel par la formule suivante (voir [42, 68])
p̃i,j
(3.5.27) p̂ = proxτ δP (p̃) ⇐⇒ p̂i,j = .
max{1, |p̃i,j |}
111
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
avec f (p) = 12 || div p + λu⋄ ||22 et g(p) = δP (p) où δP est défini par (3.5.26). La
fonction f est convexe et différentiable et on a ∇f (p) = −D ◦ (div p + λu⋄ ) où D est
défini par (3.5.12)-(3.5.13). De plus, les opérateurs D et div sont linéaires et vérifient
|||D|||2 = ||| div |||2 ≤ 8 (voir [39]), où |||.||| désigne la norme d’opérateurs. Ceci nous
montre que pour tout p, q ∈ Rn×m × Rn×m ,
Afin de quantifier la qualité des images obtenues, nous comparons le PSNR (Peak
Signal to Noise Ratio) (voir [108]) en fonction du nombre d’itérations pour chacun des
algorithmes RIGPA, Accelerated Forward-Backward (AFB) et Forward-Backward
(FB). Rappelons que le PSNR est une mesure dérivée de l’erreur quadratique moyenne
et indique le rapport entre l’intensité maximale du pixel et la puissance de la distorsion.
Rappelons enfin que bien que ces deux mesures soient simple à calculer, elle peuvent
ne pas correspondre à la qualité visuelle observée, il est donc de plus nécessaire de
comparer visuellement la qualité des images obtenues.
112
113
(a) Image originale (b) Image bruitée
Figure 3.5.6 – (a) Image originale de taille 720 × 540 pixels ; (b) Image obtenue à partir de (a) après ajout d’un bruit
blanc gaussien de moyenne nulle et de variance σ 2 = 0.01 ;
3.5. Simulations numériques
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Les paramètres utilisés pour chacun des algorithmes RIGPA, Accelerated Forward-
Backward (AFB) et Forward-Backward (FB) sont les suivants : λ et τ ont été pris
égaux à 12 et 0.0013 respectivement, les autres paramètres sont
— x0 = y0 = 0.5 × (1, . . . , 1) ∈ R720×540 , κ = 1.9, e = 4, νn = n + 10 pour RIGPA,
— x1 = x0 = 0.5 × (1, . . . , 1) ∈ R720×540 , α = 5, pour AFB,
— x0 = 0.5 × (1, . . . , 1) ∈ R720×540 pour FB.
La Figure 3.5.7 montre l’évolution du PSNR (Peak Signal to Noise Ratio) pour
chacun des algorithmes RIGPA, Accelerated Forward-Backward (AFB) et Forward-
Backward (FB). On observe que les performances de RIGPA sont meilleures que
celles de AFB jusqu’à environ 200 itérations. Après 200 itérations les performances
de RIGPA et de AFB semblent être identiques. Les performances de FB sont quant
à elles, inférieures à celles de RIGPA et de AFB.
28
27
26
PSNR (en dB)
25
24
23
22 AFB
RIGPA
FB
21
1 10 100 1000
Itérations
114
115
Figure 3.5.8 – Représentation des images obtenues avec RIGPA (gauche), AFB (milieu) et FB (droite) après 20 itérations.
3.5. Simulations numériques
sous-gradients
116
Figure 3.5.9 – Représentation des images obtenues avec RIGPA (gauche), AFB (milieu) et FB (droite) après 250
itérations.
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
117
Figure 3.5.10 – Représentation des images obtenues avec RIGPA (gauche), AFB (milieu) et FB (droite) après 1000
itérations.
3.5. Simulations numériques
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
3.6 Annexe
(3.6.1a) θn = 1
τn
(νn − ϱνn+1 ),
(3.6.1b) ẋn+1 + χ∗n + θn un = 0,
(3.6.1c) ẏn+1 + κun = 0.
Afin d’obtenir ce résultat, remarquons que Ġn+1 (s, q) peut être formulé comme
suit
(3.6.3) 2
Ġn+1 (s, q) = s(ν̇n+1 an + νn+1 ȧn+1 ) + seḃn+1 + νn+1 2
ċn+1 + cn (νn+1 − νn2 ),
118
3.6. Annexe
119
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
En effet, d’après (3.6.1b), nous avons ẋn+1 = −θn un − χ∗n . Ce qui, peut être réécrit,
pour tout ξn ̸= 1, sous la forme
Par conséquent, en prenant le produit scalaire du côté gauche de (3.6.11) avec χ∗n et
en ajoutant (1/2)∥χ∗n ∥2 , on obtient d’après (3.6.12) et ∥χ∗n ∥2 = ∥ẋn+1 + θn un ∥2 ,
120
3.6. Annexe
comme suit
νn ρ n
(3.6.13) θn = où τn = e + νn+1 .
τn
Ainsi, comme ρn > 0 (d’après la condition (3.3.3a)), on déduit de (3.6.13) que θn est
une suite strictement positive.
Introduisons à présent la suite réelle (γ̄n ) définie par
sρn
(3.6.14) γ̄n = 1 − (avec s > 0).
τn
Ensuite, pour s > 0 donné, nous montrons que les itérés générés par (3.3.8) (ou,
de manière équivalente, par (3.6.1)) vérifient
121
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
obtenue, on obtient
2
= − sνn + ϱνn+1 + sνn ρn Qn
+ − 21 νn2 − ϱ2 νn+1
2
1 2
+ 2 νn ρn ∥un ∥2
1
+ ρ−1 1
2
2
2
se − νn+1 n τn γ̄n − 2 ∥ẋn+1 ∥2 .
2
2
wn = sνn + ϱνn+1 − s(νn − ϱνn+1 ) = ϱ νn+1 + sνn+1 ,
ηn = 21 νn2 − νn+1 ϱ2 − 21 (νn2 − ϱνn νn+1 ) = 21 ϱνn+1 (νn − νn+1 ϱ) = 21 ϱνn+1 νn ρn ,
2
σn = 12 se − νn+1 + ρ−1 1 −1 2
2
2
1 2
n nτ γ̄n − 2
= 2
se − ν n+1 + ρ τ
n n (2γ̄n − 1) .
= τn,e (eρ−1 −1
n − s) − se + ρn (νn+1 ) ,
2
2σn = (ρ−1 2 −1
n − 1)(νn+1 ) + τn,e (eρn − s)
(3.6.21)
= ((νn+1 )2 + eτn,e ) (ρ−1
n − 1) + τn,e (e − s).
122
3.6. Annexe
D’une part, comme wn = ϱνn+1 (νn+1 + s) (d’après (3.6.18)) et que τn,s = s + 2νn+1 ,
on a
wn2 = (ϱνn+1 )2 ((νn+1 )2 + sτn,s ).
En posant Sn = ϱρn νn νn+1 (de sorte que Sn = 2ηn et ψn = 2σn Sn − wn2 ), on obtient
en utilisant (3.6.21) et la définition de ψn
Ainsi, en remarquant que eτn,e − sτn,s = (e − s)τn,e+s (car τn,t := t + 2νn+1 , pour tout
t ≥ 0), on en déduit que
1 (e − s)
Tn (u, x) = Sn ∥u + ςn x∥2 + Sn τn,e + (ϱνn+1 )2 τn,e+s ∥x∥2 .
2 2Sn
D’autre part, on a ςn = wn
Sn
(car Sn = 2ηn ), ainsi que wn = ϱνn+1 (νn+1 + s),
123
Chapitre 3 – Minimisation structurée de fonctions convexes non lisses avec décroissance rapide des
sous-gradients
Sn = ϱρn νn νn+1 et 1
θn
= e+νn+1
ρ n νn
(d’après (3.6.13)). On obtient alors
124
Chapitre 4
4.1 Introduction
Dans ce chapitre, H désigne un espace de Hilbert réel muni d’un produit scalaire
noté ⟨., .⟩ et de la norme induite notée ∥ . ∥. L’objectif de ce chapitre est de concevoir
des méthodes proximales rapides pour la résolution d’inclusions monotones structurées.
Nous nous concentrons, dans un premier temps, au plus simple de ces problèmes qui
s’écrit :
125
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
où (µn ) ⊂]0, 2λ[ et où JµAn := (I + µn A)−1 est la résolvante de A d’indice µn qui est
bien connue pour être univoque et partout définie (voir [31, 58, 97])
Il est bien connu que (4.1.1)-(4.1.2) inclut le problème de minimisation convexe
structuré non lisse
Il a été montré (voir chapitre 1, Section 1.2.3) que lorsque la méthode Forward-
Backward (FB) est appliquée au problème de minimisation (4.1.4), celle-ci génère
des suites (xn ) faiblement convergentes vérifiant Θ(xn ) − inf H Θ = O(n−1 ) (pour
la convergence en valeur) ainsi que ∥xn+1 − xn ∥ = O(n−1 ) (concernant la vitesse
discrète). Ces estimations ont été considérablement améliorées via l’algorithme AFB
(décrit dans le chapitre 1, Section 1.2.4). Ce dernier produit en effet des suites (xn )
vérifiant les taux de convergences Θ(xn ) − inf H Θ = o(n−2 ) et ∥xn+1 − xn ∥ = o(n−1 ).
Par la suite, diverses variantes de AFB (généralisées à des opérateurs maximaux
126
4.1. Introduction
ALG1
▶ Initialisation : Choisir {z−1 , x0 , y0 } ⊂ H.
▶ Étape principale : Pour {zn−1 , xn , yn } ⊂ H donnés, on effectue
Avec {κ, t, µ} ⊂]0, +∞[ et où les suites (θn )n et γn sont définies par :
νn −(1−κ)νn+1
(4.1.8a) θn := e+νn+1
et γn := 1 − s0
e+νn+1
1 − (1 − κ) νn+1
νn
.
1
(4.1.9) Mµ (z) = (z − JµA (z − µBz)).
µ
127
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
(2) En suivant la même méthodologie que Maingé [71] (voir aussi Raguet-Fadili-
Peyré [94]), nous adapterons les techniques d’accélération proposées dans ce
chapitre au problème d’inclusion plus général :
(4.1.11)
Pp
trouver x̄ ∈ H tel que 0 ∈ B x̄ + k=1 Ak x̄,
128
4.1. Introduction
Les méthodes d’éclatement (pour le calcul des zéros de la somme de deux opéra-
teurs maximaux monotones) peuvent être divisées en deux grandes catégories :
(a) Les méthodes d’éclatement qui procèdent essentiellement en des étapes
« backward » (voir Peaceman-Rachford et Douglas-Rachford ([51, 90]).
(b) Les méthodes d’éclatement qui combinent à la fois des étapes « backward »
et « forward ».
- (b1) Un exemple classique de ces méthodes est l’algorithme « forward-backward »
(FB) donné par (4.1.3). En particulier, lorsque B est β-cocoercif, il a été démontré que
la méthode FB génère des suites faiblement convergentes dès lors que (µn ) ⊂]0, 2β[.
- (b2) Un autre exemple de méthode lorsque B est univoque est l’algorithme
« forward-backward-forward » proposé par Tseng [106]. Cet algorithme génère des
suites faiblement convergentes lorsque B est L-lipschitzien dès lors que (µn ) ⊂]0, 1/L[.
- (b3) Par la suite, des variantes plus générales des méthodes forward-backward
et forward-backward-forward ont été adaptés à des problèmes d’inclusions monotones
plus générales tels que ceux de la forme (4.1.11) (voir [43, 94]).
Lorsque ∇f est L-lipschitzien et que (µn ) ⊂]0, L−1 [, cette méthode est bien connue
pour générer des suites (xn ) faiblement convergentes vérifiant le taux sous-linéaire
(f + g)(xn ) − inf H (f + g) = O(n−1 ) (voir chapitre 1, section 1.2.3).
Cette méthode fut, par la suite, améliorée via notamment l’algorithme « Fast
Iterative Thresholding Algorithm » (FISTA) proposé par Beck-Teboulle [24] qui est
basé sur les techniques d’accélération de Güler et Nesterov. Il a été démontré que
FISTA génère des suites qui garantissent le taux (f + g)(xn ) − inf H (f + g) = O(n−2 ),
cependant, la convergence de ces itérés n’a pas été établie.
129
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
n−1
zn = xn + n+α−1 (xn − xn−1 ),
(4.1.13)
xn+1 = proxµ (xn − µ∇f (xn )),
où µ ∈]0, L−1 [ et α > 0. Pour α > 3, les auteurs de [14]) ont démontré que (4.1.13)
génère des suites (xn ) faiblement convergentes qui vérifient le taux de convergence en
valeur (f + g)(xn ) − inf H (f + g) = o(n−2 ) au lieu des taux O(n−1 ) et O(n−2 ) pour
(4.1.3) et FISTA respectivement.
Dans le cas d’un opérateur maximal monotone A : H → 2H quelconque, des va-
riantes accélérées de la méthode PPA ont été proposées via notamment les algorithmes
« RIPA » (Regularized Inertial Proximal Algorithm) et « PRINAM » (Proximal Regu-
larized Inertial Newton Algorithm) étudiés respectivement par Attouch-Peypouquet
[13] et Attouch-László [12]. Malgré des propriétés asymptotiques intéressantes, ces
algorithmes requièrent un indice proximal non borné et ne peuvent donc pas être
étendus au cadre des méthodes forward-backward.
Dans le même contexte, une méthode du point proximal accélérée utilisant un
indice proximal constant a été proposée par Kim [65]. Cette dernière est basée sur
l’approche Performance Estimation Problem (PEP) introduite par Drori-Teboulle
[52]. Cette méthode fournit le taux de convergence O(n−2 ) pour les résidus de points
fixes. La convergence des itérés n’a, cependant, pas été démontrée.
À notre connaissance, il n’existe pas de résultats de convergence qui permettent
d’étendre les estimations obtenues pour (4.1.13) (concernant la minimisation convexe)
au problème d’inclusion monotone générale (4.1.1)-(4.1.2). Excepté l’algorithme
étudié par Attouch-Cabot dans [8], seules quelques méthodes accélérées empiriques
basées sur des techniques inertielles et de relaxation ont été proposées. Rappelons
quelques-uns des ces algorithmes
(c1) Des variantes inertielles de (4.1.3) avec un opérateur B cocoercif, ont été
étudié par Moudafi-Oliny [78]
130
4.1. Introduction
et Lorenz-Pock [70]
où (αn ) et (µn ) sont des suites strictement positives. Notons que dans (4.1.15),
l’évaluation de l’opérateur B se fait en la variable zn (au lieu de xn pour (4.1.14)).
(c2) Une variante de (4.1.3) de type réflexion pour un opérateur lipschitzien B a
été étudié pour Cevher-Vu [38] :
où {αn , wn , µn } sont des suites bornées strictement positives. Sous diverses conditions
portant sur ces derniers paramètres, les auteurs ont établi la convergence faible des
itérés (xn ) ainsi que des taux de convergence concernant la vitesse discrète et de
résidus de points fixes ∥Mµ (zn )∥ (où Mµ est défini par (4.1.9). En particulier, la
méthode (4.1.17) fait intervenir des techniques d’accélération de Nesterov via le choix
αn := 1 − αn−1 avec α > 2 (pour le coefficient inertiel), µn = µ ∈]0, 2β[ (pour l’indice
proximal) et wn = 1 − ρn−2 où 0 < ρ < α(α − 2)(1 − 4β µ
) (concernant le terme de
relaxation). Avec ces paramètres, les auteurs ont démontré (voir [9, Corollary 4.9])
les estimations ∥xn+1 − xn ∥ = O(n−1 ) et n n∥xn+1 − xn ∥2 < +∞ (pour la vitesse
P
discrète) ainsi que n n−1 ∥Mµ (xn )∥2 < +∞ et limn→+∞ ∥Mµ (xn )∥ = 0 (concernant
P
131
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
Notons que ces estimations sont similaires à celles obtenues pour des sous-gradients
par l’algorithme « Accelerated Forward-Backward » dans le cadre de la minimisation
convexe structurée non lisse (voir chapitre 3, Section 3.1.4).
Des propriétés de Lyapunov pour cette suite seront établies plus loin, exposons
tout d’abord quelques résultats préliminaires.
4.2.1 Préliminaires.
[Link] Cocoercivité de Mµ et quelques estimations.
Afin d’établir nos principaux résultats, nous rappelons une certaine propriété de
cocoercivité concernant l’opérateur Mµ dont nous tirons quelques résultats prélimi-
naires. Les deux remarques suivantes se révèleront utiles pour notre analyse.
132
4.2. Propriétés de type Lyapunov
Remarque 4.2.14. Supposons que l’opérateur B soit λ-cocoercif (pour une certaine
constante λ strictement positive). On peut alors vérifier, sous la condition µ ∈]0, 2λ[
(voir, par exemple, [8, Lemma B1]) que l’opérateur Mµ est σ-cocoercif avec
µ
(4.2.3) σ =µ 1− .
4λ
Ces deux remarques nous permettent d’énoncer quelques estimations utiles concer-
nant les itérés produits par l’algorithme(4.1.7)-(4.1.8).
Lemme 4.2.5. Supposons que les conditions (4.1.2) soient vérifiées. Soient µ ∈]0, 2λ[
et t ∈]0, σ[. Soient {zn , xn , yn } ⊂ H les suites générées par(4.1.7)-(4.1.8). Alors, pour
n ≥ 1, nous avons les propriétés suivantes :
133
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
(4.2.6) ρn := 1 − (1 − κ) νn+1
νn
,
2
(4.2.7) Tn (s) := 12 (1 − κ)ρn νn νn+1 yn − xn + 1
θn
− e−s
νn ρn
ẋn+1
Lemme 4.2.6. Soient {zn , xn , yn } ⊂ H des suites générées par (4.1.7)-(4.1.8) avec
des paramètres {e, κ, s0 , t, µ, νn } ⊂]0, +∞[. Alors nous avons les propriétés suivantes
(1) S’il existe un entier naturel n1 tel que
νn+1
(4.2.8) (1 − κ) < 1 (pour n ≥ n1 ),
νn
134
4.2. Propriétés de type Lyapunov
(4.2.11) νn ≥ (e − s0 ) δ+(1−δ)|1−κ|
δ(1−|1−κ|)
− s0 (1 − κ),
alors on a (pour n ≥ n1 )
+ 21 (e − s0 )ρ−1 2
n (e + νn+1 ) ∥ẋn+1 ∥ ≤ 0.
où {κ, θn , e, νn } sont des paramètres strictement positifs. À cette fin, nous associons
à (4.2.14) la quantité Gn (s, q) définie pour (s, q) ∈ [0, +∞[×H par
135
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
(4.2.16) − q⟩
+s(e + νn+1 )⟨dn , xn+1
+ 1 − s e+νρnn+1 ρ−1 2
n (e + νn+1 ) ⟨dn , ẋn+1 ⟩ = −Tn (s),
On observe alors que l’algorithme (4.1.7)-(4.1.8) entre dans le modèle général (4.2.14)
en prenant dn = t (Mµ (zn ) − γn Mµ (zn−1 )).
Le lemme suivant est une conséquence directe de la Proposition (4.2.1) pour une
suite γn positve quelconque :
Lemme 4.2.7. Soient {zn , xn , yn } ⊂ H des suites générées par (4.1.7)-(4.1.8) avec
γn ≥ 0 et des paramètres {e, κ, t, µ, νn } ⊂]0, +∞[ vérifiant (4.2.8). Alors, pour tout
(s, q) ∈]0, +∞[×H , on a (pour n ≥ 1)
Ėn+1 (s, q) + s (e + νn ) − γn (e + νn+1 ) ⟨tMµ (zn−1 ), xn − q⟩
(4.2.19) + 21 ρ−1 2
n (e + νn+1 ) ∥ẋ
2
n+1 + θn (yn − xn )∥
+ρ−1 2
n (e + νn+1 ) (ϑn − γn )Qn + ϑn Zn = −Tn (s),
136
4.2. Propriétés de type Lyapunov
où En (s, q), ρn et Tn (s) sont donnés respectivement par (4.2.1) (4.2.6) et (4.2.7),
ϑn := 1 − s e+νρnn+1 et où
Par conséquent, à l’aide de ces deux résultats, l’équation (4.2.19) nous donne
+γn ρ−1 2
n (e + νn+1 ) ⟨tMµ (zn ) − tMµ (zn−1 ), ẋn+1 ⟩ = −Tn (s0 ).
2
(4.2.22) −Tn (s0 ) ≤ 12 |1 − κ|ρn νn νn+1 yn − xn + θ1n − νe−s ρ
n n
0
ẋ n+1
1 −1 −1
− 2 (e − s0 ) (e + 2νn+1 )ρn + s0 (ρn − 1) ∥ẋn+1 ∥2 .
137
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
2
1 e−s0
yn − xn + θn
− νn ρn
ẋn+1
2
1 e−s0
= (θ (y
θn n n
− xn ) + ẋn+1 ) − ẋ
νn ρn n+1
(4.2.23) 2 2
1 1 e−s0
≤ (1 + 2ε) (θ (y
θn n n
− xn ) + ẋn+1 ) + (1 + 2ε
) ẋ
νn ρn n+1
2
= (1 + 2ε) θ12 ∥ẋn+1 + θn (yn − xn )∥ + (1 + 2 1
2ε
) e−s0
νn ρn
∥ẋn+1 ∥2 .
n
(4.2.24)
1
+ρn νn νn+1 ( 2 + 4ε1
) νe−s 0
n ρn
∥ẋn+1 ∥2
νn+1
= ( 12 + ε)ρ−1
n νn
(e + νn+1 )2 ∥ẋn+1 + θn (yn − xn )∥2
+( 21 + 1
4ε
)(e − s0 )2 ρ−1
n
νn+1
νn
∥ẋn+1 ∥2 .
νn+1
1
+ ε |1 − κ|ρ−1
− Tn (s0 ) ≤ 2 n νn
(e + νn+1 )2 ∥ẋn+1 + θn (yn − xn )∥2
νn+1
+ 12 + 4ε
1
|1 − κ|(e − s0 )2 ρ−1
n νn
∥ẋn+1 ∥2
− 12 (e − s0 ) ρ−1 2
n (e + 2νn+1 + s0 (1 − ρn )) ∥ẋn+1 ∥ .
− Tn (s0 )
νn+1
1
+ ε |1 − κ|ρ−1
≤ 2 n νn
(e + νn+1 )2 ∥ẋn+1 + θn (yn − xn )∥2
νn+1 νn+1
+ 21 (e − s0 )ρ−1 1 1
n e + 2ν n+1 + s 0 (1 − κ) νn
− 2 2
+ 4ε
|1 − κ|(e − s 0 ) νn
∥ẋn+1 ∥2
νn+1
= − 21 (e − s0 )ρ−1 1
n e + 2νn+1 + s 0 (1 − κ) − (e − s 0 ) 1 + 2ε
|1 − κ| νn
∥ẋn+1 ∥2 ,
138
4.2. Propriétés de type Lyapunov
νn+1
−Tn (s0 ) ≤ 12 C1 (ε, κ)ρ−1
n νn
(e + νn+1 )2 |ẋn+1 + θn (yn −xn )∥2
(4.2.25)
− 21 (e − s0 )ρ−1
n e + 2νn+1 − C2 (ε, κ) νn+1
νn
∥ẋn+1 ∥2 ,
(4.2.27) |1 − κ| < 1.
1 1 − |1 − κ|
(4.2.28) ε0 = δ ,
2 |1 − κ|
on obtient
νn+1
−Tn (s0 ) ≤ 21 C̄1 ρ−1
n νn
(e + νn+1 )2 |ẋn+1 + θn (yn − xn )∥2
(4.2.30)
νn+1
− 21 (e − s0 )ρ−1
n e + 2ν n+1 − C̄ 2 νn
∥ẋn+1 ∥2 ,
139
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
δ(1−|1−κ|) νn+1
1+ δ+(1−δ)|1−κ|
> νn
⇔ 1 − C1 (ε0 , κ) νn+1
νn
> 1 − 2δ − (1 − 2δ)|1 − κ| = (1 − 2δ)(1 − |1 − κ|).
De plus, la condition (4.2.11) peut se réécrire pour n ≥ n1 (n1 étant un entier naturel
suffisamment grand) sous la forme
νn+1
(4.2.34) νn+1 − C2 (ε0 , κ) ≥ 0.
νn
(4.2.35) limνn+1
<1+ δ(1−|1−κ|)
(pour tout δ ∈]0, 12 [).
n→+∞ νn δ+(1−δ)|1−κ|
(4.2.36) νn+1
νn
<1+ δ(1−|1−κ|)
δ+(1−δ)|1−κ|
,
140
4.3. Analyse de la convergence de la méthode.
+ 21 (e − s0 )ρ−1 2
n (e + νn+1 ) ∥ẋn+1 ∥ ≤ 0,
(4.3.3) ρn = κ − (1 − κ) ν̇n+1
νn
.
141
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
Une première série d’estimations est donnée par le lemme suivant dans le but de
démontrer la convergence de l’algorithme ALG1.
Lemme 4.3.8. Soient {zn , xn , yn } ⊂ H les suites générées par ALG1. Alors, sous
les conditions (4.1.2), (4.3.1), κ ∈]0, 2[ et s0 ∈]0, e[, nous avons :
(4.3.4d)
P 2 2
n νn ∥Mµ (zn ) − Mµ (zn−1 )∥ < +∞,
(4.3.4e) 2
P
n νn ∥ẋn+1 ∥ < +∞,
(4.3.4f)
P 2 2
n νn ∥ẋn+1 + θn (yn − xn )∥ < +∞,
(4.3.4g) 2
P
n νn ∥yn − xn ∥ < +∞.
où Un = ⟨tMµ (zn−1 ), xn − q⟩, Zn = ⟨tMµ (zn ) − tMµ (zn−1 ), ẋn+1 ⟩, c est une constante
strictement positive et où Wn = ∥ẋn+1 + θn (yn − xn )∥2 . Observons que le Lemme
4.2.5 garantit, sous les conditions (4.3.1), que les quantités Un et Zn sont positives.
Par ailleurs, concernant le second terme du côté gauche de (4.3.5), on obtient d’après
(4.3.1e) et pour un entier n1 suffisamment grand
Par conséquent, il résulte de (4.3.5) et des arguments précédents que la suite positive
(En+1 (s0 , q))n≥n1 est décroissante, et donc qu’elle converge. Ceci nous donne (4.3.4a).
En outre, En (s0 , q) s’écrit
1 1
En (s0 , q) = ∥s0 (q − xn ) + νn (yn − xn )∥2 + s0 (e − s0 )∥xn − q∥2 + s0 (e + νn )Un .
2 2
142
4.3. Analyse de la convergence de la méthode.
On en déduit donc que la suite (xn ) est bornée. Cela nous conduit à (4.3.4b). Par
ailleurs, en sommant l’inégalité (4.3.5) pour n allant de n1 à N (pour un certain
N ≥ n1 ), on a
EN +1 (s0 , q) + s0 N
P
n=n1 (s0 ρn − ν̇n+1 ) Un
(4.3.7)
PN PN
+ n=n1 (γn ρ−1 2
n )(e + νn+1 ) Zn + c
−1 2
n=n1 ρn (e + νn+1 ) Wn
+ 12 (e − s0 ) N −1 2
P
n=n1 ρn (e + νn+1 ) ∥ẋn+1 ∥ ≤ En1 (s0 , q).
résulte alors que n νn ∥un ∥2 < +∞ (car θn ∼ κ, lorsque n → +∞), ce qui nous
P
donne (4.3.4g). ■
143
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
(4.3.11d)
P
n νn |⟨Mµ (zn−1 ), ẋn+1 ⟩| < +∞,
Ainsi, comme ẋn = −un − (κ − 1)un−1 (d’après (4.3.10)), l’équation précédente nous
donne
144
4.3. Analyse de la convergence de la méthode.
Établissons à présent des estimations sur la suite Hn à l’aide de cette dernière égalité.
En utilisant les paramètres de (4.3.13) ainsi que la relation ρn = κ − (1 − κ)ν̇n+1 νn−1
(d’après (4.3.3)), on obtient
γn − θn + κ − 1
= −s0 ρn (e + νn+1 )−1 − νn (e + νn+1 )−1 κ − (1 − κ) ν̇n+1
νn
+κ
= −s0 ρn (e + νn+1 )−1 + (e + νn+1 )−1 (−κνn + (1 − κ)ν̇n+1 + κe + κνn+1 )
= −s0 ρn (e + νn+1 )−1 + (e + νn+1 )−1 (ν̇n+1 + κe)
= (e + νn+1 )−1 (−s0 ρn + ν̇n+1 + κe) .
145
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
Ainsi, comme inf n≥n1 (s0 ρn −2ν̇n+1 )(e+νn ) > 0 (pour un certain entier n1 suffisamment
grand), n νn ∥un ∥2 < +∞ (d’après (4.3.4g)) et que la quantité (eρn − ν̇n+1 − κe)
P
est bornée, on en déduit que n (e + νn+1 )∥Hn ∥2 < +∞. Cette dernière estimation
P
nous donne (4.3.11a). De plus, les arguments précédents impliquent l’existence d’un
l1 ≥ 0 vérifiant limn→+∞ (e + νn )2 ∥Hn ∥2 = l1 . Remarquons que nous avons aussi
limn→+∞ (e + νn+1 )2 ∥Hn ∥2 = l1 (car (e+ν
(e+νn )
n+1 )
→ 1 lorsque n → +∞). Par conséquent,
comme n (e + νn+1 ) = +∞ (car ν̇n est borné d’après (4.3.1e)), on en déduit que
−1
P
(4.3.11c)).
Par ailleurs, en utilisant le Lemme 4.2.6 et en passant à la limite lorsque s → 0+
dans (4.2.9), nous obtenons
2
νn+1 ∥ẋn+1 ∥2 − νn2 ∥ẋn ∥2 + 12 ρ−1 2
n (e + νn+1 ) ∥ẋn+1 + θn (yn − xn )∥
2
+ (e + νn+1 ) ρ−1 2
n (e + νn+1 ) ⟨tMµ (zn ) − tMµ (zn−1 ), ẋn+1 ⟩
+s0 (e + νn+1 )⟨tMµ (zn−1 ), ẋn+1 ⟩
2
+ 12 (1 − κ)ρn νn νn+1 yn − xn + θ1n − νneρn ẋn+1
+ 12 e(e + 2νn+1 )ρ−1 2
n ∥ẋn+1 ∥ = 0,
146
4.3. Analyse de la convergence de la méthode.
2
νn+1 ∥ẋn+1 ∥2 − νn2 ∥ẋn ∥2
≤ −s0 (e + νn+1 )⟨tMµ (zn−1 ), ẋn+1 ⟩
2
− 21 (1 − κ)ρn νn νn+1 yn − xn + 1
θn
− e
νn ρn
ẋn+1
≤ s0 (e + νn+1 )|⟨tMµ (zn−1 ), ẋn+1 ⟩|
2
2
2
+|1 − κ|ρn νn+1 y n − xn + 1
ẋ
θn n+1
+ e2 |1 − κ| νn+1
νn
ρ−1
n ∥ẋn+1 ∥
(4.3.23) e + νn+1 ∼ νn , ρn 2
2 νn+1
θn
∼ κ1 νn2 , νn+1 −1
νn
ρn ∼ κ−1 , lorsque n → +∞.
147
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
Par conséquent, comme n νn ∥yn − xn ∥2 < +∞, et n νn ∥Mµ (zn )∥2 < +∞ (d’après
P P
(4.3.4g) et (4.3.11c)), on en déduit que n νn ∥Mµ (yn )∥2 < +∞, à savoir (4.3.11h).
P
De plus, (4.3.24) montre que νn ∥Mµ (yn )∥ → 0 lorsque n → +∞, car νn ∥yn −xn ∥ → 0
et νn ∥Mµ (zn )∥ → 0 lorsque n → +∞ (d’après (4.3.11f) et (4.3.11g) respectivement).
On obtient alors (4.3.11i) . ■
Énonçons à présent le résultat principal de cette section.
Théorème 4.3.1. Soient κ ∈]0, 2[, e > 0 et s0 ∈]0, e[. Supposons que les suites
{zn , xn , yn } ⊂ H soient générées par ALG1, sous les conditions (4.1.2) et (4.3.1).
Alors les suites (xn )n , (yn )n et (zn )n convergent faiblement vers un élément x̄ ∈ S et
nous avons les estimations suivantes :
(4.3.25c) νn ∥Mµ (zn )∥2 < +∞, νn2 ∥Mµ (zn ) − Mµ (zn−1 )∥2 < +∞,
P P
n n
(4.3.25d)
P
n ⟨Mµ (zn−1 ), xn − q⟩ < +∞ (pour q ∈ S).
148
4.3. Analyse de la convergence de la méthode.
De plus, nous savons que la suite (En (s0 , q))n est convergente (d’après le Lemme
4.3.8) et que
1
∥s0 (q − xn ) − νn ẋn ∥2 + 12 s0 (e − s0 )∥xn − q∥2
En (s0 , q) =
(4.3.29) 2
+s0 (e + νn )⟨tMµ (zn−1 ), xn − q⟩.
1
(4.3.30) lim En (s0 , q) = lim s0 e∥xn − q∥2 .
n→+∞ n→+∞ 2
149
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
Donc, comme ∥ẋn+1 ∥ = o(νn−1 ), ∥Mµ (zn )∥ = o(νn−1 ) (d’après (4.3.25a)), on obtient
De plus, comme Mµ (zn ) = t−1 (zn − xn+1 ) (d’après la Remarque 4.2.13), nous pouvons
réécrire la suite ξn sous la forme
On observe alors à partir de cette dernière égalité que ξn ⇀ x̄ lorsque n → +∞, car
xn ⇀ x̄ et zn ⇀ x̄ lorsque n → +∞. Par ailleurs, la relation (4.3.35) nous donne
150
4.3. Analyse de la convergence de la méthode.
ce qui, en posant
s’écrit
(4.3.40) ∥B(ξn ) − B(zn−1 )∥ ≤ λ−1 ∥ξn − zn−1 ∥ = λ−1 µ∥Mµ (zn−1 )∥.
Alors les suites (xn ), (yn ) et (zn ) convergent faiblement vers un élément x̄ ∈ S et
nous avons les estimations suivantes
(4.3.43d)
P
n ⟨Mµ (zn−1 ), xn − q⟩ < +∞ (pour q ∈ S).
151
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
1 2
(4.3.46) lim sup ν̇n+1 < s0 κ ⇐⇒ s0 > .
n→+∞ 2 κ
On vérifie alors, sous les conditions (4.3.42), que les conditions (4.3.1) sont satisfaites
(pour n assez grand). ■
−1
(4.4.1) trouver x̄ ∈ S := (B +
Pp
k=1 Ak ) (0) ̸= ∅,
Soulignons que l’algorithme ALG2 fournit une autre façon de calculer la résolvante
d’une somme d’opérateurs maximaux monotones en un point y ∈ ran (I + pi=1 Ai ).
P
Cela s’observe en prenant B comme étant l’opérateur défini pour x ∈ H par B(x) =
x − y (donc B est 1-cocoercif).
La suite de notre méthodologie suit les mêmes lignes que celles de Maingé [71] et
la preuve du théorème suivant est donnée par souci d’exhaustivité.
152
4.4. Une variante plus générale de l’algorithme proposé
Remarque 4.4.19 (voir Maingé [71]). Soient {ςk }pk=1 ⊂]0, 1[ tels que pk=1 ςk = 1
P
(4.4.2)
Pp
trouver z̄ ∈ Sp := {z ∈ Hp | i=1 ςi zi ∈ S},
pour lequel il a été démontré qu’il possède un ensemble de solutions Sp non vides
(dès lors que S ≠ ∅). Le problème (4.4.2) peut également être reformulé comme une
inclusion monotone correspondant au problème (4.1.1)-(4.1.2) sur E. Introduisons,
en effet, les applications ĀG et B̄ de E dans E définies pour {xi }pi=1 ∈ E par
(4.4.3) ĀG ({xi }pi=1 ) = { ςµi Ai (xi )}pi=1 , B̄ ({xi }pi=1 ) = {B(xi )}pi=1 ,
On peut alors vérifier que ĀG et B̄ sont des opérateurs maximaux monotones sur E.
Ainsi les opérateurs de réflexion RĀG = 2JĀG − IHp et RNΓ = 2JNΓ − IHp sont bien
définis, ce qui nous permet de considérer les applications T , T1 et T2 de E dans E
tels que
Il a été établi (voir [94, Propositions 4.11, 4.12 et 4.15]), que pour un certain
opérateur maximal monotone A′G : E → 2E , l’ensemble des solutions Sp de (4.4.2)
peut s’écrire
−1
(4.4.6) Sp = A′G + B̄ ◦ JNΓ (0),
et que l’opérateur B̄ ◦ JNΓ est λ-cocoercif (voir la section 4.2 de [94, Proposition 4.1]).
De plus, Sp n’est rien d’autre que l’ensemble des points fixes de l’opérateur T où T
s’écrit
153
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
ALG2
▶ Initialisation : Choisir {z−1 , y0 , ζ0 } ⊂ Hp , κ ∈]0, 2[, {e, s0 , ν0 , µ, t} ⊂]0, +∞[,
(ςk )pk=1 ⊂]0, 1[.
▶ Étape principale : Pour {zn−1 , yn , ζn } ⊂ Hp donnés (avec n ≥ 0), on effectue
(4.4.9a) zn = ζn − θn (yn − ζn ) − γn (ζn − zn−1 ),
(4.4.9b) ωn = pk=1 ςk zn,k ,
P
p
(4.4.9c) t Ak
ζn+1 = zn,k + µ J µ (2ωn − µB(ωn ) − zn,k ) − ωn ,
ςk
k=1
Le théorème suivant présente les taux de convergence ∥ζ̇n ∥Hp = o(n−1 ) (pour la
vitesse discrète) et ∥T (zn ) − zn ∥Hp = o(n−1 ) (concernant les résidus de points fixes)
pour des itérés (zn ) générés par ALG2.
154
4.4. Une variante plus générale de l’algorithme proposé
Théorème 4.4.1. Soient (xn , ζn ) ∈ (Hp )2 des suites générées par ALG2. Soient
{s0 , t, e, ν0 , µ} ⊂]0, +∞[, κ ∈]0, 2[, et (ςk )pk=1 ⊂]0, 1[ vérifiant pk=1 ςk = 1, ainsi que
P
µ
(4.4.11) 0 < µ < 2λ, 0<t<µ 1− .
4λ
(4.4.12) νn = n + ν0 (pour un certain ν0 ≥ 0),
(4.4.13) e > 2κ−1 et s0 ∈]2κ−1 , e[.
(4.4.14d)
P 2 2
n n ∥(T (zn ) − zn ) − (T (zn−1 ) − zn−1 )∥Hp < +∞,
(4.4.14e) ∃ζ̄ ∈ Sp , t.q., (pour k = 1, .., p), ζ̄n,k ⇀ ζ̄k faiblement dans H,
(4.4.14f) xn ⇀ x̄ = pk=1 ςk ζ̄k ∈ S, faiblement dans H,
P
Pp
où T : Hp → Hp est donné par (4.4.7) et où ∥ . ∥2Hp = k=1 ςk ∥ . ∥2 sur Hp .
Démonstration. On peut vérifier (voir [94, Lemma 4.10]), que pour {xk }pk=1 ∈ E
l’on a
(4.4.15)
Pp
JNΓ ({xi }pi=1 ) = { p
j=1 ςj xj }i=1 ,
Alors, pour {zk }pk=1 ∈ E, on obtient d’après T2 = IHp − µB̄ ◦ JNΓ , que
T2 ({zk }pk=1 ) = {zk }pk=1 − µ(B̄ ◦ JNΓ )({zk }pk=1 )
Pp
= {zk }pk=1 − µB̄ ({ p
i=1 ςi zi }k=1 )
Pp
= {zk − µB ( i=1 ςi zi ) }pk=1 .
De plus, pour {yk }pk=1 ∈ E et en posant ȳ = i=1 ςi yi , on obtient d’après
Pp
155
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
156
4.5. Simulations numériques
La Figure 4.5.1 compare les performances de l’algorithme ALG1 pour le calcul des
zéros de A + B à l’aide de la suite ξn∗ := Aξn + Bξn (où ξn = (1 − µt−1 )zn−1 + µt−1 xn )
avec différentes valeurs de κ et de e. Comme pour l’algorithme RIGPA, on observe
que les performances de ALG1 sont meilleures pour des valeurs croissantes de κ dans
]0, 2[. La Figure 4.5.2, montre les performances de ALG1 pour différentes valeurs de t
dans ]0, σ[. On observe que la convergence est meilleure pour des valeurs croissantes
de t dans ]0, σ[. La Figure 4.5.3, quant à elle, montre le comportement asymptotique
des itérés ξn∗ et de la vitesse discrète xn+1 − xn .
104 104
ALG1 (κ = 1.9) ALG1 (κ = 1.9)
103 ALG1 (κ = 1.3) 103 ALG1 (κ = 1.3)
ALG1 (κ = 1) ALG1 (κ = 1)
102 ALG1 (κ = 0.7) 102 ALG1 (κ = 0.7)
ALG1 (κ = 0.3) ALG1 (κ = 0.3)
1
10 101
0
10 100
kξn∗ k
kξn∗ k
−1
10 10−1
10−2 10−2
10−3 10−3
10−4 10−4
10−5 10−5
100 101 102 103 104 105 100 101 102 103 104 105
Itérations Itérations
Figure 4.5.1 – Évolution des itérés ξn∗ pour e = 7 (gauche) et e = 15 (droite) avec
différentes valeurs de κ. Les autres paramètres sont µ = 0.1, s0 = 6.75, t = 0.5σ, νn =
n+2
104
ALG1 t = 0.99σ
ALG1 t = 0.5σ
10 2 ALG1 t = 0.3σ
ALG1 t = 0.1σ
100
kξn∗ k
10−2
10−4
10−6
10−8
100 101 102 103 104 105
Itérations
Figure 4.5.2 – Évolution des itérés ξn∗ pour κ = 1.9 avec différentes valeurs de t. Les
autres paramètres sont µ = 0.1, e = 1.5 × 2/κ, νn = n + 2, s0 = c × 2/κ + (1 − c) × e
avec c = 0.001.
157
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
100
100
10−5
10−5
10−10
10−10
10−15
100 101 102 103 104 105 100 101 102 103 104 105
Itérations Itérations
Cela donne alors lieu à l’algorithme décrit ci-dessous que nous appellerons ALG1-r.
158
4.5. Simulations numériques
ALG1-r
Données: x0,0 ∈ H, {µ, e, t, νk } ⊂]0, +∞[, κ ∈]0, 2[, s0 ∈]0, e[,
νk −(1−κ)νk+1
θk = e+νk+1
et γk = 1 − e+νs0k+1 1 − (1 − κ) νk+1
νk
;
Initialisation :
y0,0 ← x0,0 ;
z0,−1 ← x0,0 ;
pour j allant de 0 à S − 1 faire
pour k allant de 0 à R − 1 faire
zj,k ← xj,k − θk (yj,k − xj,k ) − γk (xj,k − zj,k−1 );
t
xj,k+1 ← 1 − µ zj,k + µt JµA (zj,k − µB(zj,k ));
yj,k+1 ← (1 − κ)yj,k + κxj,k ;
fin
xj+1,0 ← xj,R ;
yj+1,0 ← xj,R ;
zj+1,−1 ← xj,R ;
fin
159
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
10−5
10−10
10−15
kxn k
10−20
10−25
FB
ALG1
10−30 ALG1-r-5000
ALG1-r-2000
10−35 ALG1-r-200
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
Itérations
4.6 Annexe
Proposition 4.6.1. Toutes suites {zn , xn , yn }n≥1 ⊂ H générées par ALG1 vérifient
l’algorithme (4.1.10) pour n ≥ 2.
Démonstration. Soient {zn , xn , yn }n≥1 ⊂ H les suites générées par ALG1 et posons
(4.6.1) un = yn − xn et vn = xn − zn−1 .
(4.6.2a) vn = yn − un − zn−1 ,
(4.6.2b) xn = (1 − µt )zn−1 + µt JµA (zn−1 − µBzn−1 ),
(4.6.2c) un = −κ−1 ẏn+1 .
160
4.6. Annexe
zn = xn − θn un − γn vn
(4.6.3) = yn − un − θn un − γn vn
= yn+1 − ẏn+1 − (1 + θn ) un − γn vn .
à savoir
Par ailleurs, d’après (4.1.7c) on a aussi yn+1 = (1 − κ)yn + κxn , ce qui d’après (4.6.2b)
nous donne
(4.6.6) yn+1 = (1 − κ)yn + κ (1 − t
)z
µ n−1
+ t A
J (zn−1
µ µ
− µBzn−1 ) .
Par conséquent, on déduit de (4.6.2b), (4.6.5) et de (4.6.6) que les itérés {zn , xn , yn }
vérifient pour n ≥ 2,
161
Chapitre 4 – Algorithmes forward-backward accélérés pour la résolution d’inclusions monotones
structurées
⟨dn , xn+1 − q⟩
= ⟨tMµ (zn ) − tγn Mµ (zn−1 ), xn+1 − q⟩
= ⟨tMµ (zn ), xn+1 − q⟩ − γn ⟨tMµ (zn−1 ), ẋn+1 ⟩ − γn ⟨tMµ (zn−1 ), xn − q⟩
= Un+1 − γn Qn − γn Un ,
ainsi que
162
4.6. Annexe
Introduisons à présent la suite Zn = ⟨tMµ (zn ) − tMµ (zn−1 ), ẋn+1 ⟩. On déduit alors
de l’égalité précédente et de (4.6.9) que
Ainsi, comme En (s, q) = Gn (s, q) + (sτn−1 )Un , il résulte de (4.6.14) et (4.6.15), que
l’on a
163
Chapitre 5
Conclusions et perspectives
Un cadre continu et des schémas numériques sont proposés dans cette thèse tant
pour la résolution de problèmes de minimisation convexe structurés que pour la
résolution d’inclusions monotones structurées.
S’agissant de la minimisation convexe structurée, nous avons étudié un algorithme
(issu d’une variante discrète du cadre continu proposé). Nous avons démontré, entre
autres, la propriété de convergence rapide vers zéro des sous-gradients de la fonction
objectif même dans le cas non lisse, en sus des taux de convergence établis pour les
algorithmes récemment proposés dans la littérature. Il serait intéressant de poursuivre
ce travail dans le cadre des fonctions fortement convexes.
Concernant la résolution d’inclusions monotones structurées plus générales, nous
avons développé un algorithme de type Forward-Backward qui nous permet d’obtenir
des taux de convergence intéressants en termes de vitesse discrète et de résidus de
points fixes, à l’instar de ceux obtenus pour la minimisation convexe structurée.
Il serait intéressant de transposer au cadre de la minimisation stochastique, les
résultats obtenus dans cette thèse concernant la minimisation structurée non lisse.
Il s’agira, par exemple, de remplacer le gradient de la fonction régulière par un
estimateur de celui-ci afin d’éviter les calculs trop coûteux du gradient entier. Par
ailleurs, afin de réduire la variance induite par cet estimateur, il serait intéressant
d’avoir recours à une technique de réduction de la variance qui serait adaptée à des
problèmes de machine learning régularisés de (très) grandes échelles.
165
Chapitre 5 – Conclusions et perspectives
166
Bibliographie
167
[8] H. Attouch et A. Cabot. « Convergence of a relaxed inertial forward-
backward algorithm for structured monotone inclusions ». Applied Math.
Optimization 80 (2019), page(s): 547-598. doi : 10 . 1007 / s00245 - 019 -
09584-z.
[9] H. Attouch et A. Cabot. « Convergence rates of inertial Forward-Backward
algorithms ». SIAM Journal on Optimization 28 (2018), page(s): 849-874.
[10] H. Attouch, X. Goudou et P. Redont. « The heavy ball with friction
method, I. The continuous dynamical system : global exploration of the local
minima of a real-valued function by asymptotic analysis of a dissipative
dynamical system ». Communications in Contemporary Mathematics, World
Scientific Publishing Company 2 (2000), page(s): 1-34. doi : 10 . 1142 /
S0219199700000025.
[11] H. Attouch et S.C. László. « Continuous Newton-like inertial dynamics
for monotone inclusions ». Set-valued and variational Analysis (2020). doi :
10.1007/s11228-020-00564-y.
[12] H. Attouch et S.C. László. « Newton-like inertial dynamics and proximal
algorithms governed by maximally monotone operators ». SIAM J. Control
Optimization 30.4 (2020), page(s): 3252-3283. doi : 10.1137/20M1333316.
[13] H. Attouch et J. Peypouquet. « Convergence of inertial dynamics and
proximal algorithms governed by maximally monotone operators ». Mathe-
matical Programming 174 (2019), page(s): 391-432. doi : 10.1007/s10107-
018-1252-x.
[14] H. Attouch et J. Peypouquet. « The rate of convergence of Nesterov’s
accelerated forward-backward method is actually faster than 1/k 2 ». SIAM J.
Optimization (2013), page(s): 1824-1834. doi : 10.1137/15M1046095.
[15] H. Attouch, J. Peypouquet et P. Redont. « Fast convex optimization
via inertial dynamics with hessian driven damping ». Journal of Differential
Equations 261 (2016), page(s): 5734-5783. doi : 10.1016/[Link].2016.08.
020.
[16] H. Attouch et al. « Fast convergence of inertial dynamics and algorithms with
asymptotic vanishing viscosity ». Math. Programming 168 (2018), page(s):
123-175. doi : 10.1007/s10107-016-0992-8.
168
[17] H. Attouch et al. « Fast convex optimization via inertial dynamics combining
viscous and Hessian-driven damping with time rescaling ». Evolution Equations
and Control Theory (2021). doi : 10.3934/eect.2021010.
[18] H. Attouch et al. « First-order optimization algorithms via inertial systems
with Hessian driven damping ». Math. Programming (2019). doi : 10.1007/
s10107-020-01591-1.
[19] J.F. Aujol et C. Dossal. « Optimal rate of convergence of an ODE associated
to the Fast Gradient Descent schemes for b > 0. » (2017). hal : hal-01547251.
[20] J.F. Aujol, C. Dossal et A. Rondepierre. « Optimal convergence rates
for Nesterov Acceleration ». SIAM J. Optimization 29.(4) (2019), page(s):
3131-3153. doi : 10.1137/18M1186757.
[21] J.B. Baillon. « Un exemple concernant le comportement asymptotique de
la solution du problème du + ∂ϕ(u) ∋ 0. » Journal of Functional Analysis 28
(1978), page(s): 369-376.
[22] H.H. Bauschke et P.L. Combettes. « Convex analysis and monotone
operator theory in Hilbert spaces ». 2nd edition, Springer, New York (2017).
doi : 10.1007/978-3-319-48311-5.
[23] A. Beck. First-order methods in optimization. Society for Industrial & Applied
Mathematics, 2017. doi : 10.1137/1.9781611974997.
[24] A. Beck et M. Teboulle. « A fast iterative shrinkage-thresholding algorithm
for linear inverse problems ». SIAM J. Imaging Sci. 2.(1) (2009), page(s):
183-202. doi : 10.1137/080716542.
[25] G. Belgioso et S. Grammatico. « Semi-decentralized Nash equilibrium
seeking in aggregative games with separable coupling constraints and non-
differentiable cost functions ». IEEE Control Systems Letters 1.(2) (2017),
page(s): 400-405. doi : 10.1109/LCSYS.2017.2718842.
[26] R.I. Boţ et E.R. Csetnek. « Second order forward-backward dynamical
systems for monotone inclusion problems ». SIAM Journal on Control and
Optimization 54.(3) (2016), page(s): 1423-1443. doi : 10.1137/15M1012657.
[27] L. Bottou et O. Bousquet. « The tradeoffs of large scale learning ».
Advances in Neural Information Processing Systems (NIPS) 20 (2008), page(s):
161-168.
169
[28] L. Bottou et Y. Le Cun. « On-line learning for very large data sets. » Applied
Stochastic Models in Business and Industry 21 (2005), page(s): 137-151. doi :
10.1002/asmb.538.
[29] S. Boyd. « Subgradient Methods ». Notes for EE364b, Stanford University,
(2013).
[30] H. Brezis. Function Analysis, Sobolev Spaces and Partial Differential Equa-
tions. 2010. doi : 10.1007/978-0-387-70914-7.
[31] H. Brezis. Opérateurs maximaux monotones et semi-groupes de contractions
dans les espaces de Hilbert. T. 5. Burlington, MA : Elsevier Science, 1973.
[32] H. Brezis et P. L. Lions. « Produits infinis de résolvantes. » Israel Journal
of Mathematics 29.(4) (1978), page(s): 329-345.
[33] L.M. Briceño-Arias et P.L. Combettes. « Monotone operator methods for
Nash equilibria in non-potential games ». Springer Proceedings in Mathematics
& Statistics Computational and Analytical Mathematics 50 (2013), page(s):
143-159. doi : 10.1007/978-1-4614-7621-4_9.
[34] R. E. Bruck. « An iterative solution of a variational inequality for certain
monotone operators in Hilbert space ». Bulletin of the American Mathematical
Society 81 (1975), page(s): 890-892. doi : 10.1090/S0002-9904-1975-13874-
2.
[35] R. E. Bruck. « Asymptotic convergence of nonlinear contraction semigroups
in Hilbert space. » Journal of Functional Analysis 18.(1) (1975), page(s):
15-26. doi : 10.1016/0022-1236(75)90027-0.
[36] A. Cabot, H. Engler et S. Gadat. « Second order differential equations
with asymptotically small dissipation and piecewise flat potentials ». Elect. J.
of Differential Equations 17 (2009), page(s): 33-38.
[37] A. Cabot et P. Frankel. « Asymptotics for some semilinear hyperbolic
equations with non-autonomous damping ». Journal of Differential Equations
252 (2012), page(s): 294-322. doi : 10.1016/[Link].2011.09.012.
[38] V. Cevher et B.C. Vu. « A Reflected Forward-Backward Splitting Method
for Mono- tone Inclusions Involving Lipschitzian Operators ». Set Valued and
Variational Analysis (2020). doi : 10.1007/s11228-020-00542-4.
170
[39] A. Chambolle. « An algorithm for total variation minimization and applica-
tions ». J. Math. Imaging Vis (20) (2004), page(s): 89-97. doi : 10.1023/B:
JMIV.0000011325.36760.1e.
[40] A. Chambolle et C. Dossal. « On the convergence of the iterates of
“Fast Iterative Shrinkage/Thresholding Algorithm” ». Journal of Optimization
Theory and Applications 166 (2015), page(s): 968-982. doi : 10.1007/s10957-
015-0746-4.
[41] A. Chambolle et P.L. Lions. « Image recovery via total variation minimiza-
tion and related problems ». Numer. Math 76 (1997), page(s): 167-188. doi :
10.1007/s002110050258.
[42] A. Chambolle et T. Pock. « An introduction to continuous optimization
for imaging ». Acta Numerica, Cambridge University Press (CUP) 25 (2016),
page(s): 161-319. doi : 10.1017/S096249291600009X.
[43] P.L. Combettes et J.C. Pesquet. « Primal-dual splitting algorithm for
solving inclusions with mix- tures of composite, Lipschitzian, and parallel-sum
type monotone operators ». Set Valued and Variational Analysis 20.2 (2012),
page(s): 307-330.
[44] P.L. Combettes et J.C. Pesquet. « Proximal Splitting Methods in Signal
Processing ». Bauschke H., Burachik R., Combettes P., Elser V., Luke D.,
Wolkowicz H. (eds) Fixed-Point Algorithms for Inverse Problems in Science
and Engineering. Springer Optimization and Its Applications 49 (2011). doi :
10.1007/978-1-4419-9569-8_10.
[45] P.L. Combettes et V.R. Wajs. « Signal recovery by proximal forward-
backward splitting ». Multiscale Model Simul 4 (2005), page(s): 1168-1200.
doi : 10.1137/050626090.
[46] E. Corman et X. Yuan. « A generalized proximal point algorithm and its
convergence rate ». SIAM J. Optim 24.4 (2014), page(s): 1614-1638. doi :
10.1137/130940402.
[47] J.B. Cruz et T. Nghia. « On the convergence of the proximal forward-
backward splitting method with linesearches ». Optim. Methods and Software
31.(6) (2016), page(s): 1209-1238. doi : 10.1080/10556788.2016.1214959.
171
[48] E.R. Csetnek. « Continuous dynamics related to monotone inclusions and
non-smooth optimization problems, » Set Valued and Variational Analysis 28
(2020), page(s): 611-642. doi : 10.1007/s11228-020-00548-y.
[49] I. Daubechies, M. Defrise et C. De Mol. « An iterative thresholding
algorithm for linear inverse problems with a sparsity constraint ». Comm.
Pure Appl. Math. 57 (2004), page(s): 1413-1457. doi : 10.1002/cpa.20042.
[50] K. Deimling et S. Grammatico. « Zeros of accretive operators ». Manus-
cripta Mathematica (2017), page(s): 365-374. doi : 10.1007/bf01171148.
[51] J. Douglas et H. H. Rachford. « On the numerical solution of heat
conduction problems in two and three space variables ». Trans. Amer. Math.
Society 82 (1956), page(s): 421-439.
[52] Y. Drori et M. Teboulle. « Performance of first-order methods for smooth
convex minimization : A novel approach ». Math. Programming 145.2 (2014),
page(s): 451-482.
[53] I. Ekeland et R. Temam. Convex Analysis and Variational Problems. 1976.
[54] P. Getreuer. « Rudin-Osher-Fatemi Total Variation Denoising using Split
Bregman ». Image Processing On Line 2 (2012), page(s): 74-95. doi : 10.
5201/ipol.2012.g-tvd.
[55] A. A. Goldstein. « Convex programming in Hilbert spaces ». [Link].
Math. Soc. (70) (1964), page(s): 709-710.
[56] X. Goudou et J. Munier. « The gradient and heavy ball with friction
dynamical systems : the quasiconvex case. » Math. Programming 116 (2007),
page(s): 173-191. doi : 10.1007/s10107-007-0109-5.
[57] O. Güler. « New proximal point algorithms for convex minimization ». SIAM
J. Optimization 2.(4) (1992), page(s): 649-664. doi : 10.1137/0802032.
[58] O. Güler. « On the convergence of the proximal point algorithm for convex
minimization ». SIAM J. Control Optimization 29 (1991), page(s): 403-419.
doi : 10.1137/0329022.
[59] I Guyon et al. « Structural risk minimization for character recognition ».
NIPS’91 : Proceedings of the 4th International Conference on Neural Infor-
mation Processing Systems (1991), page(s): 471-479.
172
[60] A. Haraux. « Systèmes dynamiques dissipatifs et applications ». Masson
RMA17 (1991).
[61] A. Haraux et M.A. Jendoubi. « Convergence of solutions of second order
gradient like systems with analytic nonlinearities ». Journal of Differential
Equations 144.(2) (1998), page(s): 312-320. doi : 10.1006/jdeq.1997.3393.
[62] F. Iutzeler et J M. Hendrickx. « A Generic online acceleration scheme
for Optimization algorithms via Relaxation and Inertia ». (2017). arXiv :
1603.05398v3.
[63] R. Johnson et T. Zhang. « Accelerating stochastic gradient descent using
predictive variance reduction ». Advances in Neural Information Processing
Systems 26 (2013).
[64] J. Kiefer et J. Wolfowitz. « Stochastic estimation of the maximum of a
regression function ». Ann. Math. Stat. 23.(3) (1952), page(s): 462-466. doi :
10.1214/aoms/1177729392.
[65] D. Kim. « Accelerated proximal point method for maximally monotone ope-
rators ». Math. Program (2021). doi : 10.1007/s10107-021-01643-0.
[66] F. Labarre et P.E. Maingé. « First-Order frameworks for continuous
Newton-like dynamics governed by maximally monotone operators ». Set-
Valued and Variational Analysis (2021). doi : 10.1007/s11228-021-00593-
1.
[67] N. Le Roux, M. Schmidt et F. Bach. « A Stochastic Gradient Method
with an Exponential Convergence Rate for Finite Training Sets ». NIPS’12 -
26 th Annual Conference on Neural Information Processing Systems (2012).
hal : hal-00674995v4.
[68] M. Li et al. « Shrinking gradient descent algorithms for total variation regu-
larized image denoising ». Comput Optim Appl 68 (2017), page(s): 643-660.
doi : 10.1007/s10589-017-9931-8.
[69] P.L Lions et B. Mercier. « Splitting algorithms for the sum of two nonlinear
operators ». SIAM J. Numer. Anal. 16.(6) (1979), page(s): 964-979. doi :
10.1137/0716071.
173
[70] D.A Lorenz et T. Pock. « An inertial forward-backward algorithm for
monotone inclusions ». J. Math. Imaging Vision 51 (2015), page(s): 311-325.
doi : 10.1007/s10851-014-0523-2.
[71] P.E. Maingé. « Fast convergence of generalized forward-backward algorithm
for structured monotone inclusions ». (2021). arXiv : 2107.10107.
[72] P.E. Maingé et F. Labarre. « Accelerated methods with fastly vanishing
subgradients for structured non-smooth minimization ». Numerical Algorithms
(2021). doi : 10.1007/s11075-021-01181-y.
[73] P.E. Maingé et S. Maruster. « Convergence in norm of modified
Krasnoselski-Mann iterations for fixed points of demicontractive mappings ».
Applied Mathematics and Computation 217.(24) (2011), page(s): 9864-9874.
doi : 10.1016/[Link].2011.04.068.
[74] Y. Malitsky. « Proximal extrapolated gradient methods for variational
inequalities ». Optimization Methods and Software 33.(1) (2018), page(s):
140-164. doi : 10.1080/10556788.2017.1300899.
[75] B. Martinet. « Détermination approchée d’un point fixe d’une application
pseudo-contractante. Cas de l’application prox ». C.R. Acad. Sc. Paris (1972),
page(s): 163-165.
[76] B. Martinet. « Régularisation d’inéquations variationnelles par approxi-
mations successives ». Rev. Francaise Informat. Recherche Opérationnelle 4
(1970), page(s): 154-158. doi : 10.1051/m2an/197004R301541.
[77] R. May. « Asymptotic for a second order evolution equation with convex
potential and vanishing damping term ». Turkish Journal of Mathematics
41.(3) (2015).
[78] A. Moudafi et M. Oliny. « Convergence of a splitting inertial proximal
method for monotone operators ». J. Comput. Appl. Math. 155.(2) (2003),
page(s): 447-454. doi : 10.1016/S0377-0427(02)00906-8.
[79] A. Nedic et D. Bertsekas. « Convergence rate of incremental subgradient
algorithms ». Stochastic Optimization : Algorithms and Applications 54 (2001),
page(s): 263-304. doi : 10.1007/978-1-4757-6594-6_11.
174
[80] A. Nemirovski et al. « Robust stochastic approximation approach to sto-
chastic programming ». SIAM Journal on Optimization 19.4 (2009), page(s):
1574-1609. doi : 10.1137/070704277.
[81] Y. Nesterov. « A method of solving a convex programming problem with
convergence rate O(1/k 2 ) ». Soviet Mathematics Doklady 27 (1983), page(s):
372-376.
[82] Y. Nesterov. « Gradient methods for minimizing composite objective func-
tion ». Math. Programming (2013), page(s): 125-161. doi : 10.1007/s10107-
012-0629-5.
[83] Y. Nesterov. « Introductory lectures on convex optimization : A basic
course ». Kluwer Academic Publishers 87 (2004). doi : 10.1007/978- 1-
4419-8853-9.
[84] Y. Nesterov. « Smooth minimization of non-smooth functions ». Mathema-
tical Programming 103 (2005), page(s): 127-152. doi : 10.1007/s10107-004-
0552-5.
[85] A. Nitanda. « Stochastic proximal gradient descent with acceleration tech-
niques ». Advances in Neural Information Processing Systems 27 (2014),
page(s): 1574-1582.
[86] P. Ochs, T. Brox et T. Pock. « iPiasco : Inertial proximal algorithm for
strongly convex optimization ». J Math Imaging Vision 53 (2015), page(s):
171-181. doi : 10.1007/s10851-015-0565-0.
[87] Z. Opial. « Weak convergence of the sequence of successive approximations
for nonexpansive mappings ». Bull. Amer. Math. Soc. 73 (1967), page(s):
591-597.
[88] N. Parikh et S. Boyd. « Proximal algorithms ». Foundations and Trends®
in Optimization 1.3 (2014), page(s): 127-239. doi : 10.1561/2400000003.
[89] G.B. Passty. « Ergodic convergence to a zero of the sum of monotone
operators in Hilbert space ». J. Math. Anal. Appl. 72 (1979), page(s): 383-390.
doi : 10.1016/0022-247X(79)90234-8.
[90] D.W. Peaceman et H. H. Rachford. « The numerical solution of parabolic
and elliptic differ- ential equations ». J. Soc. Indust. Appl. Math. 3.1 (1955),
page(s): 28-41.
175
[91] B.T Polyak. « Some methods of speeding up the convergence of iteration
methods ». USSR Computational Mathematics and Mathematical Physics
4.(5) (1964), page(s): 1-17. doi : 10.1016/0041-5553(64)90137-5.
[92] B.T. Polyak. « A new method of stochastic approximation type ». Avtomatika
i Telemekhanika, 51 (1990), page(s): 98-107.
[93] B.T. Polyak et A.B. Juditsky. « Acceleration of stochastic approximation
by averaging ». SIAM Journal on Control and Optimization 30.4 (1992),
page(s): 838-855. doi : 10.1137/0330046.
[94] H. Raguet, J. Fadili et G. Peyré. « A generalized forward-backward
splitting ». SIAM J. Imaging Sci (2013), page(s): 1199-1226. doi : 10.1137/
120872802.
[95] S. Reich. « An iterative procedure for constructing zeros of accretive sets
in Banach spaces ». Nonlinear Analysis : Theory, Methods & Applications
(1978), page(s): 85-92. doi : 10.1016/0362-546x(78)90044-5.
[96] H. Robbins et S. Monro. « A stochastic approximation model ». Ann. Math.
Stat. 22.(3) (1951), page(s): 400-407. doi : 10.1214/aoms/1177729586.
[97] R. T. Rockafellar. « Monotone operators and the proximal point algo-
rithm ». SIAM journal on control and optimization 14.(5) (1976), page(s):
877-898. doi : 10.1137/0314056.
[98] R.T Rockafellar et R.J.B. Wets. « Variational analysis fundamental
principles of mathematical sciences ». Springer 317 (1998).
[99] L.I. Rudin, E. Osher et E. Fatemi. « Nonlinear total variation based noise
removal algorithms ». Physica D : Nonlinear Phenomena 60 (1992), page(s):
259-268. doi : 10.1016/0167-2789(92)90242-F.
[100] D. Ruppert. « Efficient estimations from a slowly convergent robbins-monro
process ». Technical report, Cornell University Operations Research and In-
dustrial Engineering (1988).
[101] K. Scheinberg, D. Goldfarb et X. Bai. « Fast first-order methods for
composite convex optimization with backtracking ». Foundations of Compu-
tational Mathematics 14.(3) (2014), page(s): 389-417. doi : 10.1007/s10208-
014-9189-9.
176
[102] S. Shalev-Shwartz et al. « Stochastic convex optimization ». Conference
on Learning Theory (COLT), (2009).
[103] B. Shi et al. « Understanding the acceleration phenomenon via high-resolution
differential equations ». (2018). arXiv : 1810.08907v3.
[104] M. Sodolov. « Incremental gradient algorithms with stepsizes bounded away
from zero ». Computational Optimization and Applications 11 (1998), page(s):
23-25. doi : 10.1023/A:1018366000512.
[105] W. Su, S. Boyd et E. J. Candès. « A differential equation for modeling Neste-
rov’s accelerated gradient method : theory and insights ». Neural Information
Processing Systems 27 (2014), page(s): 2510-2518.
[106] P. Tseng. « A modified Forward-Backward splitting method for maximal
monotone mappings ». SIAM Journal Control and Optimization 38.(2) (2000),
page(s): 431-446. doi : 10.1137/S0363012998338806.
[107] Vapnik V. « Principles of risk minimization for learning theory Principles
of risk minimization for learning theory ». NIPS’91 : Proceedings of the 4th
International Conference on Neural Information Processing Systems (1991),
page(s): 831-838.
[108] S. Winkler. « Digital Video Quality : Vision Models and Metrics. » John
Wiley & Sons Ltd., West Sussex (2005).
[109] L. Xiao et T. Zhang. « A proximal stochastic gradient method with pro-
gressive variance reduction ». (2014). arXiv : 1403.4699.
178