Optimisation 2018
Optimisation 2018
Cité
Département de mathématiques
Analyse numérique: optimisation
Spécialité MACS de SupGalilée: Promotion
2017-2020.
Optimisation continue:
Mathématiques Financières-Actuariat
Modélisation mathématique
Centrale Marseille (Promotion 2019).
Master EDP de Aix-Marseille Université.
Olivier Lafitte1
1
SupGalilée, Institut Galilée, Université Paris XIII, LAGA [email protected]
2
Contents
1 Introduction et exemples 7
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Description du cours . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Euler-Legendre 21
2.1 Condition générale d’existence (suffisante) . . . . . . . . . . . . . 21
2.2 Condition d’Euler, condition de Legendre . . . . . . . . . . . . . 22
2.2.1 Dérivabilité au sens de Fréchet et au sens de Gâteaux . . 22
2.2.2 Deux espaces de Hilbert utiles dans la totalité de ce cours 24
2.2.3 Conditions necessaires d’optimalité. Conditions suffisantes
d’optimalité . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.3 Inéquation d’Euler dans un problème avec contraintes . . . . . . 27
2.4 Multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . . . . 28
2.4.1 Contraintes égalités . . . . . . . . . . . . . . . . . . . . . 29
2.4.2 Les contraintes inégalité . . . . . . . . . . . . . . . . . . . 32
2.4.3 L’inégalité de Hardy. . . . . . . . . . . . . . . . . . . . . . 36
2.4.4 Problème mixte . . . . . . . . . . . . . . . . . . . . . . . . 36
2.4.5 Le problème des entrepôts . . . . . . . . . . . . . . . . . . 40
2.4.6 Démonstration du lemme de Kantorovich . . . . . . . . . 42
2.4.7 Calcul de la constante optimale de Poincaré . . . . . . . . 43
4 Programme convexe 57
4.1 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.1.1 Compléments et extensions . . . . . . . . . . . . . . . . . 60
4.2 Minimisation de fonctionnelles convexes . . . . . . . . . . . . . . 62
3
4 CONTENTS
6 Approximation de solutions 85
6.0.1 Algorithme de relaxation . . . . . . . . . . . . . . . . . . 85
6.1 Algorithmes de descente . . . . . . . . . . . . . . . . . . . . . . . 88
6.2 Cas classiques d’algorithmes de descente . . . . . . . . . . . . . . 90
6.2.1 Pas optimal . . . . . . . . . . . . . . . . . . . . . . . . . . 90
6.2.2 Pas de Curry . . . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.3 Pas de Goldstein . . . . . . . . . . . . . . . . . . . . . . . 91
6.2.4 Pas de Wolfe . . . . . . . . . . . . . . . . . . . . . . . . . 92
6.3 Résultats de convergence . . . . . . . . . . . . . . . . . . . . . . . 93
6.4 Algorithmes de gradient . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.4.2 L’algorithme de gradient à pas optimal . . . . . . . . . . . 96
6.4.3 Algorithme de gradient à pas constant . . . . . . . . . . . 98
6.4.4 Taux de convergence de l’algorithme du gradient en di-
mension finie . . . . . . . . . . . . . . . . . . . . . . . . . 98
6.4.5 Algorithme de gradient réduit . . . . . . . . . . . . . . . . 102
6.5 Algorithmes de gradient conjugué . . . . . . . . . . . . . . . . . . 105
6.5.1 Exemple en dimension 2 . . . . . . . . . . . . . . . . . . . 105
6.5.2 Algorithme de directions conjuguées . . . . . . . . . . . . 106
6.5.3 Algorithme du gradient conjugué . . . . . . . . . . . . . . 109
6.5.4 Un exemple en dimension 3 . . . . . . . . . . . . . . . . . 115
6.6 Descente pseudo-conjugué . . . . . . . . . . . . . . . . . . . . . . 117
6.7 Méthode de Newton . . . . . . . . . . . . . . . . . . . . . . . . . 118
6.8 Algorithmes d’optimisation avec contraintes . . . . . . . . . . . . 123
6.8.1 Le gradient avec projection . . . . . . . . . . . . . . . . . 123
6.8.2 Pénalisation des contraintes . . . . . . . . . . . . . . . . . 125
6.8.3 Algorithme d’Uzawa . . . . . . . . . . . . . . . . . . . . . 127
8 Resume 139
8.1 Résultats d’existence . . . . . . . . . . . . . . . . . . . . . . . . . 139
8.1.1 Théorème de Weierstrass . . . . . . . . . . . . . . . . . . 139
8.1.2 Cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . 140
8.2 Rappels de calcul différentiel . . . . . . . . . . . . . . . . . . . . 140
8.2.1 Dérivées premières . . . . . . . . . . . . . . . . . . . . . . 141
8.2.2 Dérivées secondes . . . . . . . . . . . . . . . . . . . . . . . 141
8.2.3 Formules de Taylor . . . . . . . . . . . . . . . . . . . . . . 141
8.3 Caractérisation des extrema . . . . . . . . . . . . . . . . . . . . . 143
8.3.1 Equation d’Euler, cas général . . . . . . . . . . . . . . . . 143
8.3.2 Inéquation d’Euler, cas convexe . . . . . . . . . . . . . . . 143
8.3.3 Multiplicateurs de Lagrange, cas général . . . . . . . . . . 145
8.3.4 contraintes égalités . . . . . . . . . . . . . . . . . . . . . . 145
8.3.5 contraintes inégalités . . . . . . . . . . . . . . . . . . . . . 146
8.4 Lagrangien et point selle . . . . . . . . . . . . . . . . . . . . . . . 149
8.4.1 Point selle . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
8.4.2 Théorie de Kuhn et Tucker . . . . . . . . . . . . . . . . . 150
8.5 Méthodes de descente. Problèmes sans contraintes . . . . . . . . 151
8.5.1 Principe . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
8.5.2 Méthode de relaxation . . . . . . . . . . . . . . . . . . . . 152
8.5.3 Méthode du gradient . . . . . . . . . . . . . . . . . . . . . 152
8.6 Estimations et convergence dans le cas quadratique . . . . . . . . 153
8.6.1 Méthode à pas optimal . . . . . . . . . . . . . . . . . . . 153
8.6.2 Méthode de gradient à pas constant . . . . . . . . . . . . 154
8.7 Méthode du gradient conjugué . . . . . . . . . . . . . . . . . . . 154
8.7.1 Principe de la méthode . . . . . . . . . . . . . . . . . . . 154
8.7.2 Ecriture comme algorithme de descente . . . . . . . . . . 155
8.7.3 Analyse de convergence . . . . . . . . . . . . . . . . . . . 155
8.8 Méthodes pour les problèmes avec contraintes . . . . . . . . . . . 156
8.8.1 Méthode de gradient projeté à pas variable . . . . . . . . 156
8.8.2 Algorithme d’Uzawa . . . . . . . . . . . . . . . . . . . . . 157
6 CONTENTS
Chapter 1
Introduction et exemples
1.1 Introduction
Le but de ce cours est d’introduire quelques unes des méthodes de la théorie de
l’optimisation. La méthode employée dans ce cours consiste essentiellement à
présenter une suite (non exhaustive) d’exemple simples issu en majeure partie
de la physique et de l’économie pour mettre en valeur une question que l’on se
pose dans le cadre de l’optimisation: trouver la meilleure quantité ou le meilleur
choix pour un problème lié à la physique ou à l’économie. Ce cours présentera
peu de résultats (les théorèmes principaux sont peu nombreux). Nous avons
essayé de traiter explicitement ici des exemples modèles simples, qui peuvent
nous permettre d’introduire des notions et de pouvoir les généraliser.
Les théories liées à l’optimisation sont très variées. On rencontre par exem-
ple (et cela est le plus courant) des problèmes de minimisation sons contraintes,
des résolutions d’équations aux dérivées partielles sous forme variationnelle,
des problèmes de contrôle, des problèmes de commande. Elles ont en commun
la minimisation d’un critère, c’est-à-dire d’une fonction chargée de mesurer
le coût d’un problème, en fonction de variables dites d’état (caractérisant la
position d’une particule par exemple) et de variables dites de commande (qui
modélisent les paramètres par lesquels on peut agir sur un système). Nous
évoquerons ainsi dans le cours la notion de commande optimale, dans les cas
où, à partir de variables d’état x et de commandes u, on souhaite soit minimiser
un critère, soit atteindre un état fixe.
Un des atouts de l’optimisation est la facilité d’obtention d’algorithmes
numériques qui convergent, et nous en aborderons certains: algorithmes d’optimisation
sans contrainte, comme un algorithme où on recherche un optimum sur N vari-
ables en résolvant, à chaque étape, N algorithmes d’optimisation sur chaque
variable, des algorithmes dit de gradient (à pas fixe ou à pas optimal, c’est à
dire une généralisation de la méthode de Newton de recherche de zéros), des
algorithmes de minimisation avec contraintes, l’algorithme d’Uzawa.
Pour l’instant, nous allons donner une liste non exhaustive d’exemples,
provenant des références [2], [3], [1]. Certains pourront être résolus dans cette
introduction sans utiliser de théorèmes nouveaux, d’autres non, et nous voulons,
dans la suite de ce cours, pouvoir résoudre les problèmes abordés ici.
7
8 CHAPTER 1. INTRODUCTION ET EXEMPLES
Les exemples abordés dans cette introduction peuvent être lus après le cours
correspondant, ils sont faits pour motiver les théorèmes du cours d’optimisation
et de calcul des variations.
On peut, très sommairement, diviser les résultats en conditions nécessaires
et en conditions nécessaires et suffisantes d’optimalité. Par exemple, x2 est
minimum en x = 0, où sa dérivée s’annule, mais la dérivée de 1 − x2 est dans
le même cas, alors que 1 − x2 est maximum en x = 0. La condition “la dérivée
s’annule” est une condition nécessaire de minimum, mais n’est pas une condition
suffisante.
1.3 Exemples
1. Résolution d’un système matriciel.
Soit A une matrice symétrique N × N définie positive et b un vecteur de
IRN . La solution du système linéaire Ax = b est donnée par le point de
minimum suivant
1
inf (Ax, x) − (b, x)
x∈IRN 2
1 1 1 1 1
(A(x − x0 ), x − x0 ) = (Ax, x) − (b, x) − (Ax, x0 ) + (b, x0 ).
2 2 2 2 2
Comme (Ax, x0 ) = (x, t Ax0 ) = (x, Ax0 ) = (x, b) car A est symétrique
1 1 1
(Ax, x) − (b, x) = − (b, x0 ) + (A(x − x0 ), x − x0 ).
2 2 2
1.3. EXEMPLES 9
On
P diagonalise A qui est symétrique définie positive, on écrit x = x0 +
i yi ei , où les ei sont les vecteurs orthonormés qui diagonalisent A, alors
i=N
1 1 1X
(Ax, x) − (b, x) = − (b, x0 ) + λi yi2 .
2 2 2
i=1
L’expression ci-dessus est minimum lorsque tous les yi sont nuls, car tous
les λi sont strictement positifs, donc lorsque x = x0 . Le résultat est
démontré.
||v−u0 ||2 = ||v−p(u0 )||2 +||p(u0 )−u0 ||2 +2(v−p(u0 ), p(u0 )−u0 ) ≥ ||v−p(u0 )||2 .
(v − v0 , u0 − v0 ) ≤ 0, (v − p(u0 ), u0 − p(u0 )) ≤ 0.
Dans la première inégalité on considère v = p(u0 ) et dans la deuxième on
considère v = v0 . Alors
10 CHAPTER 1. INTRODUCTION ET EXEMPLES
(p(u0 ) − v0 , p(u0 ) − v0 ) ≤ 0
ce qui implique v0 = p(u0 ). Il y a unicité de la projection sur un convexe.
Ceci est la redémonstration du théorème de Hahn-Banach.
On résume dans
∀y ∈ K, (y − p(x), x − p(x)) ≤ 0.
inf J(y), a1 y1 + a2 y2 ≤ 0
1 a2 b2 a1 − b1 a2
inf (1 + 21 )y12 − y2
2 a2 a1
qui est atteint au point y2 = a1 b2 aa12 −b
+a2
1 a2
et donc y1 = −a2 b2 aa12 −b
+a2
1 a2
.
1 2 1 2
a1 b1 + a2 b2
(y1 , y2 ) = (b1 , b2 ) − (a1 , a2 ).
a21 + a22
Cette méthode n’est pas instructive, mais son résultat l’est: le minimum
est obtenu au point b + λa. Le réel λ est nul lorsque a.b = 0.
Distinguons les cas b.b = 0 et a.b 6= 0. Notons avant cela que le minimum
absolu de la fonctionnelle se situe au point b. Si b est dans la contrainte,
alors ce minimum absolu est atteint sur la contrainte, et donc le problème
inf J, a.y = 0
admet comme solution y = b, de même que le problème
inf J, a.y ≤ 0.
inf |f (x)|2 .
x∈IRM
(Av, v)
λ1 = inf (Av, v) = inf .
v∈IRN ,||v||=1 IRN −{0} (v, v)
1.3. EXEMPLES 13
X yi X yi X 1
= 1, yi ≥ 1∀i ⇒ 1 = ≥ .
ri ri ri
i i
P 1
Ainsi la condition 1 ≥ ri est nécessaire pour que le gain soit au moins
égal à la mise.
P 1
Réciproquement, on suppose 1 ≥ ri , et on veut yi pour tout i plus
grand que i. Le cas limite est obtenu pour tous les yi égaux, et cette
valeur commune est yi = P1 1 , ce qui impose de choisir xi = r1i P1 1 .
rp rp
Dans ce cas, le gain est P1 1 pour tout i; il est donc plus grand que 1.
rp
j=N
X i=M
X
vij ≥ 0, vij ≤ si , vij ≥ rj
j=1 i=1
P
et le coût de livraison est i,j cij vij . On cherche l’inf de cette fonction.
Notons tout d’abord que, si l’on désigne par cj le min pour i = 1..M des
cij , on trouve
X j=N
X i=M
X X
cij vij ≥ cj ( vij ) ≥ cj rj .
i,j j=1 i=1 j
14 CHAPTER 1. INTRODUCTION ET EXEMPLES
Z l Z x1 1
ρg (y(x(s)) − y1 )ds = −ρgy1 l + ρg y(x)(1 + (y 0 (x))2 ) 2 dx.
0 x0
L’énergie totale, qui est constante, fait intervenir la vitesse, qui est donc
nulle. On a donc le problème
Z x1 1
inf y(x)(1 + (y 0 (x))2 ) 2 dx
y∈C 0 x0
sous les contraintes
Z x1
1
(1 + (y 0 (x))2 ) 2 dx = l, y(x0 ) = y0 , y(x1 ) = y1 .
x0
1
x1
(1 + (v 0 (x))2 ) 2
Z
inf dx.
x0 c(x, v(x))
Lorsque on veut par exemple évaluer le rayon entre deux milieux de vitesse
c1 et c2 , tels que c(x, y) = c1 1x>0 + c2 1x>0 , on a donc, appliquant ce qui
est écrit ci-dessus à trouver le lieu de
1 1
0
(1 + (v 0 (x))2 ) 2 x1
(1 + (v 0 (x))2 ) 2
Z Z
inf[ dx + dx].
x0 c1 0 c2
Z
1
U2 (v) = k |v|2 dx
2 Ω
Z
U3 (v) = − f (x)v(x)dx
Ω
qui sont respectivement l’énergie potentielle de déformation, l’énergie po-
tentielle élastique, l’énergie d’une force extérieure constante dans le temps.
On étudie deux fonctionnelles J1 = U1 + U2 + U3 et J2 = U1 + U3 . On
écrira quatre types de problèmes:
J2 (u + φ) ≥ J2 (u).
16 CHAPTER 1. INTRODUCTION ET EXEMPLES
−λ∆u = f
1 2 1 2
R R R R
J2 (v) − J2 (u) = 2 λ R (∇v) dx − f vdx −
R 2 λ (∇u)R dx + f udx
1 2 − λ (∇u)2 dx + f udx
R R
= 2 λ (∇v − ∇u) dx + λ ∇u∇v − f vdx
qui permet de définir ∂n u ∈ L2 (∂Ω) pour u ∈ H01 (Ω) tel que ∆u ∈ L2 (Ω)
et v ∈ H 1 (Ω)0 comme le résultat d’un théorème de Riesz. Pour
R cela, on
∞ (Ω), v → L(v) =
introduit la fonctionnelle, définie sur C 0 Ω ∇u∇v +
2
R
Ω ∆u.vdx, uniquement défini pour ∆u dans L (Ω). Cette fonctionnelle
est continue pour la topologie de C0∞ (Ω), on a:
Proposition 1.1 Si u est une solution qui minimise J1 dans H 1 (Ω) avec
u|Γ ≥ 0, alors
−λ∆u + ku = f dans L2 (Ω), et ∂n u = 0 sur u|Γ > 0 et ∂n u ≥ 0 sur
u|Γ = 0.
−λ∆u + ku = f.
Z
(c − 1)2 [U1 (u) + U2 (u)] + (c − 1) (λ(∇u)2 + k(u)2 − f u)dx ≥ 0.
Ω
n
R 1 R k+1
2 02n x2 = 6n1 3 et k n (|u0 (x)| − 1)2 dx = 0. Ainsi
n
1
J(un ) =
6n2
et inf J = 0, alors qu’il n’existe pas de u tel que J(u) = inf J.
1.3. EXEMPLES 19
dy(v)
(t) = Ay(v)(t) + Bv + f (t)
dt
RT RT
J(v) = (v(t), v(t))dt + 0 (Q(y(v)(t) − g(t)), y(v)(t) − g(t))dt
0
+(R(y(v)(T )) − g(T ), y(v)(T ) − g(T ))
On note pour l’instant que y(v) peut être calculée, par exemple à l’aide
de y(0) puis de l’exponentielle de A dans une base où par exemple A
est diagonalisable, mais cela ne sera pas de grande aide pour calculer et
minimiser le critère.
d 1 dui
− ( ) = fi (x), ∀x, ui (0) = ui (1) = 0 (1.3.2)
dx a(x) dx
XZ 1
inf |ui (x) − ūi (x)|2 dx. (1.3.3)
a∈A 0
i
Z x Z x
dui d
= CA0 (x)+A0 (x) fi (t)dt = (CA(x)+A(x) fi (t)dt)−A(x)fi (x),
dx 0 dx 0
soit
Z x Z x
ui (x) = CA(x) + A(x) fi (t)dt − A(t)fi (t)dt
0 0
en ayant utilisé ui (0) = 0. On identifie C grâce à ui (1) = 0, ce qui donne
Z 1 Z 1 Z x
A(x)
ui (x) = ( A(t)fi (t)dt−A(1) fi (t)dt)+ (A(x)−A(t))fi (t)dt.
A(1) 0 0 0
Théorème 2.1 Soit K ⊂ IRN , soit J une fonctionnelle continue sur Ω con-
tenant K, et K fermé.
Si K est compact, ou si J est ∞ à l’∞ (c’est-à-dire, pour toute suite vn
telle que |vn | → +∞, J(vn ) → +∞), alors J a au moins un minimum sur K.
On peut extraire de toute suite minimisante sur K une sous-suite con-
vergeant vers un point de minimum sur K.
21
22 CHAPTER 2. EULER-LEGENDRE
condition à l’infini, mais il n’y a pourtant pas de minimum car dans un espace
de dimension infinie, un fermé borné n’est pas necessairement compact.
Il s’agit maintenant d’être capable, comme dans les exemples traités précédemment,
de calculer les solutions. Nous allons faire cela, en écrivant des conditions très
anciennes, nécessaires pour certaines, suffisantes pour d’autres.
Définition 2.1 Lorsque, pour tout w, la limite limε→0 1ε [J(u + εw) − J(u)]
existe, on la note J 0 (u; w) et on l’appelle dérivée directionnelle de J en u dans
la direction w, qui est une fonction définie de V × V dans IR, homogène de
degré 1 dans la variable w.
Lorsque, de plus, la fonction w → J 0 (u; w) est une fonction linéaire con-
tinue, alors il existe, par le théorème de Riesz, un élément de l’espace de Hilbert
V , que l’on appelle la dérivée de Gâteaux de J en u et que l’on note J 0 (u). On
notera souvent de la même façon la forme linéaire et son représentant dans le
produit scalaire, soit (J 0 (u), w) = J 0 (u; w).
On peut aussi définir la dérivée seconde J”(u) si elle existe, lorsque la limite
1
lim [J 0 (u + δw1 ; w2 ) − J 0 (u; w2 )]
δ→0 δ
2.2. CONDITION D’EULER, CONDITION DE LEGENDRE 23
existe pour tout (w1 , w2 ) et est une forme bilinéaire continue sur V × V . La
limite est alors (J”(u)w1 , w2 ) par représentation des formes bilinéaires contin-
ues.
Lorsque J est dérivable au sens de Fréchet, elle est dérivable au sens de Gâteaux,
mais la réciproque est fausse, car l’écriture de la dérivabilité au sens de Fréchet
correspond à ε(v)
||v|| tend vers 0, alors que la dérivabilité au sens de Gateaux
correspond à ε(λw)
λ tend vers 0 lorsque λ tend vers 0 et on perd l’uniformité de
w.
On peut alors écrire des formules de Taylor sur v a l’ordre 2
1
J(u + tw) = J(u) + t(J 0 (u), w) + t2 (J”(u)w, w) + o(t2 ). (2.2.2)
2
Lorsque J” est continue, on peut écrire la formule de Taylor avec reste
intégral
Z 1
0 2
J(u + tw) = J(u) + t(J (u), w) + t (1 − x)(J”(u + xtw)w, w)dx. (2.2.3)
0
φ(t + h) − φ(t)
→ (J 0 (u + tw), w)
h
ainsi φ0 (t) = (J 0 (u + tw), w).
24 CHAPTER 2. EULER-LEGENDRE
0 0 0 0 (u),w)
On voit alors que φ (t)−φ
t
(0)
= (J (u+tw),w)−(J
t tend vers φ”(0) = (J”(u)w, w).
Ainsi on peut écrire la formule de Taylor
t2
φ(t) = φ(0) + tφ0 (0) + φ”(0) + o(t2 )
2
et on a obtenu la formule de Taylor pour une fonction différentiable, qui admet
une dérivée seconde au sens de Gateaux.
D’autre part, si J est deux fois différentiable au sens de Fréchet dans un
voisinage de u, on a
Définition 2.3 On appelle espace de Sobolev H 1 ([a, b]), où a et b sont deux
réels, a < b, le complété pour la norme
Z b
1
||u||H 1 ([a,b]) = ( ((u0 (x))2 + (u(x))2 )dx) 2
a
de l’espace C 1 (Ω).
2.2. CONDITION D’EULER, CONDITION DE LEGENDRE 25
que cet espace peut aussi s’écrire H 1 ([a, b]) = {u ∈ L2 ([a, b]), u0 ∈ L2 ([a, b])}.
Dans l’écriture ci-dessus, on peut remarquer qu’une fonction de L2 ([a, b]) n’est
pas forcément définie en tout point (elle n’est définie que presque partout), donc
pour la définition de la dérivée il est nécessaire de passer par une autre notion,
la dérivée faible:
de l’espace C01 (Ω) des fonctions de C 1 (Ω) qui sont nulles sur le bord de Ω ainsi
que leurs dérivées.
Par extension, on dira que la trace des éléments de H01 (Ω) sur le bord est nulle.
Un espace de Hilbert plus grand HΓ1 (Ω) peut aussi être défini par u nulle sur
une partie Γ du bord Ω.
∀w ∈ V, (J”(u)w, w) ≥ 0.
(condition de Legendre)
Démonstration:
Si u est un point d’optimum de J, alors, pour tout v ∈ V on a
J(u + v) ≥ J(u).
∀v ∈ V, Lu (v) + o(v) ≥ 0.
t2
J(u + tw) = J(u) + (J”(u)w, w) + o(t2 )
2
et l’inégalité J(u + tw) ≥ J(u) conduit à (J”(u)w, w) ≥ 0 pour tout w. Le
théorème est démontré.
Ce théorème est complété par une écriture de conditions suffisantes, valables
pour un minimum local
J 0 (u) = 0
et pour tout ũ dans un voisinage V0 de u0 , on ait la condition (J”(ũ)w, w) ≥ 0.
(condition forte de Legendre)
On note que les deux ensembles ainsi définis sont des cônes, et que K̇(u) ⊂
K(u).
On a alors les conditions nécessaires suivantes sur un minimum de la fonc-
tionnelle sous contraintes:
∀w ∈ K(u), (J 0 (u), w) ≥ 0.
Si J est dérivable au sens de Gâteaux, il faut que
∀w ∈ K̇(u), (J 0 (u), w) ≥ 0.
1
[J(u + en wn ) − J(u)] ≥ 0 ∀n
en
puisque en ≥ 0. Ainsi, en passant à la limite dans l’égalité de définition de
la dérivée de Fréchet, on obtient e1n [J(u + en wn ) − J(u) − (J 0 (u), en wn )] → 0,
ainsi, écrivant (J 0 (u), wn ) − (J 0 (u), w) = (J 0 (u), wn − w) → 0, on a
(J 0 (u), w) ≥ 0.
Pour le deuxième, on vérifie que J(u + εw) − J(u) ≥ 0, ainsi, en divisant
par ε et en faisant tendre ε vers 0 pour w ∈ K̇(u), on trouve
∀w ∈ K̇(u), (J 0 (u), w) ≥ 0.
φ(λ + h, ε) − φ(λ, ε) 1
= (F (u+εw+ελF 0 (u)+εhF 0 (u))−F (u+εw+ελF 0 (u)))
h εh
donc
φ(0, ε)
λ=− (1 + O(ε)),
||F 0 (u)||2
d’où une expression de λ(ε) (dont on a montré l’existence et l’unicité ci-dessus).
Ainsi on a trouvé wε = w + λ(ε)F 0 (u) tel que F (u + εwε ) = 0 et wε → w. La
direction w est une direction admissible. Lorsque F 0 (u) = 0, w est quelconque,
2.4. MULTIPLICATEURS DE LAGRANGE 31
mais cela n’assure pas l’existence d’un w non nul qui soit une direction ad-
missible. Par exemple, F (x) = x2 conduit, dans la définition, à écrire le cône
des directions admissibles à {0} dans IR, qui correspond à {0}, car dans ce cas
0 + en wn = 0 ce qui implique wn = 0, et non pas tout l’axe réel.
Lemme 2.1 Dans le cas F 0 (u) 6= 0, le cône K(u) associé à u tel que F (u) = 0
est l’ensemble des w ∈ V tels que (F 0 (u), w) = 0.
Définition 2.9 Soit K = {u, F1 (u) = 0, F2 (u) = 0, ...Fm (u) = 0}. Lorsque les
vecteurs (F10 (u), F20 (u), ..Fm
0 (u)) sont linéairement indépendants, on dit que les
Théorème 2.5 Pour que u tel que (Fj0 (u))j forme une famille libre (on dit que
les contraintes Fj (v), 1 ≤ j ≤ m sont régulières en u), soit solution de
(2.2.5), il faut qu’il existe m réels λ1 , ...λm tels que
32 CHAPTER 2. EULER-LEGENDRE
∀w ∈ K(u), (J 0 (u), w) ≥ 0.
Comme K(u) est un espace vectoriel, −w ∈ K(u) lorsque w ∈ K(u), ce qui se
traduit par
∀w ∈ K(u), (J 0 (u), w) = 0.
Ainsi J 0 (u) est dans l’espace vectoriel orthogonal à F ⊥ , c’est-à-dire F , et
l’égalité du théorème est vraie.
On peut aussi le vérifier comme suit. Il existe des P
scalaires λj et un vecteur
r, orthogonal à tous les Fj (u), tels que J (u) = − m
0 0 0
j=1 λj Fj (u) + r. Alors
0
r ∈ K(u) et (J (u), r) = 0, ce qui s’écrit (r, r) = 0 soit r = 0.
ne peut trouver un w0 que dans le cas où il existe un couple (j1 , j2 ) tels que
(Fj01 (u), w0 ) = (Fj02 (u), w0 ) = 0, on pourrait se trouver dans la situation où les
deux hypersurfaces Fj1 ≤ 0 et Fj2 ≤ 0 sont tangentes en u, de vecteur normal
w0 , et (par exemple) de concavité stricte opposée. Dans ce cas, l’intersection
des contraintes Fj1 ≤ 0 et Fj2 ≤ 0 est réduite à {u}, et on ne peut plus parler
de direction admissible.
Une condition pour que l’ensemble des directions admissibles soit non vide
est alors la condition:
Il existe w0 tel que, ∀j, (Fj0 (u), w0 ) < 0.
Cette condition est peu utilisable, car trop restrictive; en particulier une con-
trainte affine pourra donner une direction admissible avec uniquement l’égalité.
On utilise alors plutôt la condition suivante:
Il existe w0 tel que ∀j, (Fj0 (u), w0 ) < 0 (contraintes non affines) et (Fj0 (u), w0 ) =
0 si la contrainte est affine, car on sait que dans ce cas l’intersection entre le
demi hyperplan défini par la contrainte affine et les autres conditions est non
vide.
Enfin, on élimine grâce à cela la condition d’indépendance des (Fj0 (u)) que
l’on avait utilisé pour caractériser les directions admissibles.
Cette analyse induit une définition de contraintes qualifiées, qui est une hy-
pothèse technique mais qui est l’hypothèse la plus classique en théorie des mul-
tiplicateurs de Lagrange:
Définition 2.11 On dit que les contraintes inégalités {Fj (u) ≤ 0} sont quali-
fiables en u si
Théorème 2.6 Sous l’hypothèse que J est dérivable, que les Fj sont dérivables,
et que, en u, les contraintes sont qualifiables, pour que u soit une solution de
(2.2.5), il faut qu’il existe λ1 , ...λm ≥ 0 tels que λj = 0 pour j ∈ {1, .., m}−I(u)
et
i=m
X
0
J (u) + λi Fi0 (u) = 0.
i=1
Le théorème 2.6 est une conséquence simple du lemme suivant, dit de Farkas,
et de la représentation des directions admissibles du lemme 2.3. On applique
alors le théorème 2.4 pour en déduire l’existence des multiplicateurs de Lagrange
positifs.
X
pour tout v ∈ K, (p, v) ≥ 0 on a ∃(λ1 , ...λm ) ∈ (IR+ )m , p = − λ i ai .
P
On définit B = {− λi ai , 1 ≤ i ≤ m, λi ≥ 0∀i}. Nous démontrerons que B
est un convexe fermé. Admettons le pour l’instant. On peut alors appliquer la
notion de projection sur un convexe fermé non vide. On suppose donc que p0
vérifie les hypothèses du lemme de Farkas et que p0 n’appartient pas à B. On
montre que la projection p̃ de p0 sur B est égale à p0 , d’où contradiction. On
trouve, de ||p0 − p̃||2 ≤ ||p0 − w||2 , w ∈ B, que ∀w ∈ B, (p̃ − p0 , w − p̃) ≤ 0.
Dans cette inégalité, on choisit alors w = −λai et on fait tendre λ vers +∞. Il
reste donc (ai , p0 − p̃) ≥ 0 pour tout i. Ceci implique que p̃ − p0 est dans K.
De l’inégalité 0 ≤ (p0 , p̃ − p0 ) = −|p0 − p̃|2 + (p0 − p̃, 0 − p̃) ≤ −|p0 − p̃|2 (car
0 ∈ B) on déduit que p0 = p̃. On a montré que p0 ∈ B, contradiction.
Il reste à démontrer que B est fermé convexe. Il est convexe de manière
évidente (on considère 0 ≤ µ ≤ 1, alors µλ1i + (1 − µ)λ2i ≥ 0, et donc il existe
une représentation de µv1 + (1 − µ)v2 qui soit une combinaison linéaire à coef-
ficients négatifs). En revanche le caractère fermé est plus difficile à obtenir. La
2.4. MULTIPLICATEURS DE LAGRANGE 35
preuve suit:
Si la famille (ai ) est libre, la matrice (ai .aj ) est symétrique définie positive.
On note ||a|| le max P des normes des ai et α la plus petite valeur propre de la
matrice. On obtient λi ai .aj = −v.aj , donc il vient maxi |λi | ≤ α−1 ||v||.||a||.
On considère alors une suite vn d’éléments de B qui converge. On note v sa
limite et on souhaite montrer que cette limite est dans B.
On peut identifier les λni associés à chaque vn , et les suites λni sont bornées.
Quitte à faire des extractions de suite en cascade, il existe une sous-suite con-
ψ(n) P
vergente λi , qui converge vers des valeurs positives λi , donc v = − λi ai .
La limite est donc dans B.
Deuxième
P cas, si la famille est linéairement dépendante, il existe µ1 , ..µm tels
que µi ai = 0 (avec au moins
P un des coefficients qui est positif), et donc un
élément de B s’écrit v = − (λi +tµi )ai . Il faut montrer que pour une valeur de
t ≤ 0, cette somme est une combinaison à coefficients positifs de m − 1 termes,
et on se sera ramené à une famille avec moins d’éléments pour tout t. Pour
t = 0, tous les coefficients sont positifs ou nuls, donc de deux choses l’une: ou
bien µi1 ≤ 0, auquel cas µi1 t ≥ 0 et le coefficient correspondant ne s’annulera
λ
pas si λi1 6= 0, ou bien µi1 > 0, ce qui implique que t = − µii1 est une valeur
1
où le coefficient s’annule. On prend alors t0 = mini,µi >0 µλii et la combinaison
précédente a un coefficient qui s’annule pour t = −t0 . Cette construction est
valable pour chaque élément de B.
On considère alors une suite xn d’éléments de B, suite de Cauchy dans
l’espace engendré par les ai , espace vectoriel de dimension finie. Elle s’écrit
− P λni ai . Par P
P
la construction ci-dessus, pour chaque n, il existe i(n) tel que
− λni ai = − i6=i(n) λ̃ni ai . On a donc enlevé chaque fois un élément de la
famille (ai ). On note Ii = {n, i(n) = i}. L’union des Ii est l’ensemble des
entiers naturels, donc il existe au moins un i0 tel que Ii est infini, soit Ii =
φ(n)
{φ(m), m = 0, 1.. + ∞}. La suite extraite xφ(n) = − i6=i0 λ̃i ai est une suite
P
qui correspond à la famille (ai )i6=i0 . Si cette famille est libre, on s’est ramené au
cas précédent, et la suite extraite xφ(n) converge vers un élément de B. Comme
la suite est de Cauchy, elle converge vers x et la limite de toute suite extraite
est x.
Si cette famille est liée, on reprend l’argument avec la suite xφ(n) . Comme
la famille n’est pas identiquement nulle (sinon B est réduit à {0} et on n’a rien
à démontrer), alors au bout d’un nombre fini d’itérations, on aboutit à une
famille libre (aj ) et la démonstration est finie puisque la limite est dans B pour
cette suite extraite.
On a donc montré que B est fermé, donc on peut utiliser le théorème de
projection sur un convexe fermé.
36 CHAPTER 2. EULER-LEGENDRE
K(u) = {w, (Fj0 (u), w) = 0, 1 ≤ j ≤ m} = {w, (Fj0 (u), w) ≤ 0, (−Fj0 (u), w) ≤ 0, 1 ≤ j ≤ m}.
Théorème 2.7 Nous considérons les points u de K tels que la propriété suiv-
ante soit vérifiée (contraintes mixtes qualifiées):
Les contraintes égalités sont régulières en u, et les contraintes inégalité sont
2.4. MULTIPLICATEURS DE LAGRANGE 37
qualifiées en u, où le vecteur de qualification w0 est dans l’ensemble (V ect(F10 (u), ..., Fm
0 (u)))⊥ .
Pour que u soit minimum de J sur K, il faut qu’il existe λ1 , ..., λm , λm+1 , ..., λm+p ,
∀i ∈ {1, ..., p}, λm+i ≥ 0 tel que
m+p
X
J 0 (u) + λj Fj0 (u) = 0
j=1
Dans le crochet, le premier terme est strictement négatif et le deuxième tend vers
0 si (t, δ) tend vers 0. Il s’agit de montrer précisément ce résultat. Il s’appuie sur
∂φ
φj (0, δ, 0) = 0 ainsi que sur ∂δj (t, δ, x) = (Fj0 (u + tw + t xk Fj0 (u) + tδw0 ), w0 ).
P
∂φj
On en déduit que ∂δ (0, δ, 0) = 0. Donc, considérant l’identité
En excluant de notre propos les contraintes affines, nous supposons donc que
les contraintes Fm+p sont qualifiées, la direction de qualification étant w0 dans
F ⊥ . Nous allons trouver une direction w dans F ⊥ pour laquelle Gp forment des
contraintes qualifiées. On sait d’autre part que les identités, pour 1 ≤ j ≤ m,
Fj (u(r)) = 0
0
P
où u(r) = π(u0 ) + r + k sk (r)Fk (u) impliquent les relations
X
∀w ∈ F ⊥ , ∀j, 1 ≤ j ≤ m, (Fj0 (u(r)), Fk0 (u))(s0k (r), w) + (Fj0 (u(r)), w) = 0.
k
Pour r = 0, on vérifie que (Fj0 (u(r)), w) = (Fj0 (u), w) = 0, donc nous avons
l’égalité
X
∀w ∈ F ⊥ , ∀j, 1 ≤ j ≤ m, (Fj0 (u), Fk0 (u))(s0k (0), w) = 0.
k
Comme les contraintes sont régulières, le système ci-dessus, où les inconnues
sont (s0k (0), w), est inversible, homogène, donc sa solution est la solution nulle.
On trouve donc
car (s0k (0), w) = 0. Ainsi, on trouve que (G0p (0), w0 ) < 0. Les contraintes Gp
sont alors qualifiables en 0.
On peut alors appliquer le théorème des multiplicateurs de Lagrange: il existe
(λ1 , ..., λq ) positifs ou nuls tels que
X
J˜0 (0) + λp G0p (0) = 0. (2.4.6)
p
On contrôle aussi que si on note F̃j (r) = Fj (u(r)), comme cette fonction est
identiquement nulle, la dérivée est nulle donc elle n’intervient pas dans l’écriture
de la relation des multiplicateurs de Lagrange. En revanche, si on veut revenir
aux fonctions Fj et Fm+p et exprimer le résultat (2.4.6) avec ces fonctions
ainsi qu’avec J, il est nécessaire d’introduire des multiplicateurs de Lagrange
supplémentaires comme nous allons le voir dans l’exemple qui suit.
Le problème correspondant en dimension finie fait aussi l’objet de la section
40 CHAPTER 2. EULER-LEGENDRE
6.4.5 dans la partie sur les algorithmes. Nous allons réécrire le problème dans
le cas où l’espace de base est IR3 , la condition de type égalité conduit à z =
φ(x, y), ou encore, notant F la constante, F (x, y, φ(x, y)) = 0. La fonctionnelle
à minimiser est J(x, y, z), la contrainte inégalité est h(x, y, z) ≤ 0. On réécrit
donc le problème sous la forme
∂z J + λ∂z h + µ∂z F = 0
ou encore
(∂z J + λ∂z h)∂x φ = µ∂x F
On remplace cette identité dans l’égalité (2.4.7) pour obtenir
∂x J + λ∂x h + µ∂x F = 0.
On a de même
∂y J + λ∂y h + µ∂y F = 0
d’où l’égalité des multiplicateurs de Lagrange pour un problème mixte.
Dans le premier cas, tous les µij sont nuls. Le système des multiplicateurs de
Lagrange (en supposant µ1 et µ2 non nuls, soit les égalités v11 + v12 = s1 ainsi
que v21 + v22 = s2 , ce qui donne s1 + s2 = r1 + r2 ) est
c11 + λ1 − µ1 =0
c12 + λ2 − µ1 =0
c + λ1 − µ2 =0
21
c22 + λ2 − µ2 =0
Ce système implique alors la condition c11 + c22 = c12 + c21 . Si cette condition
n’est pas vérifiée, on sait que l’hypothèse du premier cas est impossible.
Si cette condition est vérifiée, on écrit c12 − c22 = c11 − c21 , et on regarde la
fonction coût
φ = c11 v11 + c12 v12 + c21 v21 + c22 v22 = c21 r1 + c22 r2 + (c11 − c21 )v11 + (c12 − c22 )v12
= c21 r1 + c22 r2 + (c11 − c21 )(v11 + v12 ) = c11 r1 + c12 r2 + (c22 − c12 )(v21 + v22 )
Dans le cas où les deux conditions sont réalisées il vient que la fonction coût est
constante et vaut c11 r1 + c12 r2 + (c22 − c12 )s2 . Si on a l’égalité v11 + v12 = s1
et v21 + v22 > s2 . Alors µ2 = 0 et on a le système
c11 + λ1 − µ1 = 0
c12 + λ2 − µ1 = 0
c + λ1 = 0
21
c22 + λ2 = 0
On suppose pour simplifier que toutes les valeurs propres sont distinctes,
λ1 < λ2 < ... < λm .
On voit que l’égalité du multiplicateur de Lagrange s’écrit
X X
yj [λ−1
j ( λ p yp
2
) + λj ( λ−1 2
p yp ) + µ] = 0∀j.
λq λp
(λp yp2 + λq yq2 )(λ−1 2 −1 2 4 4
p yp + λq yq ) = yp + yq + ( + )yp2 yq2 .
λp λq
λq λp λq λp
f ”(x) = 2(2 − + ) = 2( − 1)( − 1)
λp λq λp λq
et comme si λp /λq est plus grand que 1, λq /λp est plus petit que 1 donc le
produit est négatif.
Ce calcul est aussi celui qui prouve que la valeur 1 est plus petite que
1 1 λq λp
2 + 4 ( λp + λq ).
infR |∇u|2 dx
Ω
2 dx
= 1 et u dans H01 (Ω). En effet, si on considère
R
sous la contrainte Ω |u|
1
la fonction v = uk , avec k = ( Ω |u|2 dx) 2 , elle Rvérifie Ω v 2 dx = 1. On
R R
donc −∆u + λu = 0 dans D0 (Ω), donc λ est une valeur propre du Laplacien
avec condition de Dirichlet sur Ω. On a alors, pour ce u,
Z Z Z
J∗ (u) = (∇u) dx = − ∆uudx = −λ u2 dx = −λ.
2
Ω Ω
45
46 CHAPTER 3. CALCUL DES VARIATIONS
∂y
η(x, ε) = (x, ε)
∂ε
(ce qui explique le nom de calcul des variations). On se ramène donc à une
fonction de ε:
Une condition nécessaire pour que y0 soit une solution du problème de min-
imisation est la suivante:
J 0 (0) = 0.
Z x2
(∂y f (x, y0 (x), y00 (x)).η(x, 0) + ∂y0 f (x, y0 (x), y00 (x)).η 0 (x, 0))dx = 0. (3.2.1)
x1
2
Delenda Cartago est! (Caton)
3
Methodus inveniendi lineas curvas maximi minimive proprietate gaudentes, sive solutio
problematis isoperimetrici latissimo sensu accepti
3.2. PROBLÈMES ISOPÉRIMÉTRIQUES 47
Notons dans cette égalité comme dans l’écriture de f que l’on a considéré le
terme y 0 comme une variable indépendante de y et non comme la dérivée de y
par rapport à x.
On utilise alors la relation y(x1 , ε) = y1 , de sorte que, en dérivant par
rapport à ε, η(x1 , ε) = 0. De même, η(x2 , ε) = 0. On peut alors utiliser ces
conditions de bord pour effectuer une intégration par parties:
Z x2 Z x2
d
∂y0 f (x, y0 (x), y00 (x)).η 0 (x, 0)dx =− (∂y0 f (x, y0 (x), y00 (x))).η(x, 0)dx.
x1 x1 dx
En écrivant l’égalité (3.2.1) et en vérifiant qu’elle est vraie quelle que soit
la fonction η(x, 0) nulle en x1 et en x2 (pour s’en convaincre, il suffit d’écrire
y(x, ε) = y0 (x) + εg(x), où g est nulle aux deux bouts), on trouve l’équation
d’Euler-Lagrange:
d ∂f ∂f
( 0 (x, y0 (x), y00 (x))) = (x, y0 (x), y00 (x)). (3.2.2)
dx ∂y ∂y
Bien sûr, cette équation s’obtient facilement en utilisant le théorème 2.4
démontré dans le chapitre 2. Nous allons l’établir de deux façons distinctes.
Avant cela, cependant, donnons un résultat important lorsque f ne dépend que
des variables de position y et y 0 :
Lemme 3.1 Lorsque f ne dépend pas de x, une solution des équations d’Euler
vérifie l’égalité suivante:
d
y00 ∂y0 f (y0 , y00 ) − f (y0 , y00 )) = 0.
dx
Cette égalité donne une intégrale première.
Z x2
∂f d ∂f
1
∀w ∈ H ([x0 , x1 ]), ( (x, y0 , y00 ) − ( (x, y0 (x), y00 (x))))w(x)dx ≥ 0
x1 ∂y dx ∂y 0
Le cône des directions admissibles est un espace vectoriel, donc cette inégalité
devient une égalité, et cette égalité entraine l’équation d’Euler-Lagrange.
D’autre part, pour w ∈ H 1 ([x1 , x2 ]), une intégration par parties conduit à
Rx
(J 0 (y0 ), w) = x12 ( ∂f 0 d ∂f 0
∂y (x, y0 , y0 ) − dx ( ∂y 0 (x, y0 (x), y0 (x))))w(x)dx
∂f 0 ∂f 0
+ ∂y 0 (x2 , y0 (x2 ), y0 (x2 ))w(x2 ) − ∂y 0 (x1 , y0 (x1 ), y0 (x1 ))w(x1 ).
J 0 (y0 ) = ∂f 0 d ∂f 0
∂y (x, y0 , y0 ) − dx [ ∂y 0 (x, y0 (x), y0 (x))]
∂f 0 ∂f 0
+ ∂y 0 (x2 , y0 (x2 ), y0 (x2 ))δx2 − ∂y 0 (x1 , y0 (x1 ), y0 (x1 ))δx1 .
∂f ∂f
λ1 = (x1 , y0 (x1 ), y00 (x1 )), λ2 = − 0 (x2 , y0 (x2 ), y00 (x2 )). (3.2.3)
∂y 0 ∂y
Cette égalité aura une très jolie interprétation ci-dessous.
R x2
sous les contraintes x1 g(x, y, y 0 )dx = C, y(x1 ) = y1 , y(x2 ) = y2 . Le cas modèle
1
est le problème de Didon: f (x, y, y 0 ) = y et g(x, y, y 0 ) = (1 + (y 0 )2 ) 2 .
Une méthode usuelle classique consiste Rà employer une double variation,
x
c’est-à-dire à tenir compte de la contrainte x12 g(x, y, y 0 )dx = C en ajoutant à
une première variation y0 + εη1 une deuxième variation faite pour la contrebal-
ancer:
y0 + ε1 η1 + ε2 η2 .
On introduit dans η1 et η2 les contraintes
R x2 d’extrémité sous laRforme ηi (xj ) =
x
0, i, j = 1, 2.On écrit alors que I = x1 f (x, y, y 0 )dx et C = x12 g(x, y, y 0 )dx
sont deux fonctions de ε1 et de ε2 , et on forme
!
∂I ∂I
∆(ε1 , ε2 ) = ∂ε1 ∂ε2 .
∂C ∂C
∂ε1 ∂ε2
R x2 R x2 !
d d
(∂ f − dx (∂y f ))η1 dx
0 (∂ f − dx (∂y f ))η2 dx
0
∆(ε1 , ε2 ) = Rxx12 y d
Rxx12 y d .
x1 (∂y g − dx (∂y g))η1 dx x1 (∂y g − dx (∂y g))η2 dx
0 0
Rx d
Rx
On note les deux réels λ1 = x12 (∂y f − dx (∂y0 f ))η2 dx et λ2 = x12 (∂y g −
d
dx (∂y g))η2 dx. Si les deux réels sont nuls pour tous les choix de η2 , cela veut
0
dire que f et g vérifient tous deux l’équation d’Euler. Nous verrons ce cas plus
tard. Sinon, on note, pour un η2 donné non nul, que, pour tout η1 :
Z x2
d d
[λ2 (∂y f − (∂y0 f )) − λ1 (∂y g − (∂y0 g))]η1 dx = 0
x1 dx dx
ce qui donne l’existence d’un h = f + λg tel que h vérifie l’équation d’Euler.
Lorsque f et g vérifient toutes deux l’équation d’Euler, alors cette équation est
vérifiée quel que soit λ.
A l’évidence, cette méthode est celle que l’on emploie pour les multiplica-
teurs de Lagrange. On écrit ainsi l’existence de λ, λ1 , λ2 tels que
d y0
1= (λ )
dx (1 + (y 0 )2 ) 21
soit encore
y0 x
1 = .
(1 + (y 0 )2 ) 2 λ
On obtient y 0 = ± x
1 , dont la solution s’écrit
(λ2 −x2 ) 2
1
y(x) = y(x1 ) ± (λ2 − x2 ) 2 .
1 1
On suppose y1 < y2 , donc y(x) = y1 +(λ2 −x21 ) 2 −(λ2 −x2 ) 2 car y(x1 ) = y1 .
1 1
On identifie λ en écrivant y(x2 ) = y2 , soit (λ − x22 ) 2 − (λ − x21 ) 2 = y1 − y2 , ce qui
1 1
permet de trouver les valeurs de (λ2 −x22 ) 2 et (λ2 −x21 ) 2 . Lorsque y1 = y2 = 0, on
trouve un demi-cercle de rayon R et l’aire est πR2 , correspondant à R = 1000S 2π .
d ∂f ∂f
( 0 (x, y0 , y00 )) = (x, y0 , y00 )
dx ∂y ∂y
et les équations sur les contraintes
1
lε (u1 , u2 ) = [(u1 − y1 )2 + (u2 − y2 )2 ].
ε
Rx
Soit y0 la solution du problème de minimisation de J(y) = x12 f (x, y, y 0 )dx
avec les contraintes y(x1 ) = y1 , y(x2 ) = y2 . Si K = {y, y(x1 ) = y1 , y(x2 ) = y2 },
alors, pour tout y ∈ K, J(y) + lε (y(x1 ) − y1 , y(x2 ) − y2 ) = J(y). On utilise alors
Ainsi J(yε ) est majoré. De plus, si on suppose f positive, lε (yε (x1 )−y1 , yε (x2 )−
y2 ) est majorée par J(y0 ). On en déduit que la suite (yε (xj )) converge vers
yj , j = 1..2. En revanche, on ne sait rien sur la convergence de la suite yε
dans ce cadre là. Il faut se reporter au chapitre concernant le programme
convexe pour comprendre et obtenir des résultats convaincants; cela s’appellera
la pénalisation des contraintes.
Z t1 Z t1 Z t1
1
A(X) = [ m(Ẋ(t))2 − U (X(t))]dt = (T − U )dt = L(q(t), q 0 (t))dt.
t0 2 t0 t0
multiplicateurs de Lagrange.
˙ −
Si ξ est un élément de l’espace H 1 (]t0 , t1 [), le calcul de 1ε [L(q0 + εξ, q̇0 + εξ)
0 0
L(q0 , q̇0 )] conduit à l’expression ((L (q0 , q̇0 ), ξ) =< L (q0 , q̇0 ), ξ(t) >)
d
L0 (q0 , q̇0 ) = ∂q L(q0 , q̇0 ) − [∂q̇ L(q0 , q̇0 )] + ∂q̇ L(q0 , q̇0 )(t1 )δt1 − ∂q̇ L(q0 , q̇0 )(t0 )δt0 .
dt
La théorie des multiplicateurs de Lagrange avec q(t0 ) = q0 , q(t1 ) = q1 donne
alors immédiatement le système
d
∂q L(q0 , q̇0 ) − dt [∂q̇ L(q0 , q̇0 )] = 0 (équation d’Euler)
q0 (t0 ) = q0 , q0 (t1 ) = q1 (contraintes actives)
λ = −∂q̇ L(q0 , q̇0 )(t1 )
1
λ0 = ∂q̇ L(q0 , q̇0 )(t0 )
L’écriture des deux premières égalités permet d’avoir les conditions d’extrémité
et l’équation de Newton. Les deux dernières donnent les multiplicateurs de
Lagrange. On obtient
On en déduit
∂q H(t, q, p) = (p − ∂q̃ L(t, q, Q(q, p))).∂q Q(t, q, p) − ∂q L(t, q, Q(q, p)) = −∂q L(t, q, Q(q, p))
∂p H(t, q, p) = Q(t, q, p) + (p − ∂q̃ L(t, q, Q(q, p))).∂p Q(t, q, p) = Q(t, q, p).
∂L
Par unicité de la solution de l’équation p = ∂q̃ L, que pour p(t) = ∂ q̃ (t, q0 (t), q̇0 (t)),
alors Q(t, q0 (t), p(t)) = q̇0 (t), soit
∂L
Q(t, q0 (t), (t, q0 (t), q̇0 (t))) = q̇0 (t).
∂ q̃
On en tire que, pour toute fonction q0 (t), on a l’identité
∂L
∂p H(t, q0 (t), (t, q0 (t), q̇0 (t))) = q̇0 (t).
∂ q̃
Maintenant, si q0 est solution de l’équation d’Euler, on trouve
d ∂L ∂L
( (t, q0 (t), q̇0 (t))) = (t, q0 (t), q̇0 (t)),
dt ∂ q̃ ∂q
soit
d ∂L ∂L
( (t, q0 (t), q̇0 (t))) = −∂q H(t, q0 (t), (t, q0 (t), q̇0 (t))).
dt ∂ q̃ ∂ q̃
On en déduit le système, appelé système hamiltonien:
(
dp ∂H
dt = − ∂q (t, q0 (t), p(t))
dq0 ∂H
dt = ∂p (t, q0 (t), p(t))
d
(∂q̃ L(t, q(t), q̇(t)) = ∂p L(t, q(t), q̇(t)).
dt
On a démontré la proposition suivante, dans le cas où L est une fonction stricte-
ment convexe dans les variables (q, q̃):
54 CHAPTER 3. CALCUL DES VARIATIONS
Dire que le couple de fonctions de IR dans IRd (q0 (t), p0 (t)) est solution du
système hamiltonien
∂H
q̇0 (t) = ∂p (t, q0 (t), p0 (t))
ṗ0 (t) = − ∂H
∂q (t, q0 (t), p0 (t))
p (0) = p , q (0) = q
0 0 0 0
d ∂L ∂L
( (t, q0 (t), q̇0 (t))) = (t, q0 (t), q̇0 (t))
dt ∂ q̃ ∂q
avec les conditions initiales q0 (0) = q0 , q̇0 (0) = q̃0 , où q̃0 est la solution de
p0 = ∂L
∂ q̃ (t, q0 , q̃0 ).
d y 0 (x) 0 2 12 ∂y c
( 1 ) = −(1 + (y (x)) ) (3.4.4)
dx c(x, y(x))(1 + (y 0 (x))2 ) 2 c2
d’où on déduit
y”(x) 1 y 0 (x)
3 + 1 ∂x c = 1 .
c(x, y(x))(1 + (y 0 (x))2 ) 2 c2 (1 + (y 0 (x))2 ) 2 c2 (1 + (y 0 (x))2 ) 2
On en déduit donc
d 1 0 2 21 ∂x c
( 1 = −(1 + (y (x)) ) . (3.4.5)
dx c(x, y(x))(1 + (y 0 (x))2 ) 2 c2
~
Les deux relations (3.4.5) et (3.4.4) expriment que ct a sa dérivée qui suit le
gradient de 1c , les rayons suivent le gradient de l’indice.
1
0 2 2
D’autre part, le hamiltonien équivalent au lagrangien (1+(y ) )
c(x,y(x)) ne peut pas
être calculé, car le lagrangien n’est pas strictement convexe.
3.4. FORMULATION HAMILTONIENNE 55
1 1
(1 + (y 0 )2 ) 2 1 w (1 + (y 0 )2 ) 2 2 w2 1 + (y 0 )2
= [−( − ) + 2 + ].
c(x, y(x)) 2 c(x, y) w c w2
q̇ 2 +q̇ 2 2
Nous allons faire le raisonnement sur Lw (q1 , q2 , q̇1 , q̇2 ) = 1w2 2 + c2 (qw1 ,q2 ) . En
effet, Lw (q1 , q2 , q̇1 , q̇2 ) ≥ Lw0 (q1 , q2 , q̇1 , q̇2 ) pour w0 qui réalise le minimum en
1
w, c’est à dire w02 = c(q̇12 + q̇22 ) 2 . Dans ce cas on sait que d’une part
1
t2 t2
(q̇12 + q̇22 ) 2
Z Z
inf Lw (q1 , q2 , q̇1 , q̇2 )dt = inf dt
t1 t1 c(q1 , q2 )
et d’autre part
Z t2 Z t2
inf Lw (q1 , q2 , q̇1 , q̇2 )dt = inf Lw0 (q1 , q2 , q̇1 , q̇2 )dt
t1 t1
Ceci est une forme abstraite pour dire, dans le cas qui nous intéresse que
1
t2 t2
(q̇12 + q̇22 ) 2 q̇12 + q̇22
Z Z
1
inf dt = inf ( + 1)dt
t1 c(q1 , q2 ) 2 t1 c2 (q1 , q2 )
Pour ce nouveau lagrangien
1 ẋ2 + ẏ 2
L(x, y, ẋ, ẏ) = ( + 1)
2 c2
le hamiltonien est H(x, y, p, q) = 12 ((p2 + q 2 )c2 − 1). Ses courbes intégrales sont
dx 2
ds = pc
dy
= qc2 ds
dp
ds = −c∂x c(p2 + q 2 )
dq
= −c∂y c(p2 + q 2 )
ds
Il est constant sur les courbes bicaractéristiques. Si les données initiales sont
telles que le hamiltonien soit nul, on trouve que p2 + q 2 = c12 . On choisit le
changement d’abscisse curviligne donné par du = c(x(s), y(s))ds, alors
dx p
du = 2 2 12
(p +q )
dy =
q
du 1
(p2 +q 2 ) 2
dp
= ∂x 1c
du
dq 1
du = ∂y c .
Le vecteur d’onde suit les courbes intégrales du gradient d’indice. Ceci corre-
spond à une théorie d’optique géométrique, comme cela avait été vu ci-dessus
.
56 CHAPTER 3. CALCUL DES VARIATIONS
Chapter 4
Programme convexe
57
58 CHAPTER 4. PROGRAMME CONVEXE
n
Le premier terme est alors égal à 2pn J(u) + 2 2−p n J(v). Le second terme est
n −p
ainsi α8 22n−1 p
||u − v||2 , et est donc égal à α p 2n −p ||u − v||2 . Le cas p < 2n−1
2n−1 2 2n 2n
se traite en échangeant les rôles de u et de v. L’inégalité est démontrée pour θ
de la forme 2pn , puisque pour n − 1, on a p = 0 ou p = 1.
Pour la démontrer Pi=npour θ quelconque, on utilise le fait que, pour tout n,
αi 1
il existe θn égal à i=1 2i tel que αi (θ) ∈ {0, 1} et tel que |θ − θn | ≤ 2n
(développement binaire).
On a, pour tout n
αθn (1 − θn )
J(θn u + (1 − θn )v) ≤ θn J(u) + (1 − θn )J(v) − ||u − v||2 .
2
La limite des deux membres existe, car J est continue, ainsi on a
αθ(1 − θ)
J(θu + (1 − θ)v) ≤ θJ(u) + (1 − θ)J(v) − ||v − u||2 .
2
Le lemme est démontré, et on vérifie la stricte convexité sans souci.
La relation entre les fonctionnelles convexes et les problèmes de minimisation
est la suivante:
u+v 1
J( ) < (J(u) + J(v)) = J(u)
2 2
ce qui est impossible.
On écrit ensuite des propriétés des fonctions convexes dérivables. On a la
4.1. FONCTIONS CONVEXES 59
∀w ∈ H, (J 00 (u)w, w) ≥ α||w||2 .
α
J(u + θ(v − u)) ≤ J(u) + θ(J(v) − J(u)) − θ(1 − θ)||u − v||2 .
2
Ainsi
Z 1
1 1 1 1 α
[φ(1) − 2φ( ) + φ(0)] ≥ α||u − v||2 [ t − ]dt = ||u − v||2 .
2 2 1 2 8 8
2
alors l’épigraphe de J est fermé. Toute fonction dont l’épigraphe est fermé est
semi-continue inférieurement (on le note f s.c.i.).
Notons en particulier que la démonstration de la relation sur la convexité
(J(θu + (1 − θ)v) ≤ θJ(u) + (1 − θ)J(v)) est vraie dès que J est s.c.i.
On a aussi le résultat:
Proposition 4.3 Si J est convexe continue sur K convexe fermé non vide,
il existe une forme linéaire continue L et une constante δ telles que J(v) ≥
L(v) + δ. Si J est α−convexe, on a J(v) ≥ α8 ||v||2 − C
Preuve Si J est convexe continu, son épigraphe est convexe fermé non vide.
Démontrons qu’il est fermé. Soit (λn , vn ) une suite de points de l’épigraphe
qui converge vers (λ, v) dans l’espace de Hilbert IR × V muni de la norme
1
(λ2 + ||v||2 ) 2 . On vérifie que
λn ≥ J(vn ). (4.1.1)
Soit, si J(vφ(n) ) tend vers a, on en déduit que λ ≥ a. Bien sûr, comme J
est continue, a = J(v). Soit v0 ∈ K et λ0 < J(v0 ). On note p0 = (λ0 , v0 ). Il est
à l’extérieur de l’épigraphe et on désigne sa projection sur l’épigraphe Epi(J)
par p∗ = (λ∗ , w0 ).
On montre d’abord λ∗ = J(w0 ).
Comme la projection réalise le minimum de la distance, on a ∀(λ, v), λ ≥ J(v),
c’est-à-dire (λ − λ0 )2 + (v − v0 )2 ≥ (λ∗ − λ0 )2 + (w0 − v0 )2 .
4.1. FONCTIONS CONVEXES 61
(1 − θ0 )2 (v0 − w0 )2 ≥ (v0 − w0 )2
ce qui entraine v0 = w0 , impossible car J(v0 ) < λ0 < J(w0 ).
On a donc montré que λ∗ = J(w0 ).
On a alors l’inégalité fondamentale de la projection:
v0 −w0
J(v) ≥ ( (J(w 0 )−λ0 )
, v − v0 ) + (J(w0 ) − λ0 )λ0 .
La première inégalité de la proposition est démontrée. Notons que la difficulté
de cette preuve provient de la continuité et non la dérivabilité de J dans nos
hypothèses; en effet le cas où J est dérivable est évident dans la mesure où J
dérivable et convexe entraine l’inégalité J(u) ≥ J(u0 ) + (J 0 (u0 ), u − u0 ), donc
la forme linéaire est naturelle. L’α−convexité entraine tout de suite après la
relation J(u) ≥ J(u0 ) + α4 ||u − u0 ||2 + [ α4 ||u − u0 ||2 + (J 0 (u0 , u − u0 )], et le
deuxième terme est une forme quadratique dont le minimum est explicite.
D’autre part, on trouve, pour v0 fixé
J(v) + J(v0 ) v + v0 α v + v0 α
≥ J( ) + ||v − v0 ||2 ≥ L( ) + δ + ||v − v0 ||2
2 2 8 2 8
Théorème 4.1 Soit K un convexe fermé non vide dans un Hilbert V et soit J
une fonctionnelle convexe continue sur K.
• Si J est infinie à l’infini, alors J admet un minimum.
• Si J est α−convexe continue, le minimum u est unique, et on a
4
∀v ∈ K, ||v − u||2 ≤ [J(v) − J(u)].
α
Le premier résultat se base sur la convergence faible d’une suite minimisante
un . Nous l’admettons ici.
Le deuxième résultat provient de l’écriture, pour un suite minimisante, de
la relation, notant l l’inf de J
4.2. MINIMISATION DE FONCTIONNELLES CONVEXES 63
un + um J(un ) + J(um ) α
l ≤ J( )≤ − ||un − um ||2
2 2 8
qui implique
4
||un − um ||2 ≤ [(J(um ) − l) + (J(un ) − l)]
α
Nous sommes exactement dans le cas d’application du critère de Cauchy, ainsi
la suite um est de Cauchy, donc possède une limite u. On passe à la limite en
m dans l’inégalité ci-dessus, ce qui implique que
4 4
||un − u||2 ≤ [J(un ) − l] = [J(un ) − J(u)].
α α
Le résultat est démontré.
Dans le cas convexe, on a une condition nécessaire et suffisante d’optimalité,
obtenue à partir de la condition nécessaire provenant de l’équation d’Euler, que
je rappelle ci-dessous
∀v ∈ K, (J 0 (u), v − u) ≥ 0
u minimum de J ⇔ ∀v ∈ K, (J 0 (u), v − u) ≥ 0.
∀v ∈ K, J(v) ≥ J(u).
Ainsi u est un minimum global.1
On note que, lorsque le K est un cône convexe fermé (c’est-à-dire λv ∈ K
pour v ∈ K et λ > 0), on a
1
La redémonstration rapide de l’inéquation d’Euler provient de θ1 (J(u+θ(v−u))−J(u)) ≥ 0
lorsque u est le minimum.
64 CHAPTER 4. PROGRAMME CONVEXE
(J 0 (u), v − u) ≥ 0∀v ∈ K
et on prend v = λu. Les deux cas λ > 1 et 0 < λ < 1 donnent (J 0 (u), u) = 0,
et le remplacer dans l’inégalité donne le résultat de la proposition.
Définition 4.3 On dit que la forme bilinéaire a continue sur V est coercive si
et seulement si il existe ν > 0 tel que
∀u ∈ V a(u, u) ≥ ν||u||2 .
On a alors le
ce qui entraine
1 1 ε2
(J 0 (u), w) = lim [J(u+εw)−J(u)] = lim [εa(u, w)+ a(w, w)−ε(b, w)] = a(u, w)−(b, w).
ε→0 ε ε→0 ε 2
Alors (J 0 (u) − J 0 (v), u − v) = a(u, u − v) − (b, u − v) − a(v, u − v) + (b, u − v) =
a(u − v, u − v), donc
4.4. KUHN ET TUCKER 65
Dans cette égalité, φ appartient à H01 (Ω) car le complété pour la norme H 1 de
C0∞ (Ω) est H01 (Ω).
L’égalité ci-dessus s’écrit donc a(u, φ) = (b, φ), où a est une forme bilinéaire
continue et b est un élément du dual de H01 (Ω). C’est donc l’équation d’Euler
pour la fonctionnelle
1
2 a(u, u) − (b, u).
Comme Ω est borné, la norme ||u||H 1 est équivalente à la norme ||∇u||L2 par
l’inégalité de Poincaré, donc d’après le calcul de dérivée seconde qui précède, la
fonctionnelle est ν−convexe, donc il y a existence et unicité du minimum, qui
est la solution du problème variationnel.
x1 + y1 x2 + y2 1 1 1 1
J( , ) − J(x1 , y1 ) − J(x2 , y2 ) = − (x1 − y1 )2 − (x2 − y2 )2
2 2 2 2 8 8
ce qui fait que J est 1−convexe! D’autre part, une contrainte linéaire est
convexe, on est donc dans le cas du programme convexe. D’autre part, on
trouve J 0 (y1 , y2 ) = y − b. La condition nécessaire d’optimalité est alors
(y 0 − b, y − y 0 ) ≥ 0, ∀y, a.y = 0
• cas égalité:
Si y 0 est intérieur à a.y = 0 (c’est-à-dire a.y 0 6= 0) alors y 0 = b et si b vérifie
a.b = 0 cela convient.
Si y 0 est au bord de a.y = 0 (c’est-à-dire a.y 0 = 0) on a a.(y − y 0 ) = 0
donc y − y 0 est proportionnel à aT , ainsi (y 0 − b, µaT ) ≥ 0 pour tout µ, donc
(y 0 − b).aT = 0, soit y 0 − b = −λa, et on identifie λ grâce à y 0 .a = 0.
• cas inégalité:
si y 0 est intérieur à a.y ≤ 0, alors a.y 0 < 0 et donc toutes les directions sont
admissibles et donc y 0 = b. Si on n’est pas dans le cas b.a < 0, le point b n’est
pas le minimum sur l’espace des contraintes car il n’est pas intérieur à l’espace
des contraintes.
On suppose donc maintenant que a.b ≥ 0. On sait donc que y 0 est sur le
bord a.y 0 = 0. On voit alors que pour tout y ∈ {a.y ≤ 0}, alors a.(y − y 0 ) ≤ 0.
Les directions possibles pour y − y 0 sont donc aT et a, le coefficient devant a
étant négatif. On écrit y − y 0 = µaT − µ1 a, et on en déduit que
d
(φ(t) + λ0 F (y0 + tw))|t=0 = 0.
dt
On vérifie ainsi très directement que y0 n’est pas seulement le minimum de
J mais aussi le minimum de J + λ0 F .
Ceci nous amène à introduire dans l’exemple canonique en dimension 2 cette nouvelle fonction-
nelle. On pose
Le minimum sur IR2 de cette fonctionnelle est obtenu en y = b − λa, ce qui correspond à la remarque
que nous avons déjà faite sur le fait que cette écriture est la bonne écriture pour trouver le minimum.
Maintenant, lorsque y est dans l’intérieur de l’espace des contraintes a.y < 0 et que λ est assez petit,
alors y + λa est aussi dans l’espace des contraintes, donc le minimum de L(y, λ) est atteint en un
point yλ de l’espace des contraintes, et on vérifie que ce minimum vaut − 12 (b − λa)2 . Cette fonction
a.b
de λ admet un maximum en λ = a2
. et cette valeur du point où elle est maximum est celle cherchée
pour obtenir le point critique de J sous les contraintes a.y ≤ 0 lorsque b n’est pas dans l’espace des
contraintes.
D’autre part, lorsque y n’est pas dans l’espace F (y) = 0, on voit que L(y, λ)
n’a certainement pas d’extremum en λ (contrairement à ce que l’on a fait dans
le paragraphe ci-dessus) et on a probablement identifié un problème équivalent.
Notons que cette définition est la bonne définition pour les multiplicateurs
de Lagrange, puisque les extrema sont caractérisés par la dérivée nulle.
On a
Preuve On suppose que (u, p) est un point selle. On se place tout d’abord
dans le cas de contraintes d’égalité. Si on suppose que, pour tout q dans
IRM , alors L(q, u) ≤ L(p, u), comme L(q, u) est une fonction affine en q, cette
inégalité ne peut être vérifiée que lorsque F (u) = 0. On a donc, écrivant la
deuxième inégalité, J(u) ≤ J(v) pour tout v ∈ U , donc a fortiori pour tout
v ∈ K, et donc u est un minimum global de J sur K.
On se place ensuite dans le cas de contraintes inégalités. Si on a, ∀q ∈
(IR+ )M , l’inégalité, ceci veut dire que, en faisant tendre q vers +∞ composante
après composante, que F (u) ≤ 0. On trouve alors pF (u) ≥ 0 par l’inégalité
L(q, u) ≤ L(p, u), et comme Fj (u) ≤ 0, on trouve que pj Fj (u) = 0 pour tout
j. Ceci permet de conclure sur le fait que u est un minimum global de J car
pF (v) ≤ 0 ainsi J(v) + pF (v) ≤ J(v) et donc l’inégalité de droite de définition
du point selle entraine J(u) + 0 ≤ J(v). Le point u est aussi minimum de la
fonctionnelle J(v)+pF (v), donc nécessairement la dérivée de cette fonctionnelle
est nulle si K est intérieur à U .
Ce qui est extraordinaire est qu’il y a des conditions pour lesquelles cette
proposition donne une condition nécessaire et suffisante d’optimalité
q q 2 + q02
∀(µ0 , µ) ∈ A, µ0 − J(u) + µ ≥
q0 q0
donc si on prend le point µ0 = J(v) + , µj = Fj (v) + qui est dans A on voit
que pour tout v ∈ V
q X qj
J(v) − J(u) + F (v). + ε(1 + )≥0
q0 q0
70 CHAPTER 4. PROGRAMME CONVEXE
Ainsi il n’y a aucun problème si il existe une contrainte active non affine, car
F (ṽ)
dans ce cas on se ramène à qj j2 ≥ q 2 , donc qj = 0. Il reste donc les contraintes
actives affines. Elles sont données par Fj (v) = (aj , v) et il suffit de changer de
vecteur ṽ pour prendre successivement un vecteur orthogonal a tous les vecteurs
ap p 6= p0 et dont le produit scalaire avec ap0 est négatif. On en déduit que q = 0
ce qui donne donc une inégalité trivialement vérifiée. Ainsi on trouve p0 = J(u)
et p = 0 donc la projection de (J(u), 0) est lui même. C’est impossible car le
point en question ne peut pas être dans A.
L’égalité qq0 .F (u) = 0 entraine donc
q q
∀v ∈ V, J(v) + ( , F (v)) ≥ J(u) + ( , F (u)) ≥ J(u) + (r, F (u))∀r, rj ≥ 0.
q0 p = q0
∀v ∈ V, L(u, p) ≤ L(v, p)
ce qui implique que, utilisant L(v, p) ≤ supq∈P L(v, q):
De même,
∀q ∈ P, L(u, q) ≤ L(u, p)
donc, utilisant cette fois L(u, q) ≥ inf v∈V L(v, q), on obtient
Ceci donne l’idée d’introduire deux fonctionnelles définies par ces inégalités,
l’une sur V , l’autre sur P , par
Dans le cas étudié, on a L(v, q) = J(v) + qF (v), donc, si il existe j0 tel que
Fj0 (v) > 0, alors supq∈P L(v, q) = +∞, et, si on a ∀j ∈ {1, ..., m}, Fj (v) ≤ 0
alors supq∈P L(v, q) = maxq∈ L(v, q) = L(v, 0) = J(v).
Ainsi
˜ J(v), v ∈ K
J(v) =
+∞, v ∈ /K
˜
∀v ∈ V, L(u, p) ≤ J(v)
ce qui s’écrit
˜
∀v ∈ V, J(u) ˜
≤ J(v)
On en déduit que u est le minimum de J˜ sur V . De même
∀v ∈ V, L(u, p) ≤ L(v, p)
donc
Comme inf v∈V L(v, q) ≤ L(u, p), on a, ∀q ∈ P, G(q) ≤ G(p), donc p est un
maximum de G. On a ainsi démontré:
∂L
(v, q) = 0
∂v
72 CHAPTER 4. PROGRAMME CONVEXE
qui admet une solution unique car L est α−convexe, où α est la plus petite
valeur propre de la matrice 12 A.
On trouve Av − b + t Bq = 0, soit v = A−1 b − A−1t Bq, donc
1 1
G(q) = − (t Bq, A−1t Bq) + (BA−1 b − c, q) − (b, A−1 b)
2 2
qui est strictement concave donc admet un maximum. Le gain dans cette for-
mulation est que les contraintes s’écrivent vraiment simplement: en l’occurence
elles sont sous la forme q ≥ 0.
Chapter 5
Introduction au contrôle
optimal
Ay = f + Bu
z(u) = Cy(u).
73
74 CHAPTER 5. INTRODUCTION AU CONTRÔLE OPTIMAL
On introduit enfin sur l’espace U des contrôles un opérateur coercif N tel que
(N u, u) ≥ ν0 ||u||2H0 . Le coût du contrôle est alors
Notons que le terme ||Cy(u) − zd ||2 est un vrai terme de contrôle et le terme N
est un terme de pénalisation.
Définition 5.2 Le problème de contrôle est de trouver l’inf de J(u) sur l’ensemble
des u admissibles.
On sait que y(u) = A−1 (f + Bu) (revenant au cas général), d’où on déduit
(y 0 (u), w) = A−1 Bw. On a donc
Avec
J(u + tw) − J(u) = (C(y(u) + (y(u + tw) − y(u))) − zd , C(y(u) + (y(u + tw) − y(u))
+(C(y(u + tw) − y(u)), C(y(u + tw) − y(u))) − (Cy(u) − zd , Cy(u) − zd )
+2t(N u, w) + t2 (N w, w).
C ∗ (Cy(w) − zd ) = A∗ p(w)
(B ∗ p(u) + N u, v − u) ≥ 0∀v.
Cette inégalité est plus facile à traiter. On résume alors les résultats dans le
Théorème 5.2 On calcule la solution contrôlée y(u) telle que Ay(u) = f +Bu.
On forme l’état adjoint p(u) qui est solution de l’équation A∗ p(u) = C ∗ (C(y) −
zd ).
L’inéquation d’Euler qui caractérise la solution du problème de contrôle est:
L’opérateur adjoint A∗ est donné par (Aφ, ψ) = (φ, A∗ ψ). En faisant le calcul
dans les fonctions C0∞ (Ω), on trouve
P
(Aφ, ψ) = i,j (a (x)∂j φ, ∂i ψ) + (a0 (x)φ, ψ)
Pij
= − i,j (φ, aij (x)∂i ψ) + (a0 (x)φ, ψ)
A∗ p − y = −zd
y, p ∈ H01 (Ω)
a(y, ψ) = f (ψ)∀ψ ∈ V ⇔ Ay = f.
1
On suppose que l’on a à la fois une donnée au bord g ∈ H − 2 (Γ) et une donnée
dans l’ouvert f1 ∈ L2 (Ω), de sorte que la forme linéaire soit, γ étant l’opérateur
de trace:
Z Z Z
f (ψ) = f1 ψdx + γψgdσ = f1 ψdx+ < g, γψ > .
Ω Γ Ω
l’égalité ci-dessus sur < Aφ, ψ > permet de construire de manière abstraite la
1
dérivée normale par passage à la limite pour φ, ψ dans H 1 donc γψ ∈ H 2 (Γ).
L’état adjoint est identifié comme la solution du problème de Neumann adjoint,
où il n’y a pas de terme source sur le bord:
(i)x(0) − x0 = 0
(ii)ẋ(t) − f (x(t), u(t), t) = 0
La contrainte (i) admet λ comme multiplicateur, la contrainte (ii) admet p(t)
comme multiplicateur (en effet, l’une est continue, l’autre est ponctuelle). Le
lagrangien est
Z 1 Z 1
L(x, u, λ, p) = g(x(t), u(t), t)dt+C(x(1))+ p(t)(ẋ(t)−f (x(t), u(t), t))dt+λ(x(0)−x0 ).
0 0
R1 0 0
L(x, u, λ, p) = 0 Rg(x(t), u(t), t)dt + p(1)x(1) + C(x(1)) + λ(x(0) − x ) − p(0)x .
1
− 0 (ṗ(t)x(t) + p(t)f (x(t), u(t), t))dt
Z 1 Z 1
gx (x(t), u(t), t)w(t)dt− (ṗ(t)+p(t)fx (x(t), u(t), t))w(t)dt+C 0 (x(1))w(1) = 0,
0 0
Z 1 Z 1
gu (x(t), u(t), t)w̃(t)dt − p(t)fu (x(t), u(t), t)w̃(t)dt = 0,
0 0
Z 1
(π̇(t)x(t) + π(t)f (x(t), u(t), t))dt = 0.
0
De la deuxième, on déduit gu (x(t), u(t), t) = p(t)fu (x(t), u(t), t). De la
première, on déduit ṗ(t)+fx (x(t), u(t), t)p(t) = gx (x(t), u(t), t). De la troisième,
en effectuant une intégration par parties, on déduit l’équation (ii).
On note que le multiplicateur de Lagrange p est solution d’une équation que
l’on appelle équation adjointe de ẋ = f (x, u, t).
On remplace l’équation obtenue pour p dans le lagrangien. Alors
R1 R1
L(x, u, p, t) = 0[g(x(t), u(t), t) − xgx (t)]dt + p(1)x(1) + C(x(1)) − 0 p(t)(−x(t)fx
+f (x(t), u(t), t))dt + λ(x(0) − x0 ) − p(0)x0 .
d
(Lẋ ) = Lx
dt
qui est l’équation d’Euler associée à ce lagrangien. D’autre part, de ce problème,
on déduit l’équation de Hamilton-Jacobi-Bellman.
Pour écrire cette équation on considère le même problème:
Z 1
infẋ(t)=f (x(t),u(t),t),x(0)=x0 J(u) = g(x(t), u(t), t)dt + C(x(1))
0
5.4. EQUATION DE HAMILTON-JACOBI-BELLMANN 79
Z 1
V (y, τ +) = min[ g(x(t), u(t), t)dt+c(x(1)), ẋ(t) = f (x(t), u(t), t), x(τ +) = y].
u τ +
D’autre part
Z 1 Z τ + Z 1
g(x(t), u(t), t)dt = g(x(t), u(t), t)dt + g(x(t), u(t), t).
τ τ τ +
R1
Soit u la solution du problème de minimisation pour τ g(x(t), u(t), t)dt. On
trouve
∂V ∂V
+ min[g(y, v, t) + f (y, v, t)] = 0
∂t v ∂y
admet une solution de classe C 1 telle que V (x, 1) = C(x), alors le problème
R1
J(u) = 0 g(x(t), u(t), t)dt + C(x(1))
inf
ẋ(t) = f (x(t), u(t), t), x(0) = x0
admet une commande optimale v(x, t), qui minimise en v à chaque instant
80 CHAPTER 5. INTRODUCTION AU CONTRÔLE OPTIMAL
∂V
g(x, v, t) + (x, t)f (x, v, t).
∂x
L’équation de HJB s’écrit Vt = max H(x, −Vxt , u, t).
∂V ∂V
On considère pour cela G(x, u, t) = g(x, u, t) + ∂x (x, t)f (x, u, t) + ∂t (x, t).
Elle vérifie
On note u∗
le point où ce minimum
R1 est atteint.
On remarque alors que 0 G(x(u), u, t)dt ≥ 0 pour tout u et que
Z 1
∂V ∂V
[ (x(u), t)f (x(u), u, t) + (x(u), t)]dt = V (x(1), 1) − V (x(0), 0)
0 ∂x ∂t
d’où on déduit
ẍ + ω 2 (1 − εu(t))x = 0,
où x(0) et ẋ(0) sont connus, et on veut l’amener à l’état (x(t1 ), ẋ(t1 )), où
(x(t1 ))2 + (ẋ(t1 ))2 > (x(0))2 + (ẋ(0))2 . On peut le faire en introduisant la
commande u(t) qui vérifie 0 ≤ u(t) ≤ 1. Ainsi, on peut faire varier la fréquence
d’oscillation du ressort entre ω 2 et ω 2 (1 − ε).
On est dans la situation de ce chapitre lorsque on écrit cette équation
différentielle sous la forme du système différentiel
ẋ = y, ẏ = −(1 − εu(t))x.
1. on détermine T > t1 tel que x(t) ne s’annule pas sur [t1 , T [ et s’annule en
t = T . Le contrôle reste u = 1.
• Sur ]t2 , T [:
82 CHAPTER 5. INTRODUCTION AU CONTRÔLE OPTIMAL
π b 1 π b
x(t2 ) = b cos(β−γ−π+ ) = ρ(α) cos ω(α), ẋ(t2 ) = −b(1−ε) 2 sin(β−γ− ) = ρ(α) sin ω(α).
2 a 2 a
• Sur ]t3 , t2 [:
Le contrôle est u = 0, et les trajectoires sont des cercles. On identifie
directement
b 1 1
ẋ(t3 ) = ρ(α) , q(t3 ) = −a(1 − ε) 2 cos ω(α), q̇(t3 ) = a(1 − ε) 2 sin ω(α).
a
5.4. EQUATION DE HAMILTON-JACOBI-BELLMANN 83
• Sur ]t4 , t3 [:
Le contrôle est a nouveau u = 1. Les courbes décrites par les points sont
(ẋ(t))2 b2 (q̇(t))2
(x(t))2 + = ρ2 (α) 2 , (q(t))2 + = a2 (1 − ε cos2 ω(α))
1−ε a (1 − ε) 1−ε
ce qui donne
1
x(t) = ρ(α) ab 1
1 cos((1 − ε) 2 (t − t3 ) − π2 )
(1−ε) 2
1 1
q(t) = a(1 − ε cos2 ω(α)) 2 cos((1 − ε) 2 (t − t3 ) + β(α))
avec les relations
1
sin ω(α) (1 − ε) 2 cos ω(α)
sin β(α) = − 1 , cos β(α) = − 1 .
(1 − ε cos2 ω(α)) 2 (1 − ε cos2 ω(α)) 2
• Pour t ∈]T̃ , t4 [:
le contrôle est alors u = 0, les points se déplacent sur des cercles, donc
x(t) = µ(α) cos(t − t4 − π + ω(α)). Le point où x(t) s’annule est alors T̃ =
t4 − π2 − ω(α), ce qui donne tout de suite ẋ(T̃ ) = −µ(α).
Dans ce cas, on a fait un tour complet de l’espce des phases pour x(t), y(t)
de t = T̃ à t = T . Le gain d’orbite (rapport entre la valeur du point pour les
deux temps) est alors
1
ẋ(T ) b(1 − ε) 2 1 − ε + ε2 cos2 α sin2 α
= =
ẋ(T̃ ) µ(α) 1 + ε2 cos2 α sin2 α
Approximation de solutions de
problèmes d’optimisation
puis
inf J(un+1
1 , v2 , un3 ) = J(un+1
1 , un+1
2 , un3 )
v2 ∈V2
85
86 CHAPTER 6. APPROXIMATION DE SOLUTIONS
enfin
inf J(un+1
1 , un+1
2 , v3 ) = J(un+1
1 , un+1
2 , un+1
3 ).
v3 ∈V3
un+1,1 = (un+1
1 , un2 , un3 ), un+1,2 = (un+1
1 , un+1
2 , un3 ), un+1,3 = (un+1
1 , un+1
2 , un+1
3 ).
(J 0 (un ), un − u)
= (J10 (un n n 0 n
1 , u2 , u3 ) − J1 (u1 , u2
n−1
, u3n−1 ), un
1 − u1 )
0 0 n−1
+(J2 (u1 , u2 , u3 ) − J2 (u1 , u2 , u3 ), un
n n n n n
2 − u2 )
ce qui permet d’utiliser le caractère Lipschitz, pour avoir
1
(J 0 (un ), un − u) ≤ C[(||u n−1 n 2
√ 2 n+1− u2 ||n + ||u
n−1
3 − un 2 n n n−1
3 || ) 2 ||u1 − u1 || + ||u3 − u3 ||.||un
2 − u2 ||]
n
≤ C 2||u − u ||.||u − u||
√ 2 1
grâce à ||un n
1 − u1 || + ||u2 − u2 || ≤ 2(||un 2 n
1 − u1 || + ||u2 − u2 || ) 2 ce qui achève la preuve de
l’inégalité.
88 CHAPTER 6. APPROXIMATION DE SOLUTIONS
On peut aussi écrire une définition plus générale, qui tienne compte des
contraintes égalités:
Lemme 6.1 Si d est une direction de descente, c’est une direction de descente
limite.
Ceci est une conséquence du fait que si d est une direction de descente,
d ∈ K̇(u) donc d ∈ K(u) et la suite que l’on peut définir est d() = d.
On a alors le résultat suivant
Preuve Comme F 0 (u) est non nul, il définit une droite vectorielle dans l’espace
de Hilbert, qui est un fermé convexe. Ainsi tout point w de l’espace de Hilbert se
projette en un point φ(w)F 0 (u), et on a w − φ(w)F 0 (u) dans l’espace orthogonal
à F 0 (u).
L’égalité F (v + u + tF 0 (u)) = 0 a pour solution t = 0, v = 0 car u vérifie
F (u) = 0. Pour chaque v dans (F 0 (u))⊥ , on trouve, par le théorème des fonc-
tions implicites (dû à ∂t (F (v+u+tF 0 (u))) = ||F 0 (u)||2 > 0) une unique solution
de l’égalité ci-dessus, soit t = g(v). Alors, au voisinage de u, on étudie pour tout
v dans l’intersection Iu d’une boule de petit rayon et de (F 0 (u))⊥ , la fonction-
nelle sous les contraintes. On voit alors que pour tout v dans Iu , le problème
90 CHAPTER 6. APPROXIMATION DE SOLUTIONS
˜
infJ(v)
v ∈ Iu
v + g(v)F 0 (u) ∈ K
(un , dn , ln )
telle que
i) dn est une direction de descente en xn pour J, associée à ρn tel que
J(un + dn ) < J(un ) pour 0 < < ρn
ii) ln est un pas vérifiant 0 < ln < ρn
iii) un+1 = un + ln dn .
Les algorithmes les plus courants sont des algorithmes de recherche linéaires.
En effet, ces algorithmes conduisent, une fois la direction de descente choisie, à
la recherche d’une valeur réelle qui est la valeur du pas. On suppose ainsi que, à
chaque étape, la direction de descente dn soit choisie. Nous allons décrire dans
ce qui suit un certain nombre d’algorithmes.
Dans tous les cas, on notera, par souci de simplicité
φ(lg ) − φ(0)
0 < m1 ≤ ≤ m2 < 1.
lg φ0 (0)
La situation importante est la situation où il existe au moins 1 , 0 < 1 < ρ0
tel que
m < m2 , l’ensemble des pas de Goldstein associés à [m1 , m2 ] est non vide. En
effet, définissons h() = φ()−φ(0)
φ0 (0) et, par continuité, h(0) = 1. La fonction h est
une fonction continue.
Par le théorème des valeurs intermédiaires, comme h(0) = 1 et h(1 ) = m,
l’image réciproque dans [0, 1 ] de [m, m2 ] ⊂ [m, 1] est non vide. Tout point de
[m, m2 ] a au moins un antécédent par h, qui est un pas de Goldstein.
D’autre part, l’image réciproque de ]m2 , 1] contient un voisinage [0, 2 ] de
= 0 puisque h(0) = 1. Ainsi on a ∀ ∈ h−1 (]m2 , 1]), n’est pas un pas de
Goldstein, donc si lg est un pas de Goldstein, lg ≥ 2 .
Enfin, on ne peut pas avoir → ∞. En effet, cela impliquerait que pour
tout , ou au moins pour une suite n tendant vers +∞, la relation
φ(n ) − φ(0)
≥ m1
n φ0 (0)
soit φ(n ) ≤ φ(0)+m1 φ0 (0)n . Il existe donc une suite n telle que J(u+n d) →
−∞, et le minimum n’existe pas.
φ0 (lw ) ≥ m2 φ0 (0)
Proposition 6.3 i) Si φ0 () ≤ φ0 (0) pour tout ∈ [0, ρ0 [, il n’existe pas de pas
de Wolfe. (On note que cela implique qu’il n’existe pas de pas de Goldstein).
ii) Dans le cas contraire, il existe (m1 , m2 ) tels que l’ensemble des points l
vérifiant les inégalités de la définition 6.7 est non vide.
iii) Il existe 02 > 0 et M > 0 tels que lw ≥ 02 , lw ≤ M .
φ0 (1 )
Preuve Si 1 donné tel que φ0 (1 ) > φ0 (0), alors m = φ0 (0) < 1 et donc on
φ0 (0) 0 ()
choisit m2 ∈]m, 1[. Comme = 1 et que la fonction
φ0 (0) → φφ0 (0)
est continue,
par le théorème des valeurs intermédiaires, tout point de ]m, 1] a au moins un
antécédent, et l’image réciproque de ]m2 , 1] contient un voisinage de 0. On
prend un point l de (φ0 )−1 [m2 φ0 (0), mφ0 (0)], ainsi l ≥ 02 .
La fonction → φ()−φ(0)
φ0 (0) est continue sur le compact [02 , ρ0 ] et ne s’annule
pas sur cet intervalle, donc
φ() − φ(0)
inf∈[02 ,ρ0 ] = α > 0.
φ0 (0)
6.3. RÉSULTATS DE CONVERGENCE 93
On démontre ce théorème.
Preuve de i)
On suppose que la suite un converge (dans le cas du pas de Curry). Ainsi,
comme un+1 − un tend vers 0, ln tend vers 0 puisque dn est de norme 1. D’autre
part, comme J est continuement différentiable, la dérivée de φ est
J(un ) − J(un+1 )
∈ [m1 , m2 ].
(J 0 (un ), un − un+1 )
Dans le cas où on suppose que J 0 est uniformément continue sur
un borné contenant u, alors pour n assez grand comme la suite un converge
6.4. ALGORITHMES DE GRADIENT 95
un+1 = un − µn J 0 (un ),
où µn est la solution unique de (J 0 (un − µJ 0 (un )), J 0 (un )) = 0 qui s’appelle
l’algorithme de gradient à pas optimal, converge vers l’unique valeur qui rend
minimum la fonctionnelle J.
un+1 = un − µJ 0 (un )
et on cherche un+1 = inf µ∈IR J(un − µJ 0 (un )). Il est clair que la dérivée de
φ(µ) = J(un − µJ 0 (un )) est donnée par
D’autre part, la suite un est bornée. En effet, si elle ne l’était pas, il existerait
une sous suite uφ(n) qui tendrait, en norme, vers +∞, et comme la fonctionnelle
J est α−convexe, elle est infinie à l’infini et la suite J(uφ(n) ) tendrait vers
+∞, contradiction. Dans ce cas, en utilisant l’uniforme continuité sur une
boule fermée qui contient tous les termes de la suite un , on en déduit que
||J 0 (un ) − J 0 (un+1 )|| ≤ C||un − un+1 ||. On a alors
2 1 p
||J 0 (un )|| ≤ C||un − un+1 || ≤ ( ) 2 C J(un ) − J(un+1 ).
α
On en déduit la convergence de la suite J 0 (un ) vers 0. On note u le point
où J est minimale. Par la coercivité
ce qui implique
1 0 n
||un − u|| ≤ ||J (u )||
α
donc
1 2 1 p
||un − u|| ≤ ( ) 2 C J(un ) − J(un+1 )
α α
et donc la suite un converge vers u.
Proposition 6.5 Pour que les hypothèses du théorème 6.3 soient vérifiées, il
suffit que J vérifie
i) soit J fonctionnelle α−convexe dérivable, J 0 continue en dimension finie
ii) soit J fonctionnelle α−convexe dérivable, J 0 Lipschitzienne sur tout
borné en dimension infinie
iii) soit J est une fonctionnelle deux fois Fréchet dérivable, telle que la
dérivée seconde soit autoadjointe et vérifie
avec m > 0.
On remarque que ces conditions sont telles que iii) → ii) → i).
La preuve est plus simple. On écrit un+1 − un = −µJ 0 (un ). Ainsi, soit u
la solution On trouve un+1 − u = un − u − µ(J 0 (un ) − J 0 (u)). On utilise un
argument de type “théorème du point fixe”. Ainsi
||un+1 − u||2 = ||un − u||2 − 2µ(J 0 (un ) − J 0 (u), un − u) + µ2 ||J 0 (un ) − J 0 (u)||2
≤ (1 − 2µα + µ2 C 2 )||un − u||2
où C est la constante de Lipschitz de J 0 sur tout l’espace de Hilbert. La
démonstration est terminée car la suite ||un − u|| est alors majorée par une
suite géométrique convergeant vers 0. Dans cette inégalité, on peut choisir la
meilleure valeur de µ, c’est-à-dire celle qui minimise le taux de convergence. Le
minimum de la fonction 1 − 2µα + µ2 C 2 est alors atteint en µ = Cα2 et le taux
q
α2
de convergence est alors 1 − C 2 . En particulier, si la fonctionnelle est une
fonctionnelle quadratique en dimension finie, la valeur optimale de α est la plus
petite des valeurs propres de A = J 00 alors que la valeur optimale de C est la
plus grande des valeurs propres de A. On voit donc la difficulté essentielle à
choisir correctement la meilleure valeur de µ puisque la recherche des valeurs
propres est un problème difficile. On peut espérer une valeur de α inférieure à
λmin et une valeur de C plus grande que λmax , ce qui réduit d’autant le pas.
1 1 l2
φ(l) = J(u−lAu) = (Au−lA2 u, u−lAu) = (Au, u)−l(A2 u, u)+ (A2 u, Au).
2 2 2
(Au,Au)
On en déduit que la valeur du pas optimal est l = (A2 u,Au)
et que la valeur
minimale de φ est
Ce résultat est démontré dans la section 2.4.6. La suite donnée par l’algorithme
(Aun ,Aun )
de gradient à pas optimal est un+1 = un −ln Aun , où ln = (A 2 un ,Aun ) et on trouve
(Aun , Aun )2
J(un+1 ) = J(un )(1 − ).
(A2 un , Aun )(Aun , un )
Dans cette égalité, on prend yn = Aun et on utilise le lemme de Kan-
torovitch. Alors on trouve
Nous passons à l’étude dans le cas général. Pour ce faire, on utilise la formule
de Taylor avec reste intégral pour J et pour J 0 . Pour simplifier les notations,
on effectue une translation sur l’inconnue u pour se ramener au minimum u = 0
et on change J(u) en J(u) − l où l est le minimum de J.
Les formules de Taylor s’écrivent
Z 1 Z 1
1
J(u) = (1−θ)(J 00 (0+θu)u, u)dθ = (J 00 (0)u, u)+([ (1−θ)(J 00 (θu)−J 00 (0))]u, u).
0 2 0
Z 1
J 0 (u) = J 00 (0)u + ( J 00 (θu)dθ − J 00 (0))u
0
u, non singulier car la matrice J”(0) est symétrique définie positive. On écrit
alors µ = µ0 + β. On trouve
(J 00 (0)R(u)u, J 00 (0)u) R(u − (µ0 + β)J 0 (u))(u − (µ0 + β)J 0 (u)), J 00 (0)u + R(u)u)
β+(µ0 +β) − = 0.
(J 00 (0)2 u, J 00 (0)u) (J 00 (0)2 u, J 00 (0)u)
On vérifie alors que, par le théorème des fonctions implicites, il existe une
fonction β(u) telle que β(u) = o(1) c’est-à-dire tend vers 0 avec ||u||. Cette
valeur de β(u) détermine l’unique pas optimal.
On calcule alors
1 (J”(0)u, J”(0)u)2
J(φ(u)) = (J”(0)u, u)(1 − ) + (u)||u||2 .
2 (J”(0)u, u)((J”(0))2 u, J”(0)u)
Enfin, on reconnait que J(u) = 21 (J”(0)u, u)(1 + η(u)) avec η(u) tend vers
0 comme ||u|| puisque J”(0) est symétrique définie positive donc (J”(0)u, u) ≥
λmin ||u||2 . Ainsi il vient
J(u) (J”(0)u,J”(0)u)2
J(φ(u)) = 1+η(u) (1 −
(J”(0)u,u)((J”(0))2 u,J”(0)u)
) + (u)||u||2
(J”(0)u,J”(0)u) 2
= J(u)(1 − (J”(0)u,u)((J”(0)) 2
2 u,J”(0)u) ) + (u)||u||
η(u) (J”(0)u,J”(0)u)2
− 1+η(u) (1 − (J”(0)u,u)((J”(0)) 2 u,J”(0)u) )J(u).
Utilisant alors la plus petite valeur propre de J”(0), on constate qu’il existe une
fonction g(u), tendant vers 0 si ||u|| → 0, telle que
(J”(0)u, J”(0)u)2
J(φ(u)) = J(u)(1 − + g(u)).
(J”(0)u, u)((J”(0))2 u, J”(0)u)
max −λmin
On se donne β > λλmax 2 4λmax λmin
+λmin . On remarque que β + (λmax +λmin )2 > 1. Alors,
comme la suite un converge vers le minimum de la fonctionnelle 0, il existe n0
tel que pour n ≥ n0 on ait
4λmax λmin
1 + g(u) ≤ β 2 + .
(λmax + λmin )2
On en déduit, par application du lemme de Kantorovitch
On a donc, pour n ≥ n0
J(un+1 ) ≤ β 2 J(un )
ce qui donne
J(un+n0 ) ≤ β 2n J(un0 ).
Il suffit de rappeler la relation que l’on a obtenue précédemment
1 2 1 p
||un − u|| ≤ ( ) 2 C J(un ) − J(un+1 ).
α α
On utilise α = λmin et C = λmax , et J(un ) − J(un+1 ) ≤ β 2 J(un ) pour obtenir
λmax p
||un+n0 − u|| ≤ 3 β n+1 2J(un0 ).
2
λmin
On a donc démontré une convergence géométrique de la suite un vers u,
ayant un taux de convergence β arbitraire, strictement supérieur à γ−1
γ+1 . Ce
taux de convergence est moins bon au fur et à mesure que le conditionnement
de la matrice γ tend vers +∞. c’est par exemple ce qui se passe dans un espace
de Hilbert lorsqu’on l’approxime par des espaces de dimension finie de plus
en plus grand et que la matrice admet des valeurs propres formant une suite
tendant vers +∞. Le point ii) du théorème est démontré.
A = (A0 , A1 )
où A0 est une matrice d × d inversible et A1 est une matrice d × (m − d).
u0 = (A−1 0 0 0 0 −1 t 0 0
0 (b − A1 y ), y ), d0 = Jy (u ) − (A0 A1 ) Jx (u )
y 1 = y 0 − µ0 d0 , u1 = (A−1 1 1 0 1 −1 t 0 1
0 (b − A1 y ), y ), d1 = Jy (u ) − (A0 A1 ) Jx (u ),
On vérifie tout d’abord que IRm = {(x, y), x ∈ IRd , y ∈ IRm−d }, et que
A(x, y) = A0 x + A1 y. On en déduit que (x, y) ∈ K ⇔ A0 x = b − A1 y, soit
x = A−1
0 (b − A1 y).
On utilise la procédure décrite dans la proposition 6.1. On en déduit que
J(u) = J(A−1
0 (b − A1 y), y) = Jr (y).
On en déduit la relation
un = (A−1 n n 0 n −1 t 0 n
0 (b − A1 y ), y ), dn = Jy (u ) − (A0 A1 ) Jx (u ).
Dxn = −A−1
0 A1 dn .
donc la direction −Dn est à la fois une direction admissible (continue) et une
direction de descente pour la fonctionnelle J. C’est donc une direction de
descente pour le problème avec contrainte.
D’autre part, si on a Jr0 (y n ) = 0, alors on a dny = (A−1 t n
0 A1 ) dx , ce qui s’écrit
dy = At1 ((A−1
n t n
0 ) dx )
n t −1 t n
dx = A0 ((A0 ) dx )
104 CHAPTER 6. APPROXIMATION DE SOLUTIONS
J 0 (un ) + λAt = 0.
où ∇x F (x0 , y0 ) inversible pour un point (x0 , y0 ) tel que F (x0 , y0 ) = 0. Notons
que cela signifie que F est une application de K dans IRd , et que si on suppose
K ⊂ IRm (ou plus généralement il existe un système de coordonnées sur K
qui est inclus dans un espace vectoriel de dimension m > d, éventuellement de
dimension non finie), alors x ∈ IRd et y ∈ IRm−d . Comme F est un système
de d équations avec d inconnues x et m − d paramètres y, on se trouve dans
le cadre d’application du théorème des fonctions implicites au voisinage de y0 ,
c’est à dire on peut résoudre localement F (x, y) = 0 sous la forme y = G(x).
L’application G est alors une application de IRd dans IRm−d .
Le problème de minimisation s’écrit alors localement
infJ(G(y), y).
On en déduit alors
Dans le cas où a 6= b, la suite est donc infinie et converge par itérations succes-
sives vers le minimum. Si a = b, bien sûr une direction de gradient pointe vers
le centre du cercle et on converge en une itération.
Mais il est clair que (x0 , y 0 ) − (x0 , y 0 ) = (0, 0), donc la direction optimale
n’est pas celle du gradient mais celle du vecteur pointant vers le centre!
Nous cherchons à exploiter cette idée. En effet, en dimension 2, il n’y a que
deux directions possibles, donc même si au premier pas on n’a pas trouvé la
bonne direction, on le trouvera au deuxième pas. Pour cela, on considère la
direction du gradient comme direction de départ. On trouve que
a4 x20 + b4 y02
(x1 , y1 ) = (x0 , y0 ) − λ0 (2a2 x0 , 2b2 y0 ), λ0 = .
2(a6 x20 + b6 y02 )
La bonne direction est (x1 , y1 ), car elle conduit tout de suite au minimum.
On vérifie que
1 1 1
J(x) = (Ax, x) − (Ax0 , x) = (A(x − x0 ), x − x0 ) − (b, x0 ).
2 2 2
Ainsi minimiser J revient à minimiser la norme ||x − x0 ||A .
On se place en dimension finie N . La matrice A est symétrique définie
positive, donc elle est diagonalisable dans une base orthogonale notée (p1 , .., pN ).
On a alors, comme (Api , pj ) = 0 pour i 6= j
X
||x − x0 ||2A = (xi − x0,i )2 (Api , pi ).
i
(A(x1 + λp1 ) − b, p1 ) = 0
soit
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 107
(b − Ax1 , p1 )
λ = λ1 = .
(Ap1 , p1 )
On regarde alors le deuxième point x2 = x1 + λp2 . On trouve que la valeur
de λ est λ2 = (b−Ax 2 ,p2 )
(Ap2 ,p2 ) .
D’autre part, on considère φ(λ, µ) = J(x1 + λp1 + µp2 ). C’est une fonction
de deux variables, qui est minimale pour
∂λ φ = ∂µ φ = 0.
On obtient les relations
xn+1 = xn + λn pn
avec
(b − Axn , pn )
λn =
(Apn , pn )
Alors xn+1 est le point où J est minimum sur En = x1 + Vect(p1 , p2 , ..., pn ).
Cet algorithme est un algorithme de directions conjuguées. On écrit alors
la
Proposition 6.7 Soit (pn ) une suite dans V Hilbert de directions conjuguées
au sens où (pi , Apj ) = (Api , pj ) = 0 pour i 6= j tel que l’espace vectoriel fermé
engendré par la suite des pj est l’espace de Hilbert tout entier (c’est à dire
que tout élément de l’espace de Hilbert est limite d’une suite de combinaisons
linéaires finies des pj ).
La suite définie par
(
xn+1 = xn + λn pn
λn = (p(pn ,b−Ax n)
n ,Apn )
(b − Apn , pk ) = 0 pourk ≤ n − 1
et la suite ||xn −x0 ||2A est une suite décroissante positive. Elle a donc une limite.
Cette limite est 0 car la famille (pj ) est une famille complète. On en déduit que
la suite xn tend vers la solution du problème. La proposition est démontrée.
On remarque aussi que xn identifie déjà les n − 1 premiers termes de x0 .
Ce raisonnement n’est réellement applicable que lorsqu’on connait A donc
la forme quadratique. Dans le cas général, on va combiner cette méthode
avec une méthode de gradient afin de construire une suite par un procédé
d’orthogonalisation de Gram-Schmidt.
dn − x2 x2
Hn (x) = (−1)n (e 2 )e 2 .
dxn
On vérifie par récurrence que Hn est un polynôme de degré n dont le
monôme de plus haut degré est xn . En effet,
d x2 x2
Hn+1 (x) = − (Hn (x)e− 2 )e 2 = xHn (x) − Hn0 (x).
dx
Comme, par hypothèse, Hn est de degré n dont le monôme de plus haut
degré est xn (dans le raisonnement par récurrence), on sait que Hn0 est de degré
n − 1 donc xHn − Hn0 est de degré n + 1 et son terme de plus haut degré est
xn+1 . D’autre part, H1 (x) = 1 donc l’hypothèse de récurrence est vraie pour
n = 1.
On contrôle que
dp
Z 2
Z
x2
− x2
Hn (x)Hp (x)e dx = Hn (x)(−1)p p (e− 2 )dx.
IR IR dx
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 109
x2
et c’est donc une famille conjuguée pour l’application Af = f e− 2 .
d0 = −J 0 (x0 )
x1 = x0 + ρ0 d0
d0 = −J 0 (x0 )
La condition d’optimalité s’écrit
(J 0 (x1 ), d0 ) = 0.
On en déduit
(J 0 (x1 ) − J 0 (x0 ), d0 ) + (J 0 (x0 ), d0 ) = 0.
d1 = −J 0 (x1 ) + β1 d0 .
Ceci implique que l’on veuille trouver une direction conjuguée dans l’espace
vectoriel engendré par les gradients successifs (J 0 (x0 ), J 0 (x1 )). On a simplement
imposé que cette direction conjuguée soit telle que d1 + J 0 (x1 ) = 0. On verra
plus loin que cela ne restreint pas la généralité de faire ainsi.
Comme c’est une direction conjuguée, on trouve
(d1 , Ad0 ) = 0
soit
(J 0 (x1 ), Ad0 ) = β1 (Ad0 , d0 ).
On multiplie les deux membres de l’égalité par ρ0 , et on remarque que ρ0 d0 =
x1 − x0 , ce qui donne
|J 0 (x1 )|2
β1 = .
|J 0 (x0 )|2
La condition d’optimalité pour ρ1 s’écrit (J 0 (x2 ), d1 ) = 0. Comme de plus
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 111
(Ad2 , d1 ) = (Ad2 , d0 ) = 0.
On suppose que cette direction conjuguée appartient à l’espace vectoriel
engendré par la famille (J 0 (x0 ), J 0 (x1 ), J 0 (x2 )). Comme l’espace vectoriel en-
gendré par (J 0 (x0 ), J 0 (x1 )) est l’espace vectoriel engendré par (d0 , d1 ), on écrit
d2 = −J 0 (x2 ) + β20 d0 + β21 d1 .
Pour justifier cette forme, prenons une direction quelconque de V ect(J 0 (x0 ), J 0 (x1 ), J 0 (x2 )).
Comme l’espace vectoriel engendré par J 0 (x0 ), J 0 (x1 ) est le même que l’espace
vectoriel engendré par d0 , d1 , une direction quelconque est donc sous la forme
(J 0 (x2 ), d1 ) = 0
D’autre part, on a J 0 (x2 ) − J 0 (x1 ) = A(x2 − x1 ) = A(ρ1 d1 ), donc (J 0 (x2 ) −
J 0 (x1 ), d0 ) = 0 car (Ad1 , d0 ) = 0. Ainsi, comme par la condition d’optimalité
(J 0 (x1 ), d0 ) = 0 on en déduit que (J 0 (x2 ), d0 ) = 0. Comme J 0 (x2 ) est orthogonal
à l’espace vectoriel engendré par d0 et d1 , il est orthogonal à J 0 (x0 ) et à J 0 (x1 ).
112 CHAPTER 6. APPROXIMATION DE SOLUTIONS
β20 (d0 , Ad0 ) = (J 0 (x2 ), Ad0 ), β21 (d1 , Ad1 ) = (J 0 (x2 ), Ad1 ).
On multiplie respectivement chacune de ces égalités par ρ0 et par ρ1 et on utilise
ρ1 d1 = x2 − x1 , ρ0 d0 = x1 − x0 . Alors il vient
β20 (d0 , Aρ0 d0 ) = (J 0 (x2 ), A(x1 − x0 )), β21 (d1 , Aρ1 d1 ) = (J 0 (x2 ), A(x2 − x1 ))
β20 (d0 , Aρ0 d0 ) = (J 0 (x2 ), J 0 (x1 )−J 0 (x0 )), β21 ρ1 (d1 , Ad1 ) = (J 0 (x2 ), J 0 (x2 )−J 0 (x1 )).
On sait donc que J 0 (x3 ) est orthogonal à l’espace vectoriel engendré par
d0 , d1 , d2 donc est orthogonal à J 0 (x0 ), J 0 (x1 ), J 0 (x2 ).
Finalement le coefficient ρ2 est donné par
ρ2 (Ad2 , d2 ) + (J 0 (x2 ), d2 ) = 0
soit, utilisant d2 = −J 0 (x2 ) + β21 d1 et l’orthogonalité de d1 et de J 0 (x2 )
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 113
|J 0 (xp+1 )|2
βp+1 = .
|J 0 (xp )|2
|J 0 (xp )|2
ρp = − .
(J 0 (xp ), Adp )
• On commence par vérifier que J 0 (xn+1 ) est orthogonal à tous les autres.
Pour cela, on démontre que J 0 (xn+1 ) est orthogonal à tous les dp , 0 ≤ p ≤ n.
La première relation est la condition d’optimalité, qui s’écrit
(J 0 (xn+1 ), dn ) = 0
(et qui vient du fait que l’on minimise J(xn + tdn )). On utilise ensuite, pour
j ≤ n − 1, la relation
(J 0 (xj+1 ), dj ) = 0
et on trouve
soit
(J 0 (xn+1 ), dj ) = (A(ρn dn + .. + ρj+1 dj+1 ), dj )
et il suffit d’utiliser le fait que dj soit conjugué, par l’hypothèse de récurrence,
avec tous les dk , j +1 ≤ k ≤ n. On a donc démontré que J 0 (xn+1 ) est orthogonal
à tous les dj , j ≤ n. Comme l’espace vectoriel engendré par les dj , 0 ≤ j ≤ n
est le même que l’espace vectoriel engendré par les J 0 (xj ), 0 ≤ j ≤ n, on a le
résultat d’orthogonalité.
On construit donc xn+2 , dn+1 et ρn+1 comme suit. On veut que l’espace
vectoriel engendré par (J 0 (x0 ), .., J 0 (xp+1 )) soit aussi l’espace vectoriel engendré
par les directions (d0 , .., dp+1 ). On impose de plus que dp+1 = −J 0 (xp+1 )+lp , où
lp est dans l’espace vectoriel engendré par (d0 , .., dp ) qui est égal, par l’hypothèse
de récurrence, à l’espace vectoriel engendré par (J 0 (x0 ), .., J 0 (xp )).
114 CHAPTER 6. APPROXIMATION DE SOLUTIONS
Les directions sont conjuguées, donc (dn+1 , Adp ) = 0∀p. On en déduit donc que
n
j
X
βn+1 (dj , Adp ) = (J 0 (xn+1 ), Adp ).
j=0
Utilisant le fait que la famille de directions dj est conjuguée, il vient
p
βn+1 (dp , Adp ) = (J 0 (xn+1 ), Adp ).
On multiplie les deux membres de l’égalité par ρp et on utilise ρp Adp = J 0 (xp+1 )−
J 0 (xp ). Ensuite, comme la famille (J 0 (xk )), 0 ≤ k ≤ n + 1 est une famille or-
thogonale (ce qu’on a juste démontré), on en déduit que J 0 (xn+1 ) est orthogonal
à tous les J 0 (xp+1 ) pour p + 1 ≤ n et à tous les J 0 (xp ) pour p ≤ n. On en déduit
p
que βn+1 = 0 pour p 6= n. Il reste alors seulement un terme
n
βn+1 (dn , J 0 (xn+1 − J 0 (xn )) = (J 0 (xn+1 ), J 0 (xn+1 ) − J 0 (xn )) = |J 0 (xn+1 )|2
Comme d’autre part dn = −J 0 (xn ) + βn−1 dn−1 , utilisant le fait que dn−1 est
dans l’espace vectoriel engendré par J 0 (x0 ), .., J 0 (xn−1 ) donc est orthogonal à
J 0 (xn ) et à J 0 (xn+1 ), il reste
n
βn+1 (−J 0 (xn ), J 0 (xn+1 ) − J 0 (xn )) = |J 0 (xn+1 )|2
soit
n |J 0 (xn+1 )|2
βn = βn+1 = .
|J 0 (xn )|2
On a donc construit une direction dn+1 = −J 0 (xn+1 ) + βn dn telle que les
directions (dp ), 0 ≤ p ≤ n + 1 soient conjuguées.
Enfin, écrivons la condition d’optimalité. On a donc,
(Axn , dn )2
E(xn+1 ) = E(xn )[1 − ],
(Adn , dn )(xn , Axn )
On voit alors que (Axn , dn ) = (Axn , −Axn +βn−1 dn−1 ) = −(Axn , Axn ) car Axn
est orthogonal à dn−1 . Maximiser le facteur de réduction de l’erreur revient alors
2
à maximiser (Adn(Ax n ,dn )
,dn )(xn ,Axn ) , donc à minimiser (Adn , dn ). Comme
(Adn−1 ,Axn )
le minimum de cette fonction quadratique est obtenu pour βn−1 = (Ad n−1 ,dn−1 )
,
ce qui correspond à la formule obtenue précédemment en utilisant αn−1 dn−1 =
(A(xn −xn−1 ),Axn )
xn − xn−1 . En effet, αn1 dn−1 = xn − xn−1 donc βn−1 = (A(x n −xn−1 ),dn−1 )
. En
utilisant dn−1 = −Axn−1 + βn−2 dn−2 si n ≥ 2, d0 = −Ax0 , dn−2 est orthogonal
à Axn et à Axn−2 si n ≥ 2, donc (dn−1 , Axn − Axn−1 ) = (−Axn−1 , Axn −
||Axn ||2
Axn−1 ) = ||J 0 (xn−1 )||2 = ||r(xn−1 )||2 , et il reste βn−1 = ||Ax n−1 ||
2 . Le Corollaire
est démontré.
1
J(x, y, z) = (a2 x2 + b2 y 2 + c2 z 2 ).
2
Le point de départ est le point (x0 , y0 , z0 ). Le gradient en ce point est (a2 x0 , b2 y0 , c2 z0 ).
Les points de la droite de descente sont
x0 (1 − a2 t) = 0
y0 (1 − b2 t) = 0
z0 (1 − c2 t) = 0
1
φ(t) = (x20 (1 − a2 t)2 a2 + y02 (1 − b2 t)2 b2 + z02 (1 − c2 t)2 c2 )
2
qui atteint son minimum en t0 que l’on ne calculera pas.
Le gradient en ce point est alors
J 0 (x(1) ) = (a2 x0 (1 − a2 t0 ), b2 y0 (1 − b2 t0 ), c2 z0 (1 − c2 t0 ))
On trouve alors que la direction d1 , qui vaut d1 = −J 0 (x(1) ) + β0 d0 , est de
la forme
d1 = (αx0 , βy0 , γz0 ) = (a2 x0 (−1+a2 t0 +β0 ), b2 y0 (−1+b2 t0 +β0 ), c2 z0 (−1+c2 t0 +β0 ))
a2 + b2 2 a2 − b2 2
(λ − ) =1+( )
2 2
Pour pouvoir écrire la matrice comme précédemment, il faut diagonaliser la
matrice donc rechercher
q les vecteurs propres (e± , f± , 0) pour les deux valeurs
2 2 2 2
propres λ± = a +b2 ± 1 + ( a −b 2
2 ) .
L’algorithme du gradient conjugué converge en deux itérations dans les trois
cas suivants:
point de départ de la forme A(e+ , f+ , 0) + B(e− , f− , 0) = (x, y, 0),
point de départ de la forme A(e+ , f+ , 0) + C(0, 0, 1),
point de départ de la forme B(e− , f− , 0) + C(0, 0, 1).
dn+1 = −J 0 (xn ) + βn dn
βn = |J 0 (xn+1 |2
|J 0 (xn )|2
• algorithme de Polak-Ribiere
d = −J 0 (x0 )
0
xn+1 = xn + ρn dn
dn+1 = −J 0 (xn ) + βn dn
βn = (J 0 (xn+1 ,J 00(xn+12)−J 0 (xn ))
|J (xn )|
(H(v), φ, φ) ≥ αK ||φ||2 , ∀φ ∈ V, ∀v ∈ K
Théorème 6.7 Sous les hypothèses (H1), (H2), (H3), (H4), et (H5) ou (H6)
on a:
• Le problème de minimisation admet une solution unique u.
On considère u0 donné. Soit uk un élément de la suite. L’élément uk+1 est
construit comme uk + ∆k , où ∆k est la solution du problème variationnel
On utilise l’inégalité
Soit
U1 = {v ∈ V, ||v − w|| ≤ α−1 ||G||, w ∈ U }
Il vient uk+1 = uk + ∆k ∈ U1 .
• Il s’agit maintenant de contrôler le terme J(uk+1 ) par rapport au terme
J(uk ); On effectue un développement de Taylor pour J au voisinage de uk .
Ainsi
1
J(uk+1 ) − J(uk ) = (G(uk ), ∆k ) + (H(uk + θ∆k )∆k , ∆k )
2
d’où, en utilisant l’égalité (6.7.4) pour remplacer le terme (G(uk ), ∆k ):
1 1
J(uk+1 )−J(uk ) = − (H(uk )∆k , ∆k )−bk (∆k , ∆k )+ ([H(uk +θ∆k )−H(uk )]∆k , ∆k ).
2 2
On note β1 la constante de Lipschitz pour H sur U1 . Si on suppose uk ∈ U0 ,
on trouve uk + θ∆k ∈ U1 . Ceci permet de minorer le terme − 21 ([H(uk + θ∆k ) −
H(uk )]∆k , ∆k ). En utilisant la coercivité de H, on trouve l’inégalité
α β1 α β1
J(uk )−J(uk+1 ) ≥ ||∆k ||2 (1− ||∆k ||)+bk (∆k , ∆k ) ≥ ||∆k ||2 (1− ||∆k ||).
2 α 2 α
Deux cas se présentent. Dans cette inégalité, on doit contrôler le signe du
second membre.
β12
λ0 >
2α3
β1
||∆k || ≥
2λ0 α2
et donc
α
J(uk ) − J(uk+1 ) ≥ ||∆k ||2 .
2
En résumé, sous cette hypothèse sur λ0 , on trouve, pour tout ∆k
αC
J(uk ) − J(uk+1 ) ≥ ||∆k ||2 . (6.7.6)
2
• Dans le cas où J vérifie les hypothèses (H6) pour = 1, et si la constante
β2
lambda1 (que l’on suppose assez grande) vérifie λ1 > 8α13 , on vérifie que
8µ α3 −β 2
λ1 α2 ||∆k ||2 + α2 − β21 ||∆k || ≥ 16µ
0
0α
2
1
= δ0 > α2 , et donc J(uk )−J(uk+1 ) ≥
δ0 ||∆k ||2 (la condition sur λ1 est plus faible).
• Le raisonnement est le même si l’hypothèse (H6) est vérifiée. En effet,
on obtient
α β1
J(uk ) − J(uk+1 ) ≥ ||∆k ||2 (1 − ||∆k ||) + µ0 ||G(uk )||1+ ||∆k ||2 ,
2 α
et, utilisant (6.7.5), on obtient
α α β1
J(uk ) − J(uk+1 ) ≥ ||∆k ||2 [ − ||∆k ||) + µ0 α1+ ||∆k ||1+ ],
2 2 2
Lorsque µ0 grand, le minimum de cette fonction est strictement positif
α
pour tout > 0 (il s’écrit m2 − ψ()µ−
0 ), donc l’inégalité obtenue est
toujours valable.
122 CHAPTER 6. APPROXIMATION DE SOLUTIONS
(H(uk )δk+1 , φ)+bk (δk+1 , φ) = (H(uk )δk , φ)+bk (δk , φ)−(H(u+θ0 (uk −u))δk , φ)
une solution. D’autre part, dire que µ0 est assez grand est possible car on est
libre du choix de b pour le problème d’optimisation. On peut rapprocher cette
méthode des méthodes de pénalisation.
∀y ∈ K, (J 0 (x0 ), y − x0 ) ≥ 0.
(y − x0 , −αJ 0 (x0 )) ≤ 0
donc
∀y ∈ K, (y − x0 , x0 − αJ 0 (x0 ) − x0 ) ≤ 0
124 CHAPTER 6. APPROXIMATION DE SOLUTIONS
∀y ∈ K, (y − x0 , x0 − α0 J 0 (x0 ) − x0 ) ≤ 0
soit
∀y ∈ K, (y − x0 , J 0 (x0 )) ≥ 0
ce qui, par la caractérisation dans le cas convexe, implique que x0 est solution
du problème de minimisation.
On a même un résultat lorsque le pas de l’algorithme de gradient avec
projection est bien choisi:
||xn+1 − xn || → 0
Tous les points d’adhérence de cette suite sont des points stationnaires.
donc
1
(J 0 (xn ), xn+1 − xn ) ≤ − ||xn − xn+1 ||2 .
ρn
On utilise
6.8. ALGORITHMES D’OPTIMISATION AVEC CONTRAINTES 125
Z 1
0
J 0 (xn +t(xn+1 −xn ))−J 0 (xn ), xn+1 −xn dt.
J(xn+1 )−J(xn )−(J (xn ), xn+1 −xn ) =
0
R1
|J(xn+1 ) − J(xn ) − (J 0 (xn ), xn+1 − xn )| ≤ 0 ||J 0 (xn + t(xn+1 − xn )) − J 0 (xn )||||xn+1 − xn ||dt
R1
≤ L( 0 tdt||xn+1 − xn ||)||xn+1 − xn ||
≤ L2 ||xn+1 − xn ||2
L
J(xn+1 ) − J(xn ) − (J 0 (xn ), xn+1 − xn ) ≤ ||xn+1 − xn ||2
2
et de l’inégalité de caractérisation de la projection on déduit
1
(J 0 (xn ), xn+1 − xn ) ≤ − ||xn+1 − xn ||2
ρn
donc
L 1
J(xn+1 ) − J(xn ) ≤ ( − )||xn+1 − xn ||2 .
2 ρn
On utilise alors ρ1n ∈ [ L2 1−
1
, 1 ] soit L2 − 1
ρn ∈ [ L2 − 1 , − L2 1−
], donc finalement
la suite J(xn ) est décroissante et on a
L
||xn+1 − xn ||2 ≤ J(xn ) − J(xn+1 ).
2 1−
La suite J(xn ) est minorée et décroissante, donc elle converge. La décroissance
de la suite vient uniquement de l’hypothèse sur le pas... On en déduit que
J(xn+1 ) − J(xn ) tend vers 0, donc il en est de même de xn+1 − xn .
Enfin, si y est une valeur d’adhérence de la suite, xφ(n) tend vers y, dont
on déduit que xφ(n)+1 tend aussi vers y. De l’égalité xφ(n)+1 = pK (xφ(n) −
ρφ(n) J 0 ((xφ(n) )), on ne peut rien déduire car on ne sait pas si la suite ρφ(n)
converge. Il s’agit alors de remarquer que cette suite est bornée, donc on peut
extraire une sous-suite convergente, que l’on note ρφ(ψ(n)) . Elle converge vers
α > 0, et de la continuité de J 0 , de la continuité de la projection sur un convexe
fermé, on déduit l’égalité y = pK (y − αJ 0 (y)).
j=M
1 X
Jε (v) = J(v) + [max(Fj (v), 0)]2
ε
j=1
On a
lim uε = u.
ε→0
De plus, sous l’hypothèse J, F1 , .., FM continuement différentiables, les con-
traintes sont qualifiées en u, et la famille des contraintes actives est régulière
en u, les multiplicateurs de Lagrange λj du problème non pénalisé vérifient
2
λi = lim max(Fi (uε ), 0).
ε→0 ε
1 Pj=M
Preuve L’existence et l’unicité de u et de uε sont claires car u → ε j=1 [max(Fj (v), 0)]2 =
G(u)
ε est une fonctionnelle convexe.
On sait d’autre part que
J (u ) ≤ infK J ,
et comme, pour y ∈ K, J (y) = J(y), on vérifie que J (u ) ≤ J(u). Comme
d’autre part
J (u ) ≥ J(u )
on a l’inégalité J(u ) ≤ J(u). Comme J est α−convexe, la suite uε est bornée.
On peut extraire une sous-suite convergeant vers une limite ũ. De l’inégalité
J(uε ) ≤ J(uε ) + G(u ε
ε)
≤ J(u), on déduit l’inégalité G(uε ) ≤ ε(J(u) − J(uε )),
ce qui implique que G(ũ) = 0 (car G est continue donc G(uε ) tend vers G(ũ)
pour la suite extraite et que ε → 0). Cela exprime que ũ ∈ K. Ainsi comme
J(uε ) ≤ J(u), en considérant toujours la même suite extraite et la continuité
de J, on trouve J(ũ) ≤ J(u). On a démontré que ũ = u et donc la suite uε
admet une seule valeur d’adhérence.
Pour les multiplicateurs de Lagrange, on trouve, par définition de la dérivée
en un point x de (max(x, 0))2 qui vaut 2 max(x, 0), l’égalité
j=M
1 X
J 0 (uε ) + 2 max(Fj (uε ), 0)Fj0 (uε ) = 0.
ε
j=1
Comme J 0 , Fj0 sont continues, on trouve J 0 (uε ) → J 0 (u) et Fj0 (uε ) → Fj0 (u). On
suppose que pour un élément j, on ait Fj (uε ) → Fj0 (u) < 0. Alors il existe ε0
tel que, pour ε < ε0 , Fj (uε ) < 0 et donc on trouve max(Fj (uε , 0) = 0. L’égalité
devient, pour ε assez petit
6.8. ALGORITHMES D’OPTIMISATION AVEC CONTRAINTES 127
1 X
J 0 (uε ) + 2 max(Fj (uε ), 0)Fj0 (uε ) = 0.
ε
j∈I(u)
D’autre part, pour j ∈ I(u), on P vérifie qu’il existe une suite λ1 , ..λM , avec
/ I(u), telle que J 0 (u) + λj Fj0 (u) = 0. Ainsi on trouve
λj = 0 si j ∈
1 X
J 0 (uε ) − J 0 (u) + ( 2 max(Fj (uε ), 0) − λj )Fj0 (uε ) = 0.
ε
j∈I(u)
La famille (Fj0 (u) est libre, donc, par continuité, pour ε assez petit, la famille
(Fj0 (uε )
est libre. De plus, en formant le produit scalaire avec tous les Fj0 (uε ),
le déterminant du système obtenu est, toujours pour ε petit, minoré par une
constante. Ceci permet d’assurer le fait que 2ε max(Fj0 (uε , 0) est borné et donc
que
2
max(Fj0 (uε ), 0)(Fj0 (uε ) − Fj0 (u))
ε
tend vers 0 pour tout j. On en conclut sur la convergence, sur la base fixe des
Fj0 (u), de J 0 (uε ) + 2ε max(Fj0 (uε ), 0)Fj0 (u), d’où le résultat de convergence des
coefficients.
∀q, q ≥ 0, (p − q, F (u)) ≥ 0.
Il vient, pour µ > 0
uj+1
n = ujn + ∆x∂x u(j∆x, n∆t) + 21 (∆x)2 ∂x22 u(j∆x, n∆t) + 61 (∆x)3 ∂x33 u(j∆x, n∆t)
1
+ 24 (∆x)4 ∂x44 u((j + θ)∆x, n∆t).
uj−1
n = ujn − ∆x∂x u(j∆x, n∆t) + 21 (∆x)2 ∂x22 u(j∆x, n∆t) − 61 (∆x)3 ∂x33 u(j∆x, n∆t)
1
+ 24 (∆x)4 ∂x44 u((j − θ0 )∆x, n∆t).
129
130 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
(∆x)4 4
unj+1 +unj−1 −2ujn = (∆x)2 ∂x22 u(j∆x, n∆t)+ [∂x4 u(j+θ)∆x, n∆t)+∂x44 u(j−θ0 )∆x, n∆t)],
24
ainsi
uj+1
n + unj−1 − 2ujn (∆x)2 4
∂x22 u(j∆x, n∆t) = − [∂x4 u(j+θ)∆x, n∆t)+∂x44 u(j−θ0 )∆x, n∆t)],
(∆x)2 24
uj+1
n + uj−1
n − 2ujn (∆x)2 4
|∂x22 u(j∆x, n∆t) − | ≤ ||∂x4 u(j∆x, n∆t)||.
(∆x)2 12
.uN
n+1
1
J(x) = (Ax, x) − (b, x).
2
7.1. LES DIFFÉRENCES FINIES 131
ξ∆x ∆t
v n+1 (ξ) = (1 − 4 sin2 )v n (ξ).
2 (∆x)2
Le but est d’assurer la convergence de la suite pour tout n (c’est à dire
lorsque le temps devient grand).
132 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
• Dans le cas du schéma explicite, il est nécessaire pour cela que le coefficient
(1 − 4 sin2 ξ∆x ∆t
2 (∆x)2 ) soit de module plus petit que 1, soit l’inégalité
ξ∆x ∆t
4 sin2 > −2
2 (∆x)2
∆t 1
ce qui est possible lorsque le coefficient (∆x)2 est plus petit que 2 . Cette condi-
tion s’appelle une condition CFL et doit être vérifiée pour que la suite n’explose
pas lorsque ∆t tend vers 0 (ce qui est imposé par [0, T ] = ∪k≤ T [k∆t, (k+1)∆t]).
∆t
• Dans le cas du schéma implicite, le coefficient (1 + 4 sin2 ξ∆x ∆t −1
2 (∆x)2 ) est
toujours plus petit que 1 et le schéma implicite converge toujours.
Pour l’équation des ondes, la situation est similaire, sauf que la relation de
récurrence pour la suite est une relation d’ordre 2, et on doit étudier les racines
de la relation caractéristique. On trouve par exemple, pour le schéma explicite
ξ∆x ∆t 2 n+1
v n+1 (ξ) − 2(1 − 2 sin2 ( ) )v (ξ) + v n (ξ) = 0
2 ∆x
et pour le schéma implicite
ξ∆x ∆t 2
v n+1 (ξ)(1 + 4 sin2 ( ) ) − 2v n+1 (ξ) + v n (ξ) = 0.
2 ∆x
On constate pour le premier schéma que le produit des racines de l’équation
caractéristique est 1, donc le produit des modules est égal à 1. Si le discrim-
inant est négatif, les deux racines sont complexes conjuguées de module 1, si
le discriminant est positif, une des racines est de module supérieur à 1, donc il
n’y a pas convergence.
1
Pour le deuxième schéma, le produit des racines est 2 ξ∆x ∆t 2 et le dis-
1+4 sin 2
( ∆x )
criminant est négatif, elles sont donc complexes conjuguées de module inférieur
à 1 (égal à 1 lorsque ξ∆x = 2πn), donc ce schéma est convergent.
Ce schéma n’est pas employé en général; les numériciens préfèrent employer
le schéma de Cranck-Nicholson qui se présente de la manière suivante.
On introduit l’opérateur Ah qui est l’opérateur employé dans les algorithmes
précédents (le h correspond à ∆x). Cet opérateur s’écrit
un+1
j + un−1
j − 2unj
+ (Ah (θun+1 + (1 − 2θ)un + θun+1 ))j = 0.
(∆t)2
où θ ∈ [0, 12 ]. Le choix θ = 0 correspond à un schéma explicite comme vu
précédemment.
La transformée de Fourier appliquée à ce schéma comme cela a été fait
précedemment conduit à la relation de récurrence
7.1. LES DIFFÉRENCES FINIES 133
où
∆t 2 2 ξ∆x
α(ξ) = 4( ) sin
∆x 2
associée à l’équation caractéristique
(4θ − 1)α + 4 ≥ 0.
Lorsque θ ≥ 41 , cette inégalité est tout le temps vraie. Lorsque θ ∈ [0, 12 ], on
trouve que cette inégalité est vraie pour
∆t 2 2 ξ∆x 1
( ) sin ≤
∆x 2 1 − 4θ
ce qui est vrai sous la condition
∆t 1
≤√ .
∆x 1 − 4θ
On résume les résultats de cette section dans:
(∆x)2 (4)
|(Ah u)j + u”(j∆x)| ≤ ||u ||C 0 ([0,1]) .
12
2) Un schéma explicite pour l’équation de la chaleur s’écrit
un+1 − un
+ Ah un = 0.
∆t
Il est stable lorsque la condition suivante est satisfaite:
∆t 1
2
≤ .
(∆x) 2
134 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
un+1 − un
+ Ah un+1 = 0.
∆t
Il est tout le temps stable.
4) Un schéma explicite pour l’équation des ondes s’écrit
un+1
j + un−1
j − 2unj
+ (Ah un )j = 0.
(∆t)2
Il est tout le temps instable
5) Un schéma implicite pour l’équation des ondes s’écrit
un+1
j + ujn−1 − 2unj
+ (Ah un+1 )j = 0.
(∆t)2
Il est tout le temps stable.
6) Un schéma implicite pour l’équation des ondes respectant l’invariance
par renversement du temps est
un+1
j + un−1
j − 2unj
+ (Ah (θun+1 + (1 − 2θ)un + θun+1 ))j = 0.
(∆t)2
∆t 1
≤√ .
∆x 1 − 4θ
Z
< ∇u, ∇v >= f (x)v(x)dx
Ph = {u(x, y) ∈ H01 ([0, 1]×[0, 1]), continues, polynômes de degré 1 sur[ph, (p+1)h]×[qh, (q+1)h]}.
Son gradient est approché par (bp,q , cp,q ) et sa valeur sur X = ph est donnée par
ap,q + cp,q (Y − qh), sur X = (p + 1)h est donnée par ap,q + h + cp,q (Y − qh), sur
Y = qh est ap,q + bp,q (X − ph) et sur Y = (q + 1)h par ap,q + h + bp,q (X − ph).
On peut alors calculer l’intégrale du produit d’éléments de la base:
RhRh
11dxdy = h2
R0h R0h 3
1xdxdy = h2
R0h R0h 3
1ydxdy = h2
R0h R0h 2 4
x dxdy = h3
R0h R0h 4
0 0 xydxdy = h4
h4
RhRh 2
0 0 y dxdy = 3
ce qui fait que le produit de deux éléments a + bx + cy et a0 + b0 x + c0 y donne
h h h2
h2 [aa0 + (ab0 + a0 b + ac0 + a0 c) + (bc0 + b0 c) + (bb0 + cc0 ) ]
2 3 4
136 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
ainsi la matrice de la forme quadratique associée (en divisant par h2 pour plus
de simplicité) est
1 h2 h
h h2 h22
2 4 3 .
h h2 h2
2 3 4
Il est clair que c’est une forme quadratique définie positive puisque
Z hZ h
(a + bx + cy)2 dxdy = 0 ⇒ a = b = c = 0.
0 0
On utilise donc cette représentation des fonctions de H 1 par des des polynômes
de degré 1.
La présentation ainsi faite n’est pas satisfaisante; en effet un carré ou un
rectangle a quatre sommets, et un polynôme de degré 1 a trois coefficients.
Ainsi on ne pourra pas construire une fonction générale prenant quatre valeurs
données en tous les coins ABCD; il faut nécessairement que
Si on veut construire une famille qui conduise à toutes les valeurs possibles aux
points du carré, il faut considérer les fonctions de la forme
donc b = u(1, 0) − u(0, 0), c = u(0, 1) − u(0, 0), d = u(1, 1) + u(0, 0) − u(0, 1) −
u(1, 0), et cette famille permet de construire une solution dont les valeurs
données sont les valeurs au coin.
Les valeurs aux sommets s’appellent les degrés de liberté d’une fonction
de l’espace d’approximation. Dans le pavé [0, 1]×[0, 1], on construit les sommets
de l’approximation aij = (ih, jh) et la base de l’espace d’approximation Vh (φij )
des fonctions telles que
Cette présentation fait partie d’un cadre plus général d’approximation, dont
on résume les résultats:
∀v ∈ H, a(u, v) = L(v).
Une méthode d’approximation s’obtient par le processus suivant: on définit
une suite d’espaces vectoriels de dimension finie Vh , associée à un paramètre
h tendant vers 0, dont on connait une base simple Bh , ayant les propriétés
suivantes
i) pour tout élément v de H on peut construire une suite vh ∈ Vh telle que
|v − vh |H → 0 lorsque h → 0
ii) Le calcul de a(φ, ψ) pour φ et ψ dans Bh est simple.
Alors si uh est le minimum de 21 a(u, u) − Lh (u) sur Vh , dans certaines
conditions uh → u.
138 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
Chapter 8
139
140 CHAPTER 8. RESUME
• convexe si
• strictement convexe si
• α convexe si
Théorème 8.2 . Si J est convexe, tout minimum local est global, et l’ensemble
des solutions optimales est convexe.
Corollaire 8.1 . Soit K un convexe fermé non vide, J une fonction définie
sur K à valeurs dans R, α-convexe continue. Alors le problème de minimisation
admet une solution et une seule. De plus toute suite minimisante converge vers
u.
Remarque 8.3 Par le théorème de Riesz puisque J 0 (u) est dans V 0 , il existe
un unique élément de V noté ∇J(u) tel que pour tout v dans V on ait
J 0 (u) · v = (∇J(u), v)
Exemples de base
1. Les formes linéaires J(u) = (c, u), où c est un vecteur donné dans V .
Alors J 0 (u).v = (c, v), ∇J(u) = c.
2. Les fonctions J(u) = a(u, u), où a est une forme bilinéaire continue sur V .
Alors J 0 (u).v = a(u, v) + a(v, u), et si a est symétrique J 0 (u).v = 2a(u, v).
Pn ∂J
3. Si V = Rn , J 0 (u) = ( ∂x
∂J
1
(u), · · · , ∂J
∂x n
(u)) et J 0 (u).v =
i=1 ∂xi (u)vi .
2. J(u) = a(u, u), alors J 00 (u).v.w = a(v, w) + a(w, v), et si a est symétrique
J 00 (u).v.w = 2a(v, w). Si V = Rn , J(u) = 21 (Au, u) où A est une matrice
symétrique, alors J”(u) = A pour tout u.
∂2J
3. Si V = Rn , J 00 (u) est la matrice des dérivées partielles secondes ∂xi ∂xj (u).
2. Si J est différentiable,
∀u, v ∈ V, (J 0 (v) − J 0 (u)) · (v − u) ≥ α k v − u k2 , (8.2.12)
En particulier les fonctionnelles de la forme J(u) = a(u, u), où a est une forme
bilinéaire symétrique continue sur V sont α-convexes si et seulement si
∀u ∈ V, 2a(w, w) ≥ αkwk2
Si l’on est dans Rn , avec J(u) = 12 (Au, u), ceci revient à
∀u ∈ V, (Aw, w) ≥ αkwk2
La matrice A étant symétrique, elle diagonalise en base orthonormée, A =
P DP T , où D est la matrice des valeurs propres di et P la matrice des vecteurs
propres. On a alors
n
X n
X
2
(Aw, w) = di ((P w)i ) > (min1≤i≤n di ) ((P w)i )2
i=1 i=1
∀w ∈ V, J 00 (u)w.w ≥ α k w k2 ,
Corollaire 8.2 [Projection sur un convexe fermé]. Soit K une partie convexe
fermée non vide d’un espace de Hilbert V , et w un point de V n’appartenant
pas à K. alors il existe un unique point de K, noté PK w tel que
(
PK w ∈ K,
kw − PK wk = inf kw − vk (8.3.15)
v∈K
1. K = V On a le
144 CHAPTER 8. RESUME
M ? = {c ∈ V, ∀v ∈ M, (c, v) ≥ 0} (8.3.21)
K(v) = {0} ∪ {w ∈ V,
vk −v w
∃{vk }k∈N ⊂ K lim vk = v, vk 6= v pour tout k, lim = ||w|| }
k→+∞ k→+∞ ||vk −v||
(8.3.24)
Définition 8.2 . Les contraintes sont régulières en u ∈ K si les Fi0 (u) sont
linéairement indépendantes. On dit alors que u est un point régulier.
alors
m
X
L0v (v, q) ≡ ∂L
∂v (v, q) = J 0 (v) + qi Fi0 (v)
i=1
(8.3.29)
L0q (v, q) ≡ ∂L
∂q (v, q) = F (v)
et
u ∈ K ⇔ ∀q ∈ Rm , L0v (u, q) = 0
(8.3.30)
u minimum local ⇔ ∃p ∈ Rm , L0q (u, p) = 0
∃w̄ ∈ V, ∀i ∈ I(u), (Fi0 (u), w̄) < 0 ( resp. ≤ 0 si Fi est affine). (8.3.32)
nous avons associé de façon naturelle un lagrangien dans les cas suivants :
K = {v, F (v) ≤ 0} ; L : K × Rm
+ →R
(8.4.37)
K = {v, F (v) = 0} ; L : K × Rm → R
où F : V → Rm , et
Lemme 8.3 .
sup inf L(v, q) ≤ inf sup L(v, q) (8.4.39)
q∈P v∈U v∈U q∈P
et pour v dans K,
Remarque 8.10 .
◦
1. Si aucune des Fi n’est affine, la définition 8.5 se résume à K 6= ∅. Si
toutes les Fi sont affines, elle signifie que K 6= ∅.
m
X
0 (u) + pi Fi0 (u) = 0
J
(Th 8.14)
u solution optimale de (8.1.2) =⇒ ∃p ∈ Rm
+ m
X
i=1
pi Fi (u) = 0
i=1
m
X
0 pi Fi0 (u) = 0
J (u) +
i=1 (8.4.45)
m
X
pi Fi (u) = 0
i=1
Algorithmes
8.5.1 Principe
On se place dans un espace de Hilbert V , et on cherche à calculer numériquement
un x (qui n’est pas forcément unique) tel que
xk+1 = xk − ρk dk (8.5.47)
ou encore
xk,1 = (xk1 − ρ1 , xk2 , .., xkn )
On note xk+1
1 = xk1 − ρ1
2. à l’étape i on a
xk,i = (xk+1 k+1 k
1 , .., xi , xi , .., xkn )
3. xk+1 = xk,n
Remarque 8.11 . Dans le cas où J est quadratique, i.e. J(v) = 12 (Av, v) −
(b, v), on retrouve l’algoritme de Gauss-Seidel ou S.O.R. pour la résolution du
système linéaire Ax = b.
∇J(xk ).∇J(xk+1 ) = 0.
(rk ,dk )
ρk = (Adk ,dk )
(8.6.49)
et l’on a (rk+1 , dk ) = 0.
Notons E(v) = 12 (A(v − u), v − u), on a alors
1 (rk ,dk )2
γk = 2 (Adk ,dk )(A−1 rk ,rk ) . (8.6.51)
rk dk 2
k , k
||r || ||d ||
>µ>0 (8.6.52)
µ
alors γk > γ = K(A) (où K(A) est le conditionnement de A, c’est-à-dire le
rapport de la plus grande à la plus petite valeur propre), et donc
154 CHAPTER 8. RESUME
Remarque 8.14 . Plus la matrice est bien conditionnée (i.e. K(A) proche de
1), plus la convergence est rapide. Plus la matrice est mal conditionnée (i.e.
K(A) >> 1), plus la convergence est lente.
et on a le
Théorème 8.24
Par exemple, d’après ces estimations pour K(A) = 100, pour obtenir une
erreur de 10−6 , il faudrait 340 itérations du gradient à pas optimal et seulement
34 itérations du gradient conjugué ! Comme les itérations sont comparables, ces
performances font de cet algoritme le favori de tous les gens qui font des calculs
de grande taille. De nombreuses extensions ont été proposées : BiCGSTAB,
GMRES, etc, pour des problèmes non symétriques, à coefficients complexes,
etc..
et pour q dans K ∗ , G(q) = inf L(v, q). Le problème dual associé s’écrit :
v∈U
[1] J.C. Culioli: Optimisation: Cours à l’Ecole des Mines publié aux éditions
Ellipses (1994)
[8] G. Allaire: cours à l’Ecole Polytechnique (publié aux éditions Ellipse, 2005)
159