Cours Optimisation Lafitte
Cours Optimisation Lafitte
Olivier Lafitte12
1
Institut Galilée, Université de Paris XIII
2
Commissariat à l’Energie Atomique, Centre d’études de Saclay, lafitte@[Link]
2
Contents
1 Introduction et exemples 5
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Exemples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Euler-Legendre 17
2.1 Condition générale d’existence (suffisante) . . . . . . . . . . . . . . . . 17
2.2 Condition d’Euler, condition de Legendre . . . . . . . . . . . . . . . . 18
2.2.1 Dérivabilité au sens de Fréchet et au sens de Gâteaux . . . . . 18
2.2.2 Conditions necessaires d’optimalité. Conditions suffisantes d’optimalité 20
2.3 Inéquation d’Euler dans un problème avec contraintes . . . . . . . . . 21
2.4 Multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . . . . . . . 22
4 Programme convexe 41
4.1 Fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.2 Minimisation de fonctionnelles convexes . . . . . . . . . . . . . . . . . 46
4.3 Fonctionnelles quadratiques . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4 Notion de point selle, et théorème de Kuhn et Tucker . . . . . . . . . 48
4.4.1 Introduction à la notion de Lagrangien . . . . . . . . . . . . . . 48
4.4.2 Point selle, lagrangien, et minimisation de fonctionnelle convexe 50
4.4.3 Principe du Min-Max . . . . . . . . . . . . . . . . . . . . . . . 52
5 Equation de Hamilton-Jacobi-Bellmann 55
6 Approximation de solutions 63
6.0.4 Algorithme de relaxation . . . . . . . . . . . . . . . . . . . . . 63
6.1 Algorithmes de descente . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.2 Cas classiques d’algorithmes de descente . . . . . . . . . . . . . . . . . 67
6.2.1 Pas optimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3
4 CONTENTS
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 exemple
(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 exem-
ple) 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 com-
mande 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 con-
trainte, comme un algorithme où on recherche un optimum sur N variables 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.
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
5
6 CHAPTER 1. INTRODUCTION ET EXEMPLES
1.2 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∈IR N 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
On diagonalise A qui est symétrique définie positive, on écrit x = x0 + i yi ei ,
P
1 1 1 i=N
λi yi2 .
X
(Ax, x) − (b, x) = − (b, x0 ) +
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é.
Je vais décrire sommairement un algorithme dans ce cas: l’algorithme qui consiste à minimiser sur
chaque coordonnée. On vérifie que (A(1, 0...0), (1, 0...0)) = a11 donc a11 > 0 (matrice définie positive).
Ainsi le minimum, x2 , ..xn étant fixés, de la fonction quadratique en x1 est obtenu pour a11 x1 +
Pi=N
i=2
ai1 xi − b1 = 0, et sa valeur est
1 X X 1 X
f (x2 , ..xn ) = aij xi xj − bj xj − (b1 − a1j xj )2 .
2 2a11
i,j≥2 i≥2 j≥2
Il s’agit à nouveau d’une forme quadratique que l’on peut minimiser en x2 . On itère le procédé.
inf |f (x)|2 .
x∈IRM
normales. On remarque que c’est un espace affine passant par d dirigé par
ker t BB = ker B.
Une autre méthode plus directe: on diagonalise t BB dans une base orthonormée, les valeurs propres
étant 0 ≤ λ1 ≤ ... ≤ λM associées aux vecteurs propres (e1 , ...eM ). Alors on introduit p (éventuellement
il n’existe pas) tel que λp = 0 et λp+1P> 0. Alors (e1 , ...ep ) forme une base de ker t BB, donc de ker B.
On constate alors qu’en écrivant x = y e , on trouve
i i i
X X
(t BBx, x) − 2(t Bc, x) = λi yi2 − 2 (t Bc, ei )yi .
i>p i
(Av, v)
λ1 = inf (Av, v) = inf .
N
v∈IR ,||v||=1 IR N
−{0} (v, v)
d 1 dui
− ( ) = fi (x), ∀x, ui (0) = ui (1) = 0 (1.2.1)
dx a(x) dx
XZ 1
inf |ui (x) − ūi (x)|2 dx. (1.2.2)
a∈A 0
i
soit
Z x Z x
ui (x) = CA(x) + A(x) fi (t)dt − A(t)fi (t)dt
0 0
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
Z 1 Z x
u1i (x) =x (t − 1)fi (t)dt + (x − t)fi (t)dt.
0 0
Z 1 Z 1 Z 1
2
J(a) = a (u1i (t))2 dt − 2a u1i (x)ūi (x)dx + (ūi (x))2 dx
0 0 0
Pi=N R 1 1
u (t)ūi (t)dt
et qu’il est minimum en a0 = Pi=1
i=N
R0 1 i 1 . Son minimum, d’après les inégalités de Cauchy-
2 (ui (t)) dt
i=1 0
Schwarz, est positif ou nul et n’est nul que si tous les u1i sont égaux à un coefficient foit ūi .
Notons que cette égalité, dans le cas du plan, implique que (v − p(u0 ), u0 −
p(u0 )) ≤ 0, c’est-à-dire l’angle entre les vecteurs joignant la projection à u0 et à
un élément quelquonque de K est obtus.
Réciproquement, si cette inégalité est vérifiée, alors
||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 con-
sidère v = v0 . Alors
(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.
Posons les inconnues de ce problème. On suppose que le joueur joue xi sur chaque cheval. P Son gain
est alors yi0 = xi0 ri0 si le cheval i0 l’emporte. Pour simplifier notre analyse, on suppose xi = 1 (on
mise 1) et on veut qu’il existe une combinaison de sorte que chaque yi soit plus grand que 1. Ainsi on
a
X yi X yi X 1
= 1, yi ≥ 1∀i ⇒ 1 = ≥ .
ri ri ri
i i
1
P
Ainsi la condition 1 ≥ ri
est nécessaire pour que le gain soit au moins égal à la mise.
1
P
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
rp
1 1 1
xi = ri
P 1
. Dans ce cas, le gain est P 1
pour tout i; il est donc plus grand que 1.
rp rp
j=N
X i=M
X
vij ≥ 0, vij ≤ si , vij ≥ rj
j=1 i=1
Ainsi l’inf existe et est strictement positif. Il faut voir si cette valeur est atteinte.
Pour cela, il faut cj rj = i cij vij , donc si les cij sont ordonnés et distincts, tous
P
les vij sont nuls sauf celui correspondant au plus petit des cij , où il vaut rj .
On peut écrire la solution explicite dans le cas M = N = 2 et sous la condition de compatibilité
r1 + r2 ≤ s1 + s2 (on ne peut pas livrer plus que ce que l’on a). On trouve alors
On n’a même pas besoin de se poser les questions de vij entier. D’autre part, lorsque deux sont égaux,
on peut choisir les quantités arbitrairement. On note ainsi que l’on se trouve donc sur le bord du
domaine défini par les contraintes.
dy(v)
(t) = Ay(v)(t) + Bv + f (t)
dt
RT
(v(t), v(t))dt + 0T (Q(y(v)(t) − g(t)), y(v)(t) − g(t))dt
R
J(v) = 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. On
aura un principe dans la suite du cours.
1.2. EXEMPLES 11
Commander le système en temps minimal est trouver inf J pour v dans l’espace
de commande et trouver un v0 tel que J(v0 ) = inf J.
Z l Z x1 1
l= ds = (1 + (y 0 (x))2 ) 2 dx.
0 x0
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
Z x1 1
inf y(x)(1+ (y 0 (x))2 ) 2 dx, (1+ (y 0 (x))2 ) 2 dx = l, y(x0 ) = y0 , y(x1 ) = y1 .
y∈C 0 x0 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
1
Z
U1 (v) = λ |∇v|2 dx
2 Ω
1
Z
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 potentielle
é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).
Cette inégalité se traduit par
Z
∀φ ∈ C0∞ (Ω), λ ∇u∇φ + J2 (φ) ≥ 0.
Ω
1.2. EXEMPLES 13
choisit alors −ψ, pour obtenir λ Ω ∇u∇ψ − f ψ = 0∀ψ ∈ C0∞ (Ω). Un résultat
d’intégrations par parties indique que, au sens des distributions de H −1 (Ω) (dual,
rappelons le, des distributions de H01 (Ω)), on a la relation
−λ∆u = f
Réciproquement, lorsque u est dans H01 (Ω) solution dans H −1 (Ω) de ce problème,
alors par écriture du produit scalaire qui correspond à la dualité des distribu-
tions, on trouve
1
Z
J2 (v) − J2 (u) = λ (∇v − ∇u)2 dx.
2
14. Un exemple simple avec contraintes.
On veut trouver min( 21 v 2 − cv) sous la contrainte v ≤ b. Pour cela, on voit que,
si b ≤ c, minv≤b ( 12 v 2 − cv) = ( 21 v 2 − cv)|v=b et si b > c, minv≤b ( 12 v 2 − cv) =
( 12 v 2 − cv)|v=c . Dans le premier cas, la contrainte est saturée, dans le deuxième
cas elle est insaturée.
−λ∆u + ku = f.
Remplaçant alors cette égalité dans l’inégalité (1.2.3), on trouve, pour tout v ∈
K: Z
U1 (v − u) + U2 (v − u) + [λ∇u∇v + kuv − f v]dx ≥ 0
Ω
R R
On remplace f par −λ∆u+ku et on utilise la relation ∆uvdx = − Ω ∇u∇vdx+
1 1
R
Ω ∂n uvdσ (qui est une manière de définir ∂n u pour u ∈ H (Ω) et v ∈ H (Ω)
comme le résultat d’un théorème de Riesz)1 .
R
La relation obtenue est alors ∀v ∈ K, Γ ∂n uv|Γ dσ ≥ 0.
Nous avons pu ici étudier le problème facilement car la fonctionnelle est une
forme quadratique. Dans le cas où elle ne l’est pas, il s’agit d’étudier u + ψ, et
on vérifie que si x ∈ Γα où Γα est la partie du bord où u est supérieur ou égal
à α, alors on peut prendre ψ tel que ψ = 0 sur Γ − Γα et |ψ| ≤ α2 sur Γα , ψ
identiquement égale à 1 sur le bord dans un voisinage d’un point x0 de Γα . On
peut alors vérifier que u + ψ et que u − ψ sont dansR K, ce qui permet d’obtenir
directement, avec v − u = ±ψ, la relation au bord Γ ∂n uψdσ = 0, ce qui donne
∂n u = 0 sur Γα . On a donc
Z
∀α > 0, ∂n uΓα = 0, u∂n udσ = 0
Γ
ce qui permet de partitionner Γ en Γ1 = {x,
R
u(x) = 0} et Γ2 = Γ0 = Γ − Γα , sur
lequel ∂n u = 0, et on a, par la condition Γ ∂n uvdσ ≥ 0 pour tout v, v|Γ ≥ 0, la
condition ∂n u ≥ 0.
1
J(un ) =
6n2
et inf J = 0, alors qu’il n’existe pas de u tel que J(u) = inf J.
1
R
On introduit la fonctionnelle v → Ω ∇u∇v+ < ∆u, v >. Lorsque v ∈ C ∞ (Ω), il est clair que
cette fonctionnelle est continue et que, par dualité, comme u ∈ H 1 (Ω), ∆u ∈ H −1 (Ω) lorsque le bord
est régulier, on trouve
Z
| ∇u∇v+ < ∆u, v > | ≤ C||v||H 1 (Ω) .
Ω
Pour v = φ ∈ C0∞ (Ω), on trouve 0, donc c’est une distribution qui ne considére que les valeurs au
bord de v = φ. D’autre part, lorsque u ∈ H 2 (Ω), on trouve que cette fonctionnelle permet de définir
la dérivée normale de u, ∂n u par la formule de Green usuelle.
Finalement, pour u ∈ H 2 (Ω) et v ∈ C ∞ (Ω), il existe C1 telle que (on améliore la relation précédente)
Z
| ∇u∇v+ < ∆u, v > | ≤ C1 ||v|Γ || 1 .
H 2 (Γ)
Ω
1.2. EXEMPLES 15
inf J(y), a1 y1 + a2 y2 = 0
inf J(y), a1 y1 + a2 y2 ≤ 0
1 a2 b2 a1 − b1 a2
inf (1 + 12 )y12 − y2
2 a2 a1
−b1 a2 −b1 a2
qui est atteint au point y2 = a1 b2 aa21 +a2 et donc y1 = −a2 b2 aa21 +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 deux cas. Notons avant cela que le minimum absolu de la fonc-
tionnelle 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.
Lorsque on suppose que b n’est pas dans la zone a.y > 0, on trouve que b0 = b−λa
avec λa2 ≤ 0 et λ ≤ 0. Le minimum est alors obtenu en b et on a b = b + 0a.
On voit sur cet exemple et sur la notion de projection que l’on forme y − b + λa
et a.y = 0. Lorsque la résolution de ce système conduit à λ ≤ 0, on dit que la
contrainte est insaturée et on a y = b comme minimum. Le point de minimum
est dans l’espace des contraintes. Lorsque la résolution du système conduit à
λ ≥ 0 , la contrainte est saturée et y = b − λa convient.
Chapter 2
Théorème 2.1 Soit K ⊂ IRN , soit J une fonctionnelle continue sur Ω contenant 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 convergeant vers
un point de minimum sur K.
17
18 CHAPTER 2. EULER-LEGENDRE
Définition 2.1 Lorsque, pour tout w, la limite limε→0 1ε [J(u + εv) − 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 continue,
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 δ
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 continues.
On rappelle la définition de la dérivée au sens de Fréchet, qui n’est plus cette fois
une forme linéaire définie sur chaque direction:
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 si J est deux fois
différentiable au sens de Fréchet:
1
J(u + v) = J(u) + (J 0 (u), v) + (J”(u)v, v) + o(||v||2 ) (2.2.1)
2
Si J est diff’erentiable au sens de Fréchet et si sa dérivée est différentiable au sens
de Gateaux, alors on a aussi une formule de Taylor:
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
On vérifie que
φ(t + h) − φ(t)
→ (J 0 (u + tw), w)
h
ainsi φ0 (t) = (J 0 (u + tw), w).
0 0 (0) 0 0 (u),w)
On voit alors que φ (t)−φ t = (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
ainsi la formule de Taylor avec reste intégral pour la fonction φ conduit à l’égalité
(2.2.3).
Avec les outils de differentiabilité ainsi définis, on peut donner les résultats d’optimalité
connus soul le nom de condition d’Euler et de Legendre.
20 CHAPTER 2. EULER-LEGENDRE
∀w ∈ V, (J”(u)w, w) ≥ 0.
(condition de Legendre)
Démonstration:
On vérifie que, si u est un point d’optimum de J, alors, pour tout v ∈ V on a
J(u + v) ≥ J(u).
Si on utilise la dérivée de Fréchet de J, on en déduit que
∀v ∈ V, Lu (v) + o(v) ≥ 0.
On écrit v = tw, et on fait tendre t vers 0, t > 0. On en déduit , par passage à la
limite, Lu (w) ≥ 0. On choisit alors v = −tw, t > 0 et on en déduit Lu (−w) ≥ 0. On
a alors, ∀w, Lu (w) = 0. Ceci équivaut à J 0 (u) = 0.
Pour la condition de Legendre, on suppose que la fonctionnelle est dérivable au
sens de Fréchet et que sa dérivée de Fréchet est différentiable au sens de Gateaux.
On utilise alors la formule de Taylor (2.2.2), ce qui donne, si u est un minimum,
utilisant J 0 (u) = 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 de u0 , on ait la condition (J”(ũ)w, w) ≥ 0. (condi-
tion forte de Legendre)
2.3. INÉQUATION D’EULER DANS UN PROBLÈME AVEC CONTRAINTES 21
De manière opératoire, on peut aussi écrire une condition plus forte que la condition
forte sous la forme
Il existe α > 0 tel que (J”(u)w, w) ≥ α(w, w)1 .
Démontrons le théorème. On suppose que J 0 (u) = 0 et (J”(ũw, w) ≥ 0 pour tout
ũ dans un voisinage de u, et J deux fois Fréchet différentiable. Alors en utilisant la
formule de Taylor avec reste intégral
Z 1
J(u + tw) = J(u) + t2 (1 − x)(J”(u + txw)w, w)dx
0
et l’hypotèse sur la dérivée seconde qui implique que, pour tout ũ dans ce voisinage
de u, on choisit t = 1 et w = ũ − u de sorte que u + txw = xũ + (1 − x)u est dans ce
même voisinage, alors J(ũ) ≥ J(u) et u est un point de minimum local, ce qu’il fallait
démontrer.
Notons que l’on n’a pas ainsi de condition nécessaire et suffisante. En effet, si on
considère dans V = IR J(x) = x6 (1 + sin x1 ), et J(0) = 0, on vérifie que J(x) ≥ 0
car sin u ≥ −1. Ainsi J(x) ≥ J(0) pour tout x et 0 est un point de minimum
absolu. On vérifie que J est continue en 0 (car lim x sin x1 = 0). Sa dérivée est
J 0 (x) = 6x5 (1+sin x1 )−x4 cos x1 , elle vérifie J 0 (x) → 0 lorsque x tend vers 0, et de plus,
J(x)−J(0)
x tend vers 0, donc J est dérivable et sa dérivée est continue. Alors J”(x) =
−x2 [sin x1 − 30x2 (1 + sin x1 ) − 10x cos x1 ]. On vérifie que J”(0) = 0 et que J”( (n+11 )π ) =
2
−( (n+11 )π )2 [(−1)n − 30( (n+11 )π )2 (1 + (−1)n )], dont le signe est alternativement + et −
2 2
pour n pair ou impair assez grand (par exemple n ≥ 4). Ceci prouve que J ne vérifie
pas la condition forte de Legendre et pourtant J admet un minimum absolu en 0.
Définition 2.3 L’espace des directions admissibles au sens de Fréchet est l’ensemble
des w de V est une direction admissible pour u sur K si il existe une suite wn de V
tendant vers w et une suite en ≥ 0 telle que u + en wn ∈ K. L’ensemble des directions
admissibles est noté K(u).
Définition 2.4 L’espace des directions admissibles au sens de Gâteaux est l’ensemble
des w tels que, pour ε assez petit, u + εw soit dans K. L’ensemble de telles directions
w est aussi appelé ensemble de directions admissibles intérieures et noté K̇(u).
1
Notons que dans un Hilbert de dimension finie, cette inégalité est équivalente à l’inégalité
(J”(u)w, w) > 0 pour tout w non nul, puisque dans ce cas là la matrice J”(u) n’a pas de vecteur
propre nul, et α est sa plus petite valeur propre
22 CHAPTER 2. EULER-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 fonctionnelle
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.
(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.
0. Comme on prend quelconque assez petit, la norme de w est nulle donc w = 0. On trouve
K̇((x, y, z)) = {(0, 0, 0)}.
D’autre part, considérons maintenant la définition de K((x, y, z)). Alors w ∈ K((x, y, z))
lorsqu’il existe une suite en tendant vers 0 et une suite wn = (w1n , w2n , w3n ) tendant vers w
telles que (x, y, z) + en wn soit dans la sphère. On cherche des conditions nécessaires pour que
cela soit le cas. Comme précédemment, on écrit les deux égalités et on obtient
en n 2
xw1n + yw2n + zw3n = − ||w || .
2
En considérant la limite lorsque n tend vers l’infini, le membre de gauche tend vers xw1 +yw2 +
zw3 et le membre de droite tend vers 0, donc une condition nécessaire est xw1 +yw2 +zw3 = 0.
Montrons que cette condition est suffisante. On se donne un élément (w1 , w2 , w3 ) tel
que u.w = 0, u = (x, y, z). On considère alors une suite quelconque wn qui tend vers w
(c’est toujours possible à définir, ce serait-ce qu’en prenant w + n1 e, où e est un vecteur fixe
quelconque). On sait alors que [Link] tend vers 0. On construit alors w̃n = wn −2|[Link] |(x, y, z)
(ceci veut dire w̃1n = wn1 − 2|xwn1 + ywn2 + zwn3 |x, w̃2n = wn2 − 2|xwn1 + ywn2 + zwn3 |y). Il en
découle que w̃n tend vers w car wn tend vers w et [Link] tend vers 0. De plus, w̃n .(x, y, z) =
w̃ n
w̃n .u = wn .u − 2|wn .u| ≤ 0. On construit alors en = − ||2u n
w̃ n ||2 ≥ 0. La suite (en , w̃ ) vérifie les
conditions de la définition, donc (w1 , w2 , w3 ) ∈ K(u) (exemple 1).
Exemple1
Si K = {(x, y, z), x2 + y 2 + z 2 ≤ 1}, alors K(u) = K̇(u) = IR3 pour u = (x, y, z) tel
que x2 + y 2 + z 2 < 1 (en effet, il suffit, pour toute direction non nulle w, de considérer
u + 21 (1 − ||u||) ||w||
w
, qui est dans la sphère unité, donc on vérifie que pour 0 = 21 (1−||u||)
||w|| et
2
< 0 , u + w est dans la sphère). Pour un point du bord u = 1, on aboutit, en divisant par
en ou par , à l’inégalité
en n 2
u.w ≤ − ||w||2 , [Link] ≤ ||w ||
2 2
ce qui aboutit aux relations K̇(u) = {u.w < 0} et K(u) = {u.w ≤ 0}.
Nous généralisons ces expressions. Commençons par une contrainte égalité F (v) =
0 (exemple 1). Ainsi w est une direction admissible pour u si il existe une suite wn
tendant vers w et une suite en > 0 tendant vers 0 telles que F (u + en wn ) = 0. Alors
on en déduit, en supposant que F est différentiable
Faisant tendre en vers 0 après avoir utilisé F (u) = 0 et avoir divisé par en conduit à
(F 0 (u), w) = 0.
24 CHAPTER 2. EULER-LEGENDRE
φ(λ + 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 + λ0 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, mais cela n’assure pas
l’existence d’un w non nul qui soit une direction admissible. 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 Le cône K(u) associé à u tel que F (u) = 0 est, dans le cas F 0 (u) 6= 0
l’ensemble des w ∈ V tels que (F 0 (u), w) = 0.
Définition 2.5 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 con-
Lemme 2.2 Si les contraintes sont régulières en u, alors K(u) = {w ∈ V, (Fi0 (u), w) =
0∀i = 1..m}.
On regarde alors ce système comme une application de IRM dans lui même.
Le jacobien de cette application est, pour ε = 0, la matrice des produits scalaires
(Fj0 (u), Fk0 (u)). La famille est libre, donc cette matrice est inversible et cette propriété
est vraie pour ε < ε0 lorsque les µj appartiennent à un compact. On applique alors le
théorème des fonctions implicites de IRM dans IRM et on conclut. Lorsque les vecteurs
Fi0 (u) ne forment pas une famille libre, on a le même problème que précédemment dans
le cas F 0 (u) = 0. On ne peut pas assurer l’existence de directions admissibles. Par
exemple, si on considère l’ensemble x2 + y 2 = 1, x3 + y 3 = 1 admet comme solutions
(1, 0), (0, 1) et ces points sont isolés donc leurs directions admissibles sont réduites à
{0}. On peut aussi considérer l’exemple d’une sphère S et d’un de ses plans tangents
P . Au point d’intersection, les deux vecteurs Fi0 (u) sont égaux à la direction normale
à la sphère, et l’intersection est réduite au point.
Lorsque le cône K(u) est facile à évaluer, le théorème 2.4 permet de calculer ce
que l’on appelle les multiplicateurs de Lagrange.
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.4), il
faut qu’il existe m réels λ1 , ...λm tels que
∀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 scalaires λj et un vecteur r,
orthogonal à tous les Fj0 (u), tels que J 0 (u) = − m 0
P
j=1 λj Fj (u) + r. Alors r ∈ K(u) et
0
(J (u), r) = 0, ce qui s’écrit (r, r) = 0 soit r = 0.
26 CHAPTER 2. EULER-LEGENDRE
Un travail identique peut être fait pour les contraintes inégalités. On suppose donc
F (u) ≤ 0 une contrainte donnée de V dans IR. Soit u ∈ K, vérifiant ainsi F (u) ≤ 0.
Une direction w de K(u) est alors telle que F (u + εw) ≤ 0 pour ε assez petit, soit
F (u) + ε(F 0 (u), w) + o(εw) ≤ 0.
Deux cas sont alors à envisager:
• soit F (u) < 0, auquel cas, dès que ε est assez petit, tout élément w est admissible.
La contrainte F (u) ≤ 0 n’ajoute donc pas de condition dans le théorème 2.4, la
condition nécessaire est donc l’égalité d’Euler J 0 (u) = 0 qui provient de (J 0 (u), w) ≥
0∀w ∈ K(u). On dit pour cette raison que la contrainte est inactive (on dira aussi de
temps en temps insaturée).
• soit F (u) = 0, auquel cas, comme ε > 0, il faut et il suffit, dans le cas F 0 (u) 6= 0,
que (F 0 (u), w) ≤ 0.
On note tout de suite que si (F 0 (u), w) < 0, alors il est clair que, pour ε assez petit,
F (u + εw) = ε(F 0 (u), w) + o(ε) < 0. Le problème se pose lorsque (F 0 (u), w) = 0 pour
trouver un élément de l’espace des contraintes. On doit donc introduire une notion
de plus grande régularité des contraintes.
Par exemple la condition F 0 (u) 6= 0 est assurée lorsqu’il existe w tel que (F 0 (u), w) <
0.
D’autre part, lorsqu’il y a plusieurs contraintes inégalités, on veut pouvoir montrer
que l’ensemble des directions admissibles n’est pas vide.
Pour cela, il faut trouver un w0 tels que, pour toutes les contraintes Fj saturées,
on a (Fj0 (u), w0 ) ≤ 0.
Cette condition n’est pas assez restrictive. En effet, la définition des directions ad-
missibles w conduit à la relation (Fj0 (u), w) ≤ 0. En revanche, si on 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 (exemple 2):
Exemple 2
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, (Fj (u), w0 ) < 0.
Cette condition est peu utilisable, car trop restrictive; en particulier une contrainte
affine pourra donner une direction admissible avec uniquement l’égalité. On utilise
alors plutôt la condition suivante:
Il existe w0 tel que ∀j, (Fj (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
2.4. MULTIPLICATEURS DE LAGRANGE 27
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 (qui est non pas automatique, mais
inutile: voir exemple 3). Exemple 3
Cette étude induit une définition de contraintes qualifiées, qui est une hypothèse
technique mais qui est l’hypothèse la plus classique en théorie des multiplicateurs de
Lagrange:
Commençons par ranger les contraintes actives affines pour j ∈ I 0 (u). On prend
w0 dans l’orthogonal de l’espace vectoriel F0 engendré par les Fj0 (u), j ∈ I 0 (u), qui est
indépendant de u. Il suffit alors de voir que, pour tout w0 ∈ F0 et pour tout j ∈ I 0 (u),
on a Fj (u + w0 ) = Fj (u) = 0. Il suffit alors de regarder, pour les autres conditions,
(j ∈ I(u) − I 0 (u)), (Fj0 (u), w0 ) et K(u) est non vide lorsque w0 existe.
Une notion moins restrictive mais plus abstraite est la notion de contraintes
qualifiables:
Définition 2.7 On dit que les contraintes inégalités {Fj (u) ≤ 0} sont qualifiables 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.4), il
faut qu’il existe λ1 , ...λm ≥ 0 tels que λj = 0 pour j ∈ {1, .., m} − I(u) et
i=m
0
λi Fi0 (u) = 0.
X
J (u) +
i=1
de B converge vers v, on peut identifier les λni associés, et les suites λni sont bornées.
Quitte à faire des extractions de suite en cascade, il existe une sous-suite convergente
ψ(n)
λi , qui converge vers des valeurs positives λi , donc v = − λi ai . La limite est
P
donc dans B.
2.4. MULTIPLICATEURS DE LAGRANGE 29
Deuxième cas, si la famille est linéairement dépendante, il existe µ1 , ..µm tels que
P
µi ai = 0 (avec au moins 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,
P
construction ci-dessus, pour chaque n, il existe i(n) tel que − λi ai = − i6=i(n) λ̃ni ai .
P n P
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
φ(m)
Ii est infini, soit Ii = {φ(m), m = 0, 1..+∞}. La suite extraite xφ(n) = − i6=i0 λ̃i
P
ai
est une suite 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é.
1 i=n 1 1 i=n 1
|xi |p ) p ≤ ( |xi |q ) q , q ≥ p
X X
(
n i=1 n i=1
En effet, on suppose la contrainte |xi |q = 1 et on cherche à minimiser J(x) =
P
forment la base du calcul classique des variations. Les méthodes que nous verrons
montrent en quel sens le mot “variations” doit être entendu.
En 1696, Leibniz a résolu le problème de la brachistochrone. Il faut trouver
la courbe qui réalise le minimum du temps de parcours entre deux points (x1 , y1 ) et
(x2 , y2 ) dans un même plan vertical lorsque le point matériel glissant est soumis à
la force de pesanteur. Ce problème avait été posé par J. Bernoulli1 . Ce problème
peut être facilement résolu car les contraintes peuvent être intégrées à une intégrale
première. Cependant, après sa publication, des problèmes plus géneraux ont été
énoncés sous le nom général de problèmes isopérimétriques, et on peut les résumer
en “quelles sont les courbes de longueur donnée qui entoure la plus grande surface?”.
Le premier de ces problèmes est légendaire, comme nous l’avons rappelé dans l’exemple
11 (Problème de Didon). En effet, Didon, descendante des Troyens et fuyant sa cité
après la chute de Troie, a demandé à Jarbas, roi des terres africaines, la terre que pou-
vait recouvrir une peau d’un bœuf. Ce roi, ne pensant pas à une quelconque astuce,
accepta et Didon découpa la peau d’un bœuf en de fines lanières, qu’elle attacha entre
elles (et si on suppose que la largeur de la lanière était d’un millimètre, la longueur
obtenue était donc de 1000S). Elle forma la plus grande surface enclose par cette
lanière s’appuyant sur la côte méditerranéenne, et fonda Carthage, la grande rivale de
1
Problema novum, ad cujus solitionem mathematici invitantur
31
32 CHAPTER 3. CALCUL DES VARIATIONS
Rome2 .
J. Bernoulli demanda à un de ses élèves, le mathématicien L. Euler, de résoudre ce
problème, ce qu’il fit en 17443 , par une méthode de série, suivi en 1755 par Lagrange,
qui inventa la méthode classique de calcul des variations. Continuant ses travaux,
Lagrange introduisit ses multiplicateurs en 1797.
∂y
(x, ε)
η(x, ε) =
∂ε
(ce qui explique le nom de calcul des variations). On se ramène donc à une fonction
de ε:
J 0 (0) = 0.
Par application du théorème de dérivation sous le signe intégral, et en remarquant
∂ ∂y
que comme y est de classe C 2 , alors ∂ε
∂
(y 0 (x, ε)) = ∂x ( ∂ε (x, ε)) = η 0 (x, ε), on obtient
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
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
2
Delenda Cartago est! (Caton)
3
Methodus inveniendi lineas curvas maximi minimive proprietate gaudentes, sive solutio problema-
tis isoperimetrici latissimo sensu accepti
3.2. PROBLÈMES ISOPÉRIMÉTRIQUES 33
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, cepen-
dant, 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.
La démonstration intuitive la plus facile est de voir comment varie l’action lorsque
l’intégrale d’action est minimale, soit
d 0
dx (f (y0 , y0 )) = ∂y f (y0 , y00 )y00 + ∂y0 f (y0 , y00 )y000
d
= dx (∂y0 f (y0 , y00 ))y00 + ∂y0 f (y0 , y00 )y000
d
= dx (y00 ∂y0 f (y0 , y00 )).
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
34 CHAPTER 3. CALCUL DES VARIATIONS
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, on vérifie aisément que, pour w ∈ H 1 ([x1 , x2 ]), après intégration par
parties, on trouve
(J 0 (y0 ), w) = xx12 ( ∂f 0 d ∂f 0
R
∂y (x, y0 , y0 ) − dx ( ∂y 0 (x, y0 (x), y0 (x))))w(x)dx
∂f ∂f
+ ∂y0 (x2 , y0 (x2 ), y00 (x2 ))w(x2 ) − ∂y0 (x1 , y0 (x1 ), y00 (x1 ))w(x1 ).
J 0 (y0 ) = ∂f 0 d ∂f 0
∂y (x, y0 , y0 ) − dx [ ∂y 0 (x, y0 (x), y0 (x))]
∂f ∂f
+ ∂y0 (x2 , y0 (x2 ), y00 (x2 ))δx2 − ∂y0 (x1 , y0 (x1 ), y00 (x1 ))δx1 .
L’emploi des multiplicateurs de Lagrange pour des contraintes égalités, qui sont re-
spectivement F1 (y) = y(x1 ) − y1 et F2 (y) = y(x2 ) − y2 , ce qui donne F10 (y0 ) = δx1 et
F20 (y0 ) = δx2 , conduit à
∂f ∂f
λ1 = 0
(x1 , y0 (x1 ), y00 (x1 )), λ2 = − 0 (x2 , y0 (x2 ), y00 (x2 )). (3.2.3)
∂y ∂y
Cette égalité aura une très jolie interprétation ci-dessous.
y0 + ε1 η1 + ε2 η2 .
On introduit dans η1 et η2 lesR contraintes d’extrémité Rsous la forme ηi (xj ) = 0,
i, j = 1, [Link] écrit alors que I = xx12 f (x, y, y 0 )dx et C = xx12 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 d
R x2 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
0
x1 (∂y g − dx (∂y g))η2 dx
0
(par application du théorème 2.5). Ainsi on trouve immédiatement, sans avoir besoin
de considérer des variations qui se compensent:
d d
∂y f − dx (∂y0 f ) + λ(∂y g − dx (∂y0 g))
+(λ1 − ∂y f (x1 , y1 , y0 (x1 )) − λ∂y g(x1 , y1 , y00 (x1 )))δx1
0
d y0
1= (λ )
dx (1 + (y 0 )2 ) 12
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 . On
1 1
identifie λ en écrivant y(x2 ) = y2 , soit (λ − x22 ) 2 − (λ − x21 ) 2 = y1 − y2 , ce qui permet
1 1
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π .
36 CHAPTER 3. CALCUL DES VARIATIONS
d ∂f ∂f
( (x, y0 , y00 )) = (x, y0 , y00 )
dx ∂y 0 ∂y
et les équations sur les contraintes
1
lε (u1 , u2 ) = [(u1 − y1 )2 + (u2 − y2 )2 ].
ε
Soit y0 la solution du problème de minimisation de J(y) = xx12 f (x, y, y 0 )dx avec
R
1 1
m(Ẋ(T ))2 + U (X(T )) = m(Ẋ(0))2 + U (X(0)).
2 2
Cette égalité s’écrit comme la conservation de l’énergie. Ce n’est pas celle ci que l’on
souhaite obtenir, mais on cherche à interpréter le problème comme la solution d’une
3.4. FORMULATION HAMILTONIENNE 37
1
f (X, Ẋ) = m(Ẋ)2 − U (X).
2
On vérifie que l’équation d’Euler dans ce cas est bien l’équation dite loi de Newton.
On en déduit que
La solution des équations du mouvement d’une particule dans un champ
de forces conservatif, c’est-à-dire dérivant d’un potentiel, est la fonction
qui minimise l’intégrale d’action
Z t1 1
Z t1
A(X) = [ m(Ẋ(t))2 − U (X(t))]dt = (T − U )dt.
t0 2 t0
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)
λ1 = −∂q̇ L(q0 , q̇0 )(t1 )
λ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
dans le cas L convexe en q̃ conduit à la première égalité p = ∂q̇ L(q, q̃), ce qui porte un
nom: transformation de Legendre. Revenant au cas où L dépend de t (car ceci n’est
pas essentiel pour cette partie de l’analyse), soit
∂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
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
Soit L une action (un lagrangien) de la forme L(t, q(t), q̇(t)). Lorsque q(t) est une
fonction donnée, L est une fonction de t uniquement. Lorsque on veut considérer les
problèmes d’intégrale d’action, on se ramène à la fonctionnelle de IR × IRd × IRd dans
IR qui à (t, q, q̃) fait correspondre L(t, q, q̃).
On a démontré la proposition suivante, dans le cas où L est une fonction stricte-
ment convexe dans les variables (q, q̃):
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))
p0 (0) = p0 , q0 (0) = q0
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 ).
Ce système hamiltonien est très couramment utilisé en optique, mais il faut modifier pour
cela la formulation de l’exemple 12 de l’introduction. En effet, l’équation d’Euler devient alors
d y 0 (x) 0 2 12 ∂y c
( 1 ) = −(1 + (y (x)) ) (3.4.4)
dx c(x, y(x))(1 + (y (x)) ) 2
0 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 1 ∂x c
( = −(1 + (y 0 (x))2 ) 2 2 . (3.4.5)
dx c(x, y(x))(1 + (y 0 (x))2 ) 12 c
40 CHAPTER 3. CALCUL DES VARIATIONS
~
t
Les deux relations (3.4.5) et (3.4.4) expriment que c a sa dérivée qui suit le gradient de
1
c , les rayons suivent le gradient de l’indice.
1
(1+(y 0 )2 ) 2
D’autre part, le hamiltonien équivalent au lagrangien c(x,y(x)) ne peut pas être calculé,
car le lagrangien n’est pas strictement convexe.
1
(1+(y 0 )2 ) 2
Pour se ramener à un lagrangien strictement convexe, on considère que le terme c(x,y(x))
est un double produit, donc on a
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̇12 +q̇22 w2
Nous allons faire le raisonnement sur Lw (q1 , q2 , q̇1 , q̇2 ) = w 2 + c2 (q1 ,q2 ) . En effet, Lw (q1 , q2 , q̇1 , q̇2 ) ≥
1
Lw0 (q1 , q2 , q̇1 , q̇2 ) pour w0 qui réalise le minimum en w, c’est à dire w02 = c(q̇12 + q̇22 ) 2 . Dans
ce cas on sait que d’une part
t2 t2 1
(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
t2 1 t2
(q̇12 + q̇22 ) 2 1 q̇12 + q̇22
Z Z
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
dyds = pc
2
ds = qc
dp 2 2
ds = −c∂x c(p + q )
dq 2 2
ds = −c∂y c(p + q )
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
= 2 p2 1
dx
du
(p +q ) 2
dy
q
du = 1
(p2 +q2 ) 2
dp = ∂ 1
xc
du
dq
1
du = ∂ y c.
Le vecteur d’onde suit les courbes intégrales du gradient d’indice. Ceci correspond à une
théorie d’optique géométrique, comme cela avait été vu ci-dessus .
Chapter 4
Programme convexe
Définition 4.1 Soit K un ensemble convexe non vide (c’est-à-dire vérifiant, pour
tout u, v dans K et tout réel β de [0, 1], βu + (1 − β)v ∈ K.) On dit que la fonction
J définie sur K est une fonction convexe si et seulement si on a
Lemme 4.1 Si J est α−convexe et continue, elle est strictement convexe. De plus,
αθ(1 − θ)
J(θu + (1 − θ)v) ≤ θJ(u) + (1 − θ)J(v) − ||u − v||2 .
2
41
42 CHAPTER 4. PROGRAMME CONVEXE
αθ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.
On a les résultats suivants:
Proposition 4.1 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 con-
1
verge vers (λ, v) dans l’espace de Hilbert IR × V muni de la norme (λ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).
On remarque aussi que si J(v) ≤ a pour tout a valeur d’adhérence de la suite
J(vn ), alors on a (λ, v) qui est dans l’épigraphe, et l’épigraphe est fermé.
On remarque alors que le Lemme suivant est vrai
4.1. FONCTIONS CONVEXES 43
La notion de continuité plus faible évoquée dans ce lemme porte le nom de semi
continuité inférieure (et on note parfois J s.c.i.).
Reprenons la démonstration de la proposition.
Soit v0 ∈ K et λ0 < J(v0 ).
On note ce point p0 , qui 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),
l’inégalité (λ − λ0 )2 + (v − v0 )2 ≥ (λ∗ − λ0 )2 + (w0 − v0 )2 .
On suppose v = w0 , auquel cas pour λ ≥ J(w0 ) on a (λ − λ0 )2 ≥ (λ∗ − λ0 )2 . On
sait que λ∗ ≥ J(w0 ). Si J(w0 ) ≥ λ0 , on trouve λ ≥ J(w0 ) ⇒ λ ≥ λ0 , donc λ ≥ λ∗
pour λ ≥ J(w0 ) et on en déduit J(w0 ) ≥ λ∗ et comme (λ∗ , w0 ) est dans l’épigraphe,
λ∗ = J(w0 ).
Si J(w0 ) < λ0 , le point (λ0 , w0 ) est dans l’épigraphe, donc on trouve (λ∗ −λ0 )2 ≤ 0,
donc λ∗ = λ0 .
Dans le cas où J est continue, il existe θ tel que J(θv0 + (1 − θ)w0 ) = λ0 , puisque
J(v0 ) < λ0 < J(w0 ). Alors, pour ce θ, on trouve
(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.
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
On utilise alors le fait que α8 ||v − v0 ||2 + L(v)
2 est quadratique en +∞ pour voir que
cette fonction est minorée par
α α
||v||2 − [||L|| + ||v0 ||]||v||
8 4
qui peut être minoré par α4 ||v||2 − C1 , d’où le résultat.
La relation entre les fonctionnelles convexes et les problèmes de minimisation est
la suivante:
Proposition 4.2 Soit J une fonctionnelle convexe sur un ensemble convexe K. Tout
point de minimum local est un point de minimum global, et les points de minimum
forment un ensemble convexe. Cet ensemble convexe est réduit à un point lorsque J
est strictement convexe
α
J(v) ≥ J(u) + (J 0 (u), v − u) + ||v − u||2
2
ou par
α
J(u + θ(v − u)) ≤ J(u) + θ(J(v) − J(u)) − θ(1 − θ)||u − v||2 .
2
Ainsi
α
J(v) ≥ J(u) + (J 0 (u), v − u) + ||v − u||2
2
α
J(u) ≥ J(v) + (J 0 (v), u − v) + ||v − u||2
2
et on les additionne pour trouver la deuxième inégalité.
Enfin, considèrant u vérifiant la deuxième inégalité, on veut étudier φ(t) = J(tu +
(1 − t)v).
On voit que φ0 (t) = J 0 (tu + (1 − t)v), u − v). On en déduit φ0 (t) − φ0 (s) = J 0 (tu +
1
(1 − t)v), u − v) − J 0 (su + (1 − s)v), u − v) = t−s [J 0 (tu + (1 − t)v − J 0 (su + (1 − s)v), tu +
(1− t)v − su− (1− s)v)]. Lorsque t ≥ s, on trouve bien φ0 (t)− φ0 (s) ≥ α||v − u||2 (t − s).
Intégrant de s = 0 à s = 12 et de t = 12 à t = 1, on trouve
1 1
Z 1 1 1 α
[φ(1) − 2φ( ) + φ(0)] ≥ α||u − v||2 [ t − ]dt = ||u − v||2 .
2 2 1
2
2 8 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)].
α
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
Cette proposition est une conséquence du fait que, pour u ∈ K, toutes les directions
admissibles sont v − u pour v ∈ K, car u + θ(v − u) est dans K pour 0 < θ < 1.
On a
u minimum de J ⇔ ∀v ∈ K, (J 0 (u), v − u) ≥ 0.
4.3. FONCTIONNELLES QUADRATIQUES 47
∀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
(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.
1
J(v) = a(v, v) − (b, v)
2
où a est une forme bilinéaire continue sur V et b est un élément de V .
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
Lemme 4.3 Si a est coercive, et qu’une de ses constantes de coercivité est ν, alors a
est ν−convexe.
ce qui entraine
Théorème 4.3 Le minimum de J sur K convexe est unique et noté u. C’est l’unique
solution du problème
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
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.
4.4. NOTION DE POINT SELLE, ET THÉORÈME DE KUHN ET TUCKER 49
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 fonctionnelle. 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,
50 CHAPTER 4. PROGRAMME CONVEXE
et on vérifie que ce minimum vaut − 21 (b − λa)2 . Cette fonction de λ admet un maximum en λ = a.b
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.
Dans le cas des contraintes inégalités, on désigne par P = (IR+ )M , et dans le cas
de contraintes égalités, on note P = (IRM ). Soit U ⊂ V
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
Proposition 4.6 Si les fonctions J, F1 , ...FM sont continues sur V et si (u, p) est
un point selle de L sur U × P . Alors, K étant défini par les contraintes Fj (égalité si
P = IRM , inégalités si P = (IR+ )M , et K ⊂ U , on a
• l’élément u est dans K
• c’est un minimum global de J sur K
• Dans le cas où K est inclus dans l’intérieur de U , et où les fonctionnelles sont
dérivables, on a
M
J 0 (u) + pj Fj0 (u) = 0.
X
j=1
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 com-
posante, que F (u) ≤ 0. On trouve alors pF (u) ≥ 0 par l’inégalité, et comme Fj (u) ≤ 0,
4.4. NOTION DE POINT SELLE, ET THÉORÈME DE KUHN ET TUCKER 51
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 propo-
sition donne une condition nécessaire et suffisante d’optimalité
Preuve On considère un point de minimum global sur K. Soit I(u) l’ensemble des
indices où les contraintes sont actives, qui est, rappelons le, l’ensemble des indices tels
que Fi (u) = 0. La convexité de Fi entraine que
p
∀(µ0 , µ) ∈ A, µ0 − J(u) + µ>0
p0
Comme A = ∪v∈V ]J(v), +∞[×]Fj (v), +∞[, il vient
p
∀v, J(v) − J(u) + F (v) ≥ 0.
p0
p
Finalement, si v = u on en déduit p0 F (u) ≥ 0, donc comme pj ≥ 0 et Fj (u) ≤ 0 on
trouve pp0 F (u) = 0 donc on trouve
p p
∀v ∈ V, J(v) + ( , F (v)) ≥ J(u) + ( , F (u)) ≥ J(u) + (q, F (u))∀q, qj ≥ 0.
p0 p0
i=1
(ce qui est équivalent à + i∈I(u) λi Fi0 (u) = 0 où I(u) est l’ensemble des con-
J 0 (u)
P
On veut montrer que (u, λ) est un point selle pour le Lagrangien, d’où on déduira
que u est un minimum global donc que u est le minimum global.
La fonctionnelle L(v, λ) est convexe. De plus, on a la relation λj Fj (u) = 0, donc
∀v ∈ K,
La condition nécessaire et suffisante est démontrée.
∀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)
˜
∀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
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 formulation
est que les contraintes s’écrivent vraiment simplement: en l’occurence elles sont sous
la forme q ≥ 0.
Chapter 5
Equation de
Hamilton-Jacobi-Bellmann
(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
(π̇(t)x(t) + π(t)fx (x(t), u(t), t))dt = 0.
0
55
56 CHAPTER 5. EQUATION DE HAMILTON-JACOBI-BELLMANN
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
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
J(u) = 01 g(x(t), u(t), t)dt + C(x(1))
R
inf
ẋ(t) = f (x(t), u(t), t), x(0) = x0
admet une commande optimale v(x, t), qui minimise en v à chaque instant
∂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
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.
Ainsi f1 (x, y, u, t) = y, f2 (x, y, u, t) = −(1 − εu(t))x et Ẋ = f . D’autre part, on
introduit le multiplicateur de Lagrange (p, q) associé à (x, y). Il n’y a pas d’équation
de contrôle sur u.
Le Lagrangien est alors
Après intégration par parties en temps, on trouve les équations adjointes pour p
et q de sorte que ce Lagrangien ait un extremum (point selle). Il s’agit de
donc −xẋ(t1 ) < 0. On peut positionner le point d’arriver dans le quatrième quadrant
(x > 0, y < 0).On écrit x(t1 ) = cos α, y(t1 ) = sin α, α ∈] − π2 , 0[. Ainsi on trouve
q(t1 ) = cos(α + π2 ), p(t1 ) = sin(α + π2 ). Le point (p(t), q(t)) est, dans un voisinage de
p2 2α
t1 , sur l’ellipse q 2 + 1−ε = a2 = sin2 α + cos1−ε , et le point (x(t), y(t)) est sur l’ellipse
y 2 2 2 2
x2 + 1−ε = b2 = cos2 α + sin α 2
1−ε . On contrôle que a =
1−ε sin α
1−ε et b2 = 1−ε1−ε
cos α
.
Dans ce qui suit, on va construire une trajectoire ’en remontant le sens du temps’
à partir du point d’arrivée. PLus précisément, on adopte la démarche suivante:
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 [:
On commence par donner la forme des fonctions x et q. On trouve x(t) = b cos((1−
1 1 1
ε) 2 (t − t1 )+ β), ẋ(t) = y = −b(1− ε) 2 sin((1− ε) 2 (t − t1 )+ β), d’où on déduit β ∈]0, π2 [
et tan β = − tan α1 .
(1−ε) 2
On suppose que le système reste dans l’état excité avec u = 1. On sait que q(t) =
1 1
a cos((1 − ε) 2 (t − t1 ) + γ) avec γ ∈] − π2 , 0[, a cos γ = − sin α, a(1 − ε) 2 sin γ = cos α.
1
On en déduit γ ∈] − π2 , 0[ et tan γ = 1 . On contrôle alors que ab cos(γ − β) =
(1−ε) 2 tan α
ε sin α cos α
1−ε< 0, donc, ajoutant le fait que γ − β ∈] − π, 0[, il vient γ − β ∈] − π, − π2 [.
On remarque que ab sin(γ − β) = − 1 1 .
(1−ε) 2
1
Soit T tel que (1 − ε) (T − t1 ) + β = π2 . On en déduit que, pour t ∈]t1 , T ],
2
1
γ + (1 − ε) 2 (t − t1 ) décrit ]γ, γ + π2 − β] ⊂] − π2 , 0], avec
π 1 π
q(T ) = a cos(+ γ − β), q̇(T ) = −a(1 − ε) 2 sin( + γ − β).
2 2
Lorsque l’on introduit ρ(α) et ω(α) tels que q(T ) = ρ(α) cos ω(α) et q̇(T ) =
1
ρ(α) sin ω(α), on obtient tan ω(α) = −(1− ε) 2 tan( π2 + γ − β), ce qui donne tan ω(α) =
2 sin2 α cos2 α
−ε cos α sin α. De plus, (ρ(α))2 = a2 sin2 (γ−β)+a2 (1−ε) cos2 (γ−β) = 1+ε1−ε cos2 α
.
1 1
De plus ẋ(T ) = −b(1 − ε) 2 = −(1 − ε cos2 α) 2 .
On commence à remonter le temps à partir de t = T . On écrit
1
x(t) = b cos((1 − ε) 2 (t − T ) + π2 )
1
q(t) = a cos((1 − ε) 2 (t − T ) + π2 + γ − β).
Comme π2 + γ − β ∈] − π2 , 0[, on voit qu’en remontant le sens du temps, le premier
point òu le produit qx change de signe est atteint pour q au temps t2 tel que
1 π π
(1 − ε) 2 (t2 − T ) + +γ−β =− .
2 2
1
Le contrôle est u = 1 pour t ∈]t2 , T [, et q̇(t2 ) = a(1 − ε) 2 . On vérifie aussi que
60 CHAPTER 5. EQUATION DE HAMILTON-JACOBI-BELLMANN
π 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
• 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
1
x(t) = ρ(α) ab 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
On trouve donc β(α) ∈] − π, − π2 [ et tan β(α) = − ε sin α cos
1
α
.
(1−ε) 2
Le point où q(t) s’annule (qui est le premier point inférieur à t3 où xq change de
signe) est donné par
1 3π
(1 − ε) 2 (t4 − t3 ) + β(α) = − .
2
On a
x(t4 ) = −µ(α) cos ω(α), ẋ(t4 ) = −µ(α) sin ω(α),
avec
b cos2 β(α) (1 + ε2 cos2 α sin2 α)
(µ(α))2 = (ρ(α) )2 ( + sin2 β(α)) = .
a 1−ε (1 − ε + ε2 cos2 α sin2 α)(1 − ε sin2 α)
• 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̃ ) = −µ(α).
61
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 α
en ayant utilisé 1 − ε + ε2 cos2 α sin2 α = (1 − ε cos2 α)(1 − ε sin2 α).
ẋ(t2 ) ẋ(t4 ) ẋ(t)
On vérifie alors que x(t 2)
= tan ω(α), x(t 4)
= tan ω(α) et limt→T,t<T x(t) = +∞,
ẋ(t) ẋ(t) ẋ(t)
limt→t3 ,t>t3 x(t) = −∞, limt→t3 ,t<t3 x(t) = +∞, limt→T̃ ,t>T̃ x(t) = −∞.
ẋ(t)
On a ainsi vu que le contrôle est donné par u(t) = H( x(t) − tan ω(α)), où H
désugne la fonction de Heaviside.
62 CHAPTER 5. EQUATION DE HAMILTON-JACOBI-BELLMANN
Chapter 6
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
enfin
inf J(un+1
1 , un+1
2 , v3 ) = J(un+1
1 , un+1
2 , un+1
3 ).
v3 ∈V3
63
64 CHAPTER 6. APPROXIMATION DE SOLUTIONS
1 1
x1 + x2 = α, x2 + x1 = β
2 2
soit
4 2 4 2
x01 = α − β, x02 = β − α.
3 3 3 3
L’algorithme de relaxation consiste à partir du point (x, y) quelconque, puis à
déterminer le point où J(x1 , y) est minimum (c’est donc x11 = α − 21 y), évaluer le point
x2 où J(x11 , x2 ) est minimum, soit x12 = β − 12 x11 , et donc étudier la suite récurrente
1 1
xn+1
1 = α − xn2 , xn+1
2 = β − xn+1 .
2 2 1
On obtient ainsi une relation de récurrence qui est
4 2 1 4 2
xn+1
1 − ( α − β) = (xn1 − ( α − β))
3 3 4 3 3
qui conduit à
4 2 1 4 2
xn1 − ( α − β) = n [x11 − ( α − β)]
3 3 4 3 3
dont on a la convergence vers la valeur x01 .
Un résultat général est le suivant:
Théorème 6.1 On suppose que J est α−convexe différentiable et que, de plus J 0 est
Lipschitzien sur tout borné:
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 ).
On note Ji0 la dérivée de J par rapport à l’élément de Vj , tous les autres éléments
étant fixes:
Définition 6.1 Soit J une fonctionnelle continue sur V , espace de Hilbert et soit K
l’espace des contraintes. On dit que d est une direction de descente au point u de K
si
i) d est une direction admissible de K̇(u)
ii) Il existe ρ0 > 0 tel que
On peut aussi écrire une définition plus générale, qui tienne compte des contraintes
égalités:
Définition 6.2 On suppose que d ∈ K(u) et que, de plus, il existe 0 > 0 et d()
tels que d() → d et ∀ < 0 , u + d() ∈ K (généralisation continue de la direction
admissible au sens de Fréchet).
On dit que d est une direction de descente limite au point u de K si il existe 1 ≤ 0
tel que
pour 0 < < 1 , on a J(u + d()) < J(u).
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
Comme d est une direction admissible continue, il existe d() et 0 tels que, pour
< 0 , u + d() soit dans K. Comme J est différentiable en u, on peut écrire l’égalité
de Taylor définissant la dérivabilité au sens de Fréchet:
est équivalent, pour tous les points u où F (u) = 0, F 0 (u) 6= 0, à un problème de
minimisation sur (F 0 (u))⊥ de la forme
Ceci est un résultat de réduction des variables. On en verra l’utilisation plus loin,
lorsqu’on étudiera l’algorithme de gradient réduit.
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 fonctions 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 fonctionnelle sous les contraintes. On voit alors
que pour tout v dans Iu , le problème de minimisation s’écrit u + v + tF 0 (u) ∈ K et
u+v+tF 0 (u) ∈ {F (w) = 0}, soit u+v+tF 0 (u) ∈ K et t = g(v), soit u+v+g(v)F 0 (u) ∈
K. Ainsi on s’est ramené à la fonctionnelle J(v) ˜ = J(u+v +g(v)F 0 (u)) et au problème
˜
infJ(v)
v∈I u
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)
Exemples:
figure 1 figure 2
Dans la situation de la figure 2, il n’existe pas de pas de Goldstein, mais en revanche
on a ∀ ∈ [0, ρ0 ], φ() ≤ φ(0) + φ0 (0), ce qui fait que l’on peut choisir pour la valeur
ρ0 , même si cela a un inconvénient, comme on le verra ci-dessous.
La situation importante est la situation où il existe au moins 1 , 0 < 1 < ρ0 tel
que
Proposition 6.2 i) Si φ() ≤ φ(0) + φ0 (0) pour tout ∈ [0, ρ0 ], il n’existe pas de pas
de Goldstein.
ii) Dans le cas contraire, il existe m1 , m2 ∈]0, 1[, m1 < m2 tel que l’ensemble des
points l vérifiant les inégalités de la définition 6.6 soit non vide.
iii) Toujours dans le cas contraire, il existe 2 > 0 et M > 0 (dans le cas où la
fonctionnelle admet un minimum) tel que, pour tout lg , 2 ≤ lg ≤ M .
Selon le point iii), il y a une borne supérieure pour lg , et lg n’est pas trop petit. Ces
deux remarques sont importantes, et en particulier si on avait φ() ≤ φ(0) + φ0 (0) on
n’aurait pas de majorant a priori de .
Preuve:
On note m = φ(11φ)−φ(0)
0 (0) . On sait que m ∈]0, 1[ et si on choisit m1 < 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)
70 CHAPTER 6. APPROXIMATION DE SOLUTIONS
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.
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 .
Preuve
φ0 (1 )
Si 1 donné tel que φ0 (1 ) > φ0 (0), alors m = φ0 (0) < 1 et donc on choisit
φ0 (0) φ0 ()
m2 ∈]m, 1[. Comme φ0 (0) = 1 et que la fonction → φ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)
Si on choisit 0 < m1 < α, on trouve que pour tout ∈ [02 , ρ0 ], φ()−φ(0)
φ0 (0) ≥ α, donc
est un pas de Wolfe.
Enfin, si on était dans le cas ρ0 = +∞ et si il existait une suite de pas de Wolfe
qui tendait vers +∞, il existe donc n telle que φ(n ) ≤ φ(0) + m1 n φ0 (0), donc
J(u + n d) → −∞ et le minimum n’existe pas.
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
1 0
||J 0 (un )|| ≤ ||J (un + ln dn ) − J 0 (un )||.
α
Comme J 0 est continue, on vérifie que J 0 (un+1 ) − J 0 (u) − (J 0 (un ) − J 0 (u)) tend vers
0 dans l’espace des formes linéaires, donc on en déduit que J 0 (un ) tend vers 0.
D’autre part, la suite J(un ) est strictement décroissante (par construction) donc
comme un converge vers u, la suite J(un ) converge vers J(u) et la suite J 0 (un ) converge
vers J 0 (u). On en déduit J 0 (u) = 0. Le point i) est démontré pour le pas de Curry.
Démontrons le point i) pour la règle de Wolfe. On suppose que un converge. Par
continuité J(un ) converge vers J(u) et J 0 (un ) converge vers J 0 (u). On a (J 0 (un ), dn ) ∈
[−α||J 0 (un )||, 0] donc toute suite extraite convergente de (J 0 (un ), dn ) converge vers une
limite l dans l’intervalle [−α||J 0 (u)||, 0].
On utilise la deuxième inégalité du pas de Wolfe. On a alors (J 0 (un+1 ), dn ) ≥
m2 (J 0 (un ), dn ). On note que si on prend une suite extraite convergente de (J 0 (un ), dn ),
notée (J 0 (uφ(n) ), dφ(n) ), la suite (J 0 (uφ(n)+1 ), dφ(n) ) converge aussi vers l car la différence
est majorée par un terme tendant vers 0 par continuité de J 0 et convergence de la suite
un . Ainsi, l qui est négatif vérifie l’inégalité l ≥ m2 l, soit (1 − m2 )l ≥ 0 donc l = 0.
On a démontré le point i) pour la règle de Wolfe.
Démontrons le point ii). Pour cela, suposons que liminf||J 0 (un )|| = α0 > 0. Alors
il existe N assez grand tel que, pour tout n ≥ N on ait ||J 0 (un )|| > α20 . Si cela
n’était pas le cas, il existerait un nombre infini de termes de cette suite de nombres
positifs qui sont compris entre 0 et α20 , donc il existerait une sous-suite extraite de
cette suite qui convergerait vers une valeur comprise entre 0 et α20 , contradictoire avec
l’hypothèse que α0 est la plus petite des limites des suites extraites.
On en déduit alors
αα0
||un+1 − un || ≤ J(un ) − J(un+1 ).
2
Si J(un ), qui est une suite décroissante, ne tend pas vers −∞, alors elle tend vers
une limite l et la série de terme général (J(un ) − J(un+1 )) est une série convergente,
donc la somme de la série u1 + n (−un + un+1 ) existe, et on la note u, qui est la
P
i) Règle de Wolfe. D’après le i), comme un a une limite, notée u, on sait que la
suite J 0 (un ) est convergente et que sa limite est J 0 (u) = 0, ce qui est contradictoire
avec l’hypothèse que la limite inf de ||J 0 (un )|| est nulle.
On a donc démontré que liminf||J 0 (un )|| = α0 > 0 ⇒ J(un ) → −∞. On en déduit
que si J(un ) converge vers une limite finie, alors liminf||J 0 (un )|| = 0. Notons qu’on ne
peut pas conclure directement que la suite un converge.
ii) Règle de Goldstein
On suppose donc que la suite J(un ) converge vers une limite l. On suppose aussi
que liminf||J 0 (un )|| = α0 > 0. Ceci implique que la suite un est convergente, et sa
limite est notée u. Par continuité de J et de J 0 , J(un ) tend vers J(u) et J 0 (un ) tend
vers J 0 (u). Contrairement à la règle de Wolfe, on n’a pas d’autre information sur la
dérivée. En effet, l’information sur la limite inf nous apprend que ||J 0 (un )|| ≥ α20 pour
n ≥ n0 , mais on n’a pas le même résultat pour (J 0 (un ), dn ).
On sait, par la règle de Goldstein, que
J(un ) − J(un+1 )
∈ [m1 , m2 ].
(J 0 (un ), un − un+1 )
Z 1
−J(un ) + J(un+1 ) = (J 0 (un + θ(un+1 − un )), un+1 − un )dθ
0
Ainsi, divisant les deux membres par (J 0 (un ), un+1 − un ) et utilisant l’inégalité
(J 0 (u 0 0
n ), dn ) ≤ −α||J (un )||, dans le cas où J (un ) ne tend pas vers 0, pour n ≥ n ,
n )−J(un+1 )
On en déduit que le quotient (JJ(u
0 (u ),u
n n+1 −un )
tend vers 1. Comme ce quotient appar-
tient à [m1 , m2 ] et que m2 < 1 il y a contradiction. Le résultat est démontré sous
l’hypothèse d’uniforme continuité ou de continuité dans un borné en dimension finie.
Remarque 1 : le i) peut s’étendre à toute sous-suite convergente dans le cas où
la suite ln tend vers 0. On note que ceci n’implique pas que la suite un converge :
exemple si dn = e1 pour tout n et si ln = n1 alors il n’y a pas convergence de un .
Remarque 2 :Pour la règle de Goldstein, il suffit, en dimension finie que J vérifie
l’une des deux conditions suivantes :
(*) J 0 est uniformément Lipschitz sur tout borné
(**) la fonctionnnelle J est deux fois Fréchet dérivable à dérivée continue (qui
implique la condition (*) et qui se retrouve le plus fréquemment)
6.4. ALGORITHMES DE GRADIENT 73
(un ) 0
et ce minimum est atteint pour d = − ||JJ 0 (u n )||
.
Théorème 6.3 Soit J une fonctionnelle α−convexe sur un espace de Hilbert H, telle
que J 0 est uniformément continue sur tout borné. La suite, définie par la relation
un+1 = un − µn J 0 (un ),
où µn est la solution unique de J 0 (un − µJ 0 (un )) = 0 qui s’appelle l’algorithme de gra-
dient à 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
2 1 q
||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é
1 0 n
||un − u|| ≤ ||J (u )||
α
donc
1 2 1 q
||un − u|| ≤( ) 2 C J(un ) − J(un+1 )
α α
et donc la suite un converge vers u.
6.4. ALGORITHMES DE GRADIENT 75
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
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
λmax
γ= .
λmin
γ−1
Cette valeur s’appelle le conditionnement de J”(u). On note β = γ+1 , et si β est
proche de 1, l’algorithme peut converger très lentement. On dit dans ce cas que la
matrice J”(u) est mal conditionnée.
i) Lorsque J est quadratique, l’algorithme de gradient vérifie l’inégalité:
76 CHAPTER 6. APPROXIMATION DE SOLUTIONS
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 de φ est
(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 Kantorovitch.
Alors on trouve
p
Comme ||un ||A = 2J(un ), on trouve l’inégalité
Z 1 1
Z 1
J(u) = 00
(1−θ)(J (0+θu)u, u)dθ = (J 00 (0)u, u)+([ (1−θ)(J 00 (θu)−J 00 (0))]u, u).
0 2 0
Z 1
0 00
J (u) = J (0)u + ( J 00 (θu)dθ − J 00 (0))u
0
1 00
que l’on écrira pour simplifier J(u) = 2 (J (0)u, u)+ (Q(u)u, u) et J 0 (u) = J 00 (0)u +
R(u)u, où Q et R, par la continuité de la dérivée seconde au sens de Fréchet, sont
égales à o(1) (c’est à dire tendent vers 0 lorsque u tend vers 0).
On sait déjà que l’algorithme du gradient converge, donc il existe n0 tel que
||un || ≤ δ0 pour n ≥ n0 . On cherche donc, pour u donné l’unique solution de
(J 0 (u − µJ 0 (u)), J 0 (u)) = 0. On note, comme précédemment, φ(µ) = J(u − µJ 0 (u)),
φ0 (µ) = −(J 0 (u − µJ 0 (u)), J 0 (u)), φ00 (µ) = (J 00 (u − µJ 0 (u))J 0 (u), J 0 (u)).
On vérifie que
(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
78 CHAPTER 6. APPROXIMATION DE SOLUTIONS
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 4λmax λmin
On se donne β > λλmax 2
+λ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 q
||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 q
||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
γ−1
taux de convergence β arbitraire, strictement supérieur à γ+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é.
λp yp2 )( λ−1 2
X X
sup( p yp ).
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
λ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 21 + 41 ( λqp + λqp ).
A = (A0 , A1 )
où A0 est une matrice m × m inversible et A1 est une matrice m × (n − m).
Proposition 6.6 L’algorithme de gradient réduit est une suite (un , dn , µn ) donnée
par
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 IRn = {(x, y), x ∈ IRm , y ∈ IRn−m }, 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 ).
On se place dans le cas où dn 6= 0 (car sinon on aurait atteint le point de minimum).
Dans ce cas, on introduit
Dxn = −A−1 0 A1 dn .
(D n , J 0 (un )) = (−A−1 n n n −1 t n
0 A1 dn , dx ) + (dn , dy ) = (dn , dy − (A0 A1 ) dx ) = (dn , dn ) > 0
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
(
dny = At1 ((A−1 t n
0 ) dx )
dnx = At0 ((A−1 t n
0 ) dx )
J 0 (un ) + λAt = 0.
82 CHAPTER 6. APPROXIMATION DE SOLUTIONS
Comme on est en dimension 2, cela veut dire qu’il existe λn tel que
On en déduit, utilisant
Dans le cas où a 6= b, la suite est donc infinie et converge par itérations successives
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
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 83
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
(A(x1 + λp1 ) − b, p1 ) = 0
soit
(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
(
(J 0 (x1 + λp1 + µp2 ), p1 ) = 0
(J 0 (x1 + λp1 + µp2 ), p2 ) = 0
soit (
(Ax1 − b + λAp1 + µAp2 , p1 ) = 0
(Ax1 − b + λAp1 + µAp2 , p2 ) = 0
84 CHAPTER 6. APPROXIMATION DE SOLUTIONS
(
(Ax1 − b, p1 ) + λ(Ap1 , p1 ) = 0
(Ax1 − b, p2 + µ(Ap2 , p2 ) = 0
ce qui conduit à λ = λ1 et µ = λ2 .
On voit donc que le point x3 = x1 + λ1 p1 + λ2 p2 est le point qui réalise le minimum
de J sur l’espace affine x1 + Vect(p1 , p2 ).
On définit alors la suite de récurrence par
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 )
On voit alors que b − Ax2 = i≥2 (Xi − xi1 )Api , donc (b − Ax2 , p2 ) = (X2 −
P
xi1 pi .
X X
xn = Xi pi +
1≤i≤n−1 i≥n
i≥n
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
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 85
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
x2 dp − x2
Z Z
Hn (x)Hp (x)e− 2 dx = Hn (x)(−1)p (e 2 )dx.
IR IR dxp
Sans restreindre la généralit,́ on peut supposer soit p = n soit p > n. Dans le cas
p > n, en faisant p intégrations par parties, on trouve que
x2 dp x2
Z Z
Hn (x)Hp (x)e− 2 dx = p
(Hn (x))e− 2 dx = 0
IR IR dx
car Hn est un polynôme de degré n < p.
D’autre part, pour p = n on trouve que
Z
x2
Z
x2 √
Hn (x)Hn (x)e− 2 dx = n! e− 2 dx = n! 2π
IR IR
La famille de polynômes Hn est donc une famille orthogonale pour le produit scalaire
x2
Z
f (x)g(x)e− 2 dx
x2
et c’est donc une famille conjuguée pour l’application Af = f e− 2 .
d0 = −J 0 (x0 )
86 CHAPTER 6. APPROXIMATION DE SOLUTIONS
(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 vec-
toriel engendré par les gradients successifs (J 0 (x0 ), J 0 (x1 )). On a simplement imposé
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 87
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
(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 engendré 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
88 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 (d1 , J 0 (x1 )−J 0 (x0 )) = (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
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 89
ρ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 )
Raisonnement par récurrence On suppose donc que l’on a construit une suite
(xp , ρp , dp ), p ≤ n, et xn+1 ayant les propriétés suivantes:
• la suite (dp ) est une suite de directions conjuguées
• dp+1 = −J 0 (xp+1 ) + βp+1 dp pour p ≤ n − 1 avec
|J 0 (xp+1 )|2
βp+1 = .
|J 0 (xp )|2
• les vecteurs (J 0 (xp )) forment une famille orthogonale pour le produit scalaire
usuel pour 0 ≤ p ≤ n + 1
• xp+1 = xp + ρp dp pour p ≤ n, les ρp étant donnés par la relation
|J 0 (xp )|2
ρp = − .
(J 0 (xp ), Adp )
On construit xn+2 , dn+1 et ρn+1 suivant les conditions suivantes. 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 )). On écrit donc
On sait déjà que
n
j
dn+1 = −J 0 (xn+1 ) +
X
βn+1 dj
j=0
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 orthogonale,
on en déduit que J 0 (xn+1 ) est orthogonal à tous les J 0 (xp+1 ) pour p + 1 ≤ n et à tous
p
les J 0 (xp ) pour p ≤ n. On en déduit que βn+1 = 0 pour p 6= n. Il reste alors seulement
un terme
90 CHAPTER 6. APPROXIMATION DE SOLUTIONS
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.
La condition d’optimalité pour xn+2 s’écrit
(J 0 (xn+2 ), dn+1 ) = 0
On sait en outre que
Toutes les hypothèses du raisonnement par récurrence ont été vérifiées, ainsi l’algorithme
continue jusquà obtenir J 0 (xN ) = 0. En dimension finie d, on aura nécessairement
cette condition puisque la famille (J 0 (x0 ), .., J 0 (xd−1 )) est une famille orthogonale. Si
c’est une famille libre, c’est une base et J 0 (xd ) orthogonal à tous les éléments implique
que J 0 (xd ) = 0. Si c’est une famille liée, comme le vecteur J 0 (xd−1 ) est orthogonal
à tous les autres, si il est combinaison linéaire de tous les autres, cette combinaison
linéaire est nulle si tous sont non nuls, donc il en existe au moins un qui est nul.
6.5. ALGORITHMES DE GRADIENT CONJUGUÉ 91
On remarque que dans le cas de la forme quadratique J(x) = 21 (Ax, x), on trouve
J 0 (x)
= Ax donc E(x) = 2J(x). On a alors immédiatement
(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 = xn − xn−1 .
(A(xn −xn−1 ),Axn )
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−1 ) = ||J 0 (xn−1 )||2 =
||Axn ||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
2
x0 (1 − a t) = 0
y (1 − b2 t) = 0
0
z (1 − c2 t) = 0
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 ))
x(2) =
(a2 x 0 [(1 − a2 t 0) + ρ(−1 + a2 t 0 + β0 )], b2 y 0 [(1 − b2 t 2 2 2 2
0 ) + ρ(−1 + b t0 + β0 )], c z0 [(1 − c t0 ) + ρ(−1 + c t0
On suppose que l’algorithme a convergé en deux itérations. Alors les coordonnées dans
l’expression ci-dessus sont nulles. On élimine le cas où une seulement des valeurs de
(x0 , y0 , z0 ) est non nulle car c’est le cas précédent. Si x0 y0 z0 6= 0, on en déduit que les
coefficients sont nuls, c’est à dire on obtient un système sur t0 , β0 , ρ. On vérifie que ce
système n’a pas de solutions. En effet, on trouve les relations (1 − a2 t0 )(1 − ρ) + ρβ0 =
(1 − b2 t0 )(1 − ρ) + β0 ρ = 0, d’où (a2 − b2 )t0 (1 − ρ) = 0. Le cas t0 est impossible (il
suffit de vérifier que t0 (a6 x20 + b6 y02 + c6 z02 ) = a4 x20 + b4 y02 + c4 z02 ). Il reste donc ρ = 1,
ce qui donne β0 = 0. Comme β0 est le quotient des normes de J 0 (x(1) ) et de J 0 (x(0) ),
on trouve que c’est impossible. Ainsi, seulement deux valeurs sur les trois sont non
nulles.
Dans ce cas, on considère par exemple z0 = 0. Alors le point de départ est dans
le plan z = 0, ainsi que le vecteur gradient. Le point d’arrivée x(1) est alors dans
ce plan, et on s’est ramené au minimum de la fonctionnelle J(x, y, 0) qui est atteint
en deux itérations, la première direction d0 = −J 0 (x(0) ) et la deuxième direction
d1 = −J 0 (x(1) ) + β0 d0 comme dans le cas de l’ellipse.
On vérifie alors que l’algorithme du gradient conjugué converge en deux
itérations seulement si le point de départ appartient à un des espaces de
dimension 2 invariants par la matrice J”(0).
6.6. ALGORITHME DE DESCENTE PSEUDO-CONJUGUÉ POUR UNE FORME NON QUADRATIQU
a2 1 0
Remarque On considére la forme quadratique associée à la matrice A = 1 b2 0 .
0 0 c2
On voit que les valeurs propres de cette matrice sont c2 et λ solution de λ2 − (a2 +
b2 )λ + a2 b2 − 1 = 0, soit
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 propres λ± =
a2 +b2 2 2
2 ± 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).
d0 = −J 0 (x0 )
xn+1 = xn + ρn dn
dn+1 = −J 0 (xn ) + βn dn
0 2
βn = |J|J (x n+1 |
0 (x )|2
n
• algorithme de Polak-Ribiere
d0 = −J 0 (x0 )
xn+1 = xn + ρn dn
dn+1 = −J 0 (xn ) + βn dn
0 0 0
βn = (J (xn+1 ,J|J 0(x n+1 )−J (xn ))
(xn )|2
(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 con-
struit comme uk + ∆k , où ∆k est la solution du problème variationnel
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
6.7. MÉTHODE DE NEWTON 97
il existe C telle que 2λβ01α2 ≤ (1 − C) βα1 . Dans ce cas, on voit que si ||∆k || ≥
(1 − C) βα1 , on obtient
β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 lambda1
β12
(que l’on suppose assez grande) vérifie λ1 > 8α3 , on vérifie que λ1 α2 ||∆k ||2 +
8µ0 α3 −β12
α
2 − β21 ||∆k || ≥ 16µ0 α2
= δ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.
Un des problèmes essentiels d’un algorithe de gradient, lorsqu’on n’est pas dans
le cas du gradient réduit, est qu’il ne donne pas à l’itération n + 1 un élément de
l’espace des contraintes car on ne sait pas si la direction −J 0 (xn ) est une direction
admissible pour l’espace des contraintes si xn est dans K. D’autre part, la projection
est une application contractante, donc ||pK (x)−pK (y)|| ≤ ||x−y||, ce qui implique que
||pK (x − αJ 0 (x)) − pK (y)|| ≤ ||x − αJ 0 (x) − y|| donc en projetant le résultat d’un algo-
rithme de gradient, on se rapproche plus de y solution du problème de minimisation.
L’algorithme de gradient avec projection est un algorithme de la forme
(y − x0 , −αJ 0 (x0 )) ≤ 0
donc
∀y ∈ K, (y − x0 , x0 − αJ 0 (x0 ) − x0 ) ≤ 0
ce qui est la caractérisation de la projection de x0 − αJ 0 (x0 ) en x0 . On en déduit que
∀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:
Théorème 6.8 On suppose K convexe fermé non vide, J bornée inférieurement sur
K, de classe C 1 , Lipschitz uniformément sur K dont une constante de Lipschitz est
L:
||xn+1 − xn || → 0
Tous les points d’adhérence de cette suite sont des points stationnaires.
100 CHAPTER 6. APPROXIMATION DE SOLUTIONS
donc
1
(J 0 (xn ), xn+1 − xn ) ≤ − ||xn − xn+1 ||2 .
ρn
On utilise
Z 1
0
J(xn+1 )−J(xn )−(J (xn ), xn+1 −xn ) = (J 0 (xn +t(xn+1 −xn ))−J 0 (xn ), xn+1 −xn )dt.
0
|J(xn+1 ) − J(xn ) − (J 0 (xn ), xn+1 − xn )| ≤ 01 ||J 0 (xn + t(xn+1 − xn )) − J 0 (xn )||||xn+1 − xn ||dt
R
≤ L( 01 tdt||xn+1 − xn ||)||xn+1 − xn ||
R
≤ 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 L
2 − ρ1n ∈ [ 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−
6.8. ALGORITHMES D’OPTIMISATION AVEC CONTRAINTES 101
On a
lim uε = u.
ε→0
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
102 CHAPTER 6. APPROXIMATION DE SOLUTIONS
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
1 X
J 0 (uε ) + 2 max(Fj (uε ), 0)Fj0 (uε ) = 0.
ε j∈I(u)
D’autre part, pour j ∈ I(u), on vérifie qu’il existe une suite λ1 , ..λM , avec λj = 0
/ I(u), telle que J 0 (u) + λj Fj0 (u) = 0. Ainsi on trouve
P
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) + 12 (∆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) + 12 (∆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).
2 2 (∆x)4 4
uj+1 j−1 j
n +un −2un = (∆x) ∂x2 u(j∆x, n∆t)+ [∂x4 u(j+θ)∆x, n∆t)+∂x44 u(j−θ 0 )∆x, n∆t)],
24
105
106 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
ainsi
u1n+1
u2n+1
A = 2un−1 − un−1 .
.
.uNn+1
C’est un système linéaire de la forme Ax = b qui peut se résoudre par des méthodes
d’approximation du cours d’optimisation, sur la fonctionnelle
1
J(x) = (Ax, x) − (b, x).
2
Pour l’équation de la chaleur, on écrit les mêmes schémas:
ξ∆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).
• 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 condition
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
108 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
ξ∆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 car-
actéristique est 1, donc le produit des modules est égal à 1. Si le discriminant 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 discrim-
1+4 sin 2
( ∆x )
inant 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 + ujn−1 − 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
où
∆t 2 2 ξ∆x
α(ξ) = 4( ) sin
∆x 2
associée à l’équation caractéristique
que 1. Il vient alors qu’une condition nécessaire de stabilité est donnée par le fait que
les deux racines sont complexes conjuguées, donc de module 1. Ceci s’écrit
(4θ − 1)α + 4 ≥ 0.
Lorsque θ ≥ 41 , cette inégalité est tout le temps vraie. Lorsque θ ∈ [0, 21 ], 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
3) Un schéma implicite pour l’équation de la chaleur s’écrit
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 + ujn−1 − 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.
110 CHAPTER 7. INTRODUCTION À LA DISCRÉTISATION
un+1
j + ujn−1 − 2unj
+ (Ah (θun+1 + (1 − 2θ)un + θun+1 ))j = 0.
(∆t)2
∆t 1
≤√ .
∆x 1 − 4θ
Ph = {u(x, y) ∈ H01 ([0, 1]×[0, 1]), continues, polynômes de degré 1 sur[ph, (p+1)h]×[qh, (q+1)h]}.
sur une base, et on écrit la minimisation de J sur Ph ⊂ H01 ([0, 1] × [0, 1]). Alors on
trouve, de l’égalité variationnelle (7.2.6) écrite pour vh ∈ Ph et uh ∈ Ph , un système
en dimension finie de la forme Ah uh = Fh , que l’on résout par les méthodes usuelles
du cours (en minimisant par exemple 21 (Ah X, X) − (Fh , X)), et on essaie d’avoir un
résultat en faisant tendre h vers 0.
Par exemple, la base de polynômes sur chaque pavé est (1, X, Y ) donc tout polynôme
de degré au plus 1 s’écrit
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
0 0 1xdxdy = h2
RhRh 3
1ydxdy = h2
R0h R0h 2 4
x dxdy = h3
R0h R0h 4
xydxdy = h4
R0h R0h 2 h 4
0 0 y dxdy = 3
h h h2
h2 [aa0 + (ab0 + a0 b + ac0 + a0 c)
+ (bc0 + b0 c) + (bb0 + cc0 ) ]
2 3 4
2
ainsi la matrice de la forme quadratique associée (en divisant par h pour plus de
simplicité) est
h h
1 2 2
h h2 h2
.
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
qui sont des polynômes de degré 1 dans chacune des variables x, y. Alors on aura
∀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 12 a(u, u) − Lh (u) sur Vh , dans certaines conditions
uh → u.
Chapter 8
Problèmes d’examens
Dans cette partie, nous donnons les sujets d’examens posés les années précédentes.
La solution sommaire est donnée en italique à la suite de chaque question.
2
J0 (y) = 12 01 ( ddt2y )2 (t)dt
R
1. On veut résoudre
inf J0 (y)
(A) y(0) = v0
y(1) = v1 .
113
114 CHAPTER 8. PROBLÈMES D’EXAMENS
1 d2 y d2 w
Z
(J00 (y), w) = dt.
0 dt2 dt2
1.3. Ecrire l’équation d’Euler et donner les conditions nécessaires sur y. Calculer la
solution générale dans H 4 (0, 1) de l’équation différentielle obtenue.
R 2 2
L’équation d’Euler est ∀w ∈ H 2 (0, 1), 01 ddt2y ddtw ∞
2 dt = 0. On prend w ∈ C0 (0, 1),
ce qui implique que, au sens de D 0 (0, 1), y (4) = 0. On ne peut pas aller plus loin car
on n’a aucune information sur la continuité de y” pour y ∈ H 2 , donc on ne peut pas
utiliser la formule d’intégration par parties.
La solution générale de l’équation différentielle dans H 4 est y = a0 + a1 x + a2 x2 +
3
a3 x .
2. On cherche à résoudre
inf Jε (y)
(B) y(0) = v0
y(1) = v1 .
2.1. Identifier α tel que Jε est α−convexe sur H 2 (0, 1) muni de sa norme usuelle
d2 u 2
1 du
Z
1
||u|| = ( [(
2
) + ( )2 + u2 ]dt) 2 .
0 dt dt
Il suffit de prendre α = min(ε, 1).
8.1. PROBLÈME DES SPLINES: TEXTE DU PROBLÈME DE 1999 115
2.2. Justifier le fait que (B) admet une solution unique. Donner les conditions
nécessaires sur la solution yε , supposée encore ici dans H 4 (0, 1). *Montrer que cette
solution peut se décomposer sur une base de fonctions de la forme eλt et donner le
système vérifié par les coefficients. Ne Pas le résoudre.
On applique le théorème 4.1. L’équation d’Euler s’écrit
Z 1
2
∀w ∈ H (0, 1), y”w” + ε(y 0 w0 + yw) = 0.
0
y (4) − εy” + εy = 0.
Si la solution est dans H 4 , par intégrations par parties, on trouve y”(1) = y”(0) =
0. On a donc l’équation différentielle ordinaire + quatre conditions aux limites y(0) =
v0 , y(1) = v1 , y”(0) = y”(1) = 0.
D’autre part, il est facile de voir que l’équation différentielle ordinaire a, dans H 4 ,
les solutions (pour < 4)
On en déduit J0 (yε ) ≤ Cε, ce qui démontre, puisque y”ε est une suite de L2 , que
y”ε tend vers 0 dans L2 . On écrit alors
Z 1
yε (x) = v0 + yε0 (0)x + x2 (1 − t)y”ε (tx)dt
0
De ces deux égalités, on déduit que yε0 (0) converge vers v1 − v0 , en utilisant
l’inégalité de Cauchy-Schwartz sur l’intégrale, puis que yε (x) converge vers v0 + (v1 −
v0 )x en tout point. On montre même, utilisant la formule de Taylor avec reste intégral
sur yε0 , que yε tend vers y0 dans H 2 .
3. On veut résoudre
inf J(y, v)
(C)
y ∈ H 2 (0, 1).
116 CHAPTER 8. PROBLÈMES D’EXAMENS
3.1. Montrer que, pour tout v ∈ IR2 , il existe y(v)(t) telle que y”(v)(t) = 0∀t et
J(y, v) = J(y − y(v), 0).
Comme y” est nulle, y(v)(x) = a + bx. Dire que l’égalité demandée est vraie se
traduit en
1
J(y − y(v)) = J0 (y − y(v)) + [(y(1) − a − b − v1 )2 + (y(0) − a − v0 )2 ]
2
donc y(v)(x) = −v0 − (v1 − v0 )x et l’égalité est vérifiée.
Z 1 Z 1
y(x) = y(0) + (y(1) − y(0))x + x2 (1 − t)y”(tx)dt − x (1 − t)y”(t)dt
0 0
Z 1 Z 1
0
y (x) = y(1) − y(0) + x y”(xt)dt − y”(t)dt
0 0
On en déduit
Z 1 7 7
(y(x))2 dx ≤ 2((y(0))2 +y(0)y(1)+(y(1))2 )+ ||y”||2L2 ≤ 3((y(0))2 +(y(1))2 )+ ||y”||2L2
0 9 9
On a un résultat identique pour l’intégrale de y 0 , donc on a la coercivité de J par
l’équivalence des normes. On applique alors la proposition 4.3.
3.3. Démontrer que le problème (C) admet une solution unique dans H 2 (0, 1). En
écrivant la condition d’Euler, déterminer la solution de (C).
Comme il s’agit d’une fonctionnelle α−convexe, on a l’existence et l’unicité du
minimum. Les équations d’Euler sont
Z 1
∀w ∈ H 2 , y”w” + y(0)w(0) + y(1)w(1) = 0.
0
8.1. PROBLÈME DES SPLINES: TEXTE DU PROBLÈME DE 1999 117
∀w ∈ H 2 , y”(1)w0 (1) − y”(0)w0 (0) + (y(0) − y (3) (0))w(0) + (y(1) − y (3) (1))w(1) = 0
ce qui donne quatre relations sur les coefficients 6a3 + 2a2 = 0, a2 = 0, a0 − 6a3 =
0, a0 +a1 +a2 +a3 −6a3 = 0, donc la solution est 0. On aurait pu le trouver directement
en rappelant qu’il y a une solution unique, que la valeur de J(y, 0) en y = 0 est le
minimum, donc le minimum est 0.
Z 1
∀w ∈ C ∞ , [∂y L(s, y, y 0 , y”)w + ∂y0 L(s, y, y 0 , y”)w0 + ∂y” L(s, y, y 0 , y”)w”]ds = 0.
0
d d2
∂y L(t, y0 (t), y00 (t), y”0 (t))− (∂y0 L(t, y0 (t), y00 (t), y”0 (t)))+ 2 (∂y” L(t, y0 (t), y00 (t), y”0 (t))) = 0.
dt dt
∂y” L(1, v1 , y00 (1), y0 ”(1)) = 0, ∂y” L(0, v0 , y00 (0), y”0 (0)) = 0, y0 (1) = v1 , y0 (0) = v0 .
j=N
1 1 d2 y 2 1 X
Z
S(y, v) = ( ) dt + (y(tj ) − vj )2 .
2 0 dt2 2 j=0
5. Spline d’ajustement.
118 CHAPTER 8. PROBLÈMES D’EXAMENS
5.1. On suppose N ≥ 2. Déterminer les relations sur t1 , ..., tN1 , v1 , ..., vN1 en fonction
de v0 et de vN de sorte que S(y, v) = 0 admette une solution y.
Si S(y, v) = 0, alors y est un polynôme de degré 1, entièrement déterminé par
N −v0
y(t0 ) = v0 et y(tN ) = vN : y(t) = v0 + vtN −t0 (t − t0 ). Alors les conditions de
compatiblité sont
X−1
1 i=N
S(y, v) = J(y, v0 , vN ) + (y(ti ) − vi )2
2 i=1
la somme étant vide si N = 1. On utilisera alors les questions 3.1., 3.2..
On sait alors que J(y, v0 , vN ) = J(y − y(v0 , vN ), 0) ≥ α||y − y(v0 , vN )||2H 2 , ce qui
implique la coercivité de S dans H 2 . L’α−convexité s’en déduit.
5.3. En déduire que (D) admet une solution unique ỹ, pour laquelle on donnera les
conditions nécessaires d’optimalité. On remarquera, pour obtenir ces équations, qu’il
n’est pas licite de supposer ỹ ∈ H 4 (0, 1), mais on démontrera en utilisant des fonctions
test adéquates que l’on pourra prendre ỹ ∈ H 4 (]ti , ti+1 [) pour i ≤ N − 1.
Le fait qu’il y a une solution unique provient de l’α−convexité. La condition
d’Euler s’écrit
Z 1
w(tj )(y(tj ) − vj ) = 0∀w ∈ H 2 .
X
y”w”dt +
0 j
On en déduit, prenant w ∈ C0∞ (]ti , ti+1 [), que y (4) est nulle dans D 0 (]ti , ti+1 [), ainsi
y ∈ H 4 (]tj , tj+1 [).
5.4. Démontrer que ỹ est une fonction spline cubique de classe C 2 sur [0, 1]. On
l’appelle spline d’ajustement.
Comme y est dans H 2 , y est de classe C 1 sur [0, 1] par inclusion d’espaces de
Sobolev. Ceci se démontre car y0 (x) − y0 (z) = xz y”(t)dt donc |y0 (x) − y0 (z)|| ≤ (|x − z|) 2 ||y||H 2 . Cette
R 1
simple inégalité ne suffit pas. On montre d’abord que, pour f de classe C 2 , on a l’inégalité |f 0 (x) − f 0 (z)| ≤
1 1
(|x − z|) 2 ||f ”||, ainsi on en déduit |f 0 (x)| ≤ |f 0 (z)| + (|x − z|) 2 ||f ”||2 , donc en intégrant en z sur [0, 1] on
trouve |f 0 (x)| ≤ ||f 0 ||2 + 43 ||f ”||2 . On voit donc que si yn est une suite de fonctions de classe C 2 convergeant
vers y au sens H 2 , alors |yn
0 (x) − y 0 (x)| vérifie le critère de Cauchy, donc la suite y 0 (x) converge pour tout
m n
x, uniformément en x, vers une fonction continue notée g(x). On montre ainsi que, de même, la suite yn (x)
Rx 0 (s)ds on
converge uniformément. Soit y la limite uniforme de yn . Alors de l’égalité yn (x) − yn (a) = yn
Rx a
déduit que y(x) − y(a) = g(t)dt, donc y0 = g.
a
De plus, grâce à l’équation d’Euler, en effectuant l’intégration par parties sur
]ti , ti+1 [ et sur ]ti−1 , ti [, on trouve
Z ti+1
y”w”dt = y”(ti+1 −0)w0 (ti+1 )+w0 (ti )(y”(ti −0)−y”(ti +0))−w0 (ti−1 )y”(ti−1 −0)
ti−1
8.1. PROBLÈME DES SPLINES: TEXTE DU PROBLÈME DE 1999 119
6. Spline d’interpolation.
6.1 Montrer que (E) admet une solution, lorsque N ≥ 1. Donner les conditions
d’optimalité. On note ȳ une solution de l’équation d’Euler.
Attention: on ne peut pas dire que J0 est infini à l’infini dans H 2 car toute fonction
de la forme ya,b (x) = ax + b vérifie J0 (y) = 0 et pourtant ||y||2H 2 = a2 + a + 2b, et il
suffit de prendre b = 0 et a infini pour avoir y tend vers l’infini. On trouve aussi que
pour tout y, J0 (y + ya,b ) = J0 (y).
Lorsque N ≥ 1, on considère z(x) = y(x) − v0 − (v1 − v0 )x. Lorsque y est dans
l’espace des contraintes, cette fonction est dans H02 . Elle vérifie les contraintes z(ti ) =
vi − v0 − (v1 − v0 )ti . On voit que
Z x Z 1 Z x Z 1
0
z(t) = (x − t)z”(t)dt − x (1t )z”(t)dt, z (t) = tz”(t)dt − (1 − t)z”(t)dt
0 0 0 x
√
√1 ||z”||L2 x(1 − x)( x + (1 − x)) et |z 0 (x)| ≤
p
ce qui donne les majorations |z(x)| ≤ 3
3 3
√1 ||z”||L2 (x 2
+ (1 − x) 2 ). Ainsi, intégrant sur (0, 1) le carré de ces fonctions pour
3
trouver la norme H 2 , on trouve
1 2 1
||z||H 2 ≤ ( + + 1) 2 ||z”||L2 .
45 3
6.2. En supposant ȳ ∈ H 4 (]ti , ti+1 [), trouver les équations différentielles vérifiées par
ȳ. Donner les conditions aux limites aux points ti .
√
Ainsi, soit K0 = {y, y(0) = v0 , y(1) = v1 }. On a l’inégalité, pour tout y ∈ K0 ,
61
√
6 5
||y − y0 ||2H 2 ≤ J0 (y), ce qui permet d’en déduire l’existence et l’unicité d’un
minimum, puisque l’on a une fonctionnelle convexe sur un convexe. Ensuite, les
équations
R1
sur ȳ sont bien ȳ (4) = 0 sur ]tI , ti+1 [. Comme l’équation d’Euler est
2
0 y”w”dt = 0 pour w ∈ H , w(ti ) = 0∀i, on trouve que ȳ”(0) = 0, ȳ”(1) = 0 et
120 CHAPTER 8. PROBLÈMES D’EXAMENS
ȳ”(ti + 0) − ȳ”(ti − 0) = 0 puisque l’on peut prendre une fonction w quelconque telle
que w(ti0 ) = 0, w0 (ti0 ) = 1, et w à support compact dans ]ti0 −1 , ti0 +1 [ pour i0 6= 0, N .
Ainsi les conditions aux limites sont ȳ(ti ) = vi , ȳ” continue. On a répondu à la
question suivante.
6.3. Démontrer que la solution est unique* et que c’est une spline cubique de classe
C 2.
N −1
ȳ (4) − y”(1)δ10 + y”(0)δ00 + i=1 (y”(ti + 0) − y”(ti − 0))δt0 i
P
PN −1 000
+ i=1 (y (ti + 0) − y (ti − 0))δti − y 000 (1)δ1 + y 000 (0)δ0 + i λi δti = 0
000 P
6.5. Comparer S(ỹ, v) et J0 (ȳ). En déduire une comparaison des deux types d’approximation.
On voit que S(ȳ, v) = J0 (ȳ), donc, comme le minimum de S est atteint en y = ỹ,
on a S(ỹ, v) ≤ J0 (ȳ). On se place dans le cas N ≥ 1. Alors, si S(ỹ, v) = J0 (ỹ), on en
déduit, ∀y, S(y, v) ≥ J0 (ỹ) et donc ỹ = ȳ. Donc si ỹ 6= ȳ, alors S(ỹ, v) < J0 (ȳ).
1 1 1 t3 1
ỹ(t) = v0 − 1 (v0 +v2 −2v1 )+t[v1 −v0 − 1 (v0 +v2 −2v1 )]+ 1 (v0 +v2 −2v1 )
6 + 24 8 6 + 24 3 6 + 24
1
et pour t ≥ 2
3
ȳ(t) = v0 + t[v2 − v0 − (v2 + v0 − 2v1 )] + 2t3 (v0 + v2 − 2v1 )
2
1
et pour t ≥ 2 que
Jp (ky) = kp J(y).
On suppose que J est de classe C 2 et on considère sa dérivée J 0 et sa dérivée
seconde J”. Montrer les égalités:
mogène de degré p − 1 donc (J”p (y)y, w) = (p − 1)(Jp0 (y), w). Il suffit de prendre
w = y et d’appliquer le résultat précédent.
1) a) Montrer que, si y ∈ H01 (Ω) est solution de (8.2.1) au sens des distributions,
alors on a
Z Z Z
∀φ ∈ C0∞ (Ω), L(y, φ) = ∇y(x)∇φ(x)dx + y 3 φ(x)dx = u(x)φ(x)dx. (8.2.2)
Ω Ω Ω
b) Démontrer que cette égalité est vraie pour φ ∈ C ∞ (IR3 ), ainsi que pour
φ ∈ H01 (Ω).
Lorsque φ est dans H01 (Ω), c’est la limite d’une suite de fonctions de C0∞ (Ω),
φn et onRa L(y, φn ) = Ω uφn dx. La limite lorsque φn tend vers φ dans H01 (Ω)
R
notée
de Ω uφn est Ω uφdx car c’est une limite dans L2 , et de même dans H 1 (Ω). Un
R
1 1
Z Z Z
Φ(y) = |∇y(x)|2 dx − y(x)u(x)dx + (y(x))4 dx.
2 Ω Ω 4 Ω
a) Montrer que Φ est une application α−convexe continue de H01 (Ω) dans IR, et
qu’elle possède un minimum unique, noté y(u).
0 (y), v) = 3 alors (Φ0 (y)− Φ0 (z), y − z) =
R
On calcule (Φ Ω [∇y∇v + y v]dx. On trouve
3 3 2 + (y − z)2 (y 2 +
R R
Ω [(∇y − ∇z).(∇y − ∇z) + (y − z )(y − z)]dx = Ω [|∇(y − z)|
yz + z )]dx. On trouveR alors, sachant que la norme sur H0 est (∇φ)2 , la relation
2 1
R
(Φ0 (y)−Φ0 (z), y −z) ≥ Ω (∇y −∇z)2 dx = ||y −z||2H 1 , donc l’application est α−convexe
0
continue de H01 (Ω) dans IR (la continuité est une conséquence de l’inégalité y 4 ≤
R
1 R 1
( y 6 ) 2 ( Ry 2 ) 2 ≤ (c6 )3 ||y||4H 1 ). On utilise l’inégalité de Poincaré, d’où la continuité
R
du terme uydx. L’existence du minimum et l’unicité est alors une conséquence d’un
théorème du cours.
b) Donner l’équation d’Euler associée à y(u). En effectuant un choix adéquat
de φ dans l’égalité L(y(u), φ) = 0, démontrer qu’il existe une constante c1 , telle que
1√
Z Z Z
1 1
||y(u)||2H 1 (Ω) ≤ ( u2 dx) 2 ( (y(u))2 dx) 2 ≤ ( u2 dx) 2 C||y(u)||H 1 (Ω) ,
0 0
Ω Ω Ω
Ω, alors z(x) ≤ 0.
On intègre l’égalité (−∆z(x) + m(x)z(x))z + (x) = (u(x) − v(x))z+R(x). On vérifie
2 + m(x)z(x)z (x)dx =
R R R
que ∇z + | + Ω (u − v)z R+
dx. D’autre part, m(x)zR+ zdx =
2 2
R
m(x)(z + ) dx et m ≥ 0 donc nécessairement de (u−v)z+ dx ≤ 0 on déduit mz+ =
2
R
0 et (∇z+ ) dx = 0 donc z+ = 0. On en déduit que max(z, 0) = 0 donc z ≤ 0.
8.4 Partie I
1) Résultat général
On considère une fonction de C 2 (IR4 ) dans IR, notée L(p1 , p2 , q1 , q2 ). On notera
parfois p ou ~p le vecteur de composantes (p1 , p2 ) (de même pour q).
On introduit une fonction ~u(x, t) = (u1 (x, t), u2 (x, t)) une fonction de classe C 2 (IR2 )
dans IR2 . On la notera aussi u (omettant le vecteur). On veut minimiser
Z T Z a
I(u) = L(∂t ~u, ∂x ~u)dxdt
0 0
On note que p1 = ∂t u1 , p2 = ∂t u2 ...
a) Etablir les équations d’Euler en tout point (x, t) ∈]0, a[×]0, T [ pour une solution
u0 de
inf I(u)
(on ne cherche pas à préciser les conditions aux limites sur le bord du rectangle Ω
dans IR2 ).
On considère w ∈ C0∞ ([0, a] × [0, T ]). Alors on trouve
Z T Z a
I(~u + w)
~ − I(~u) = (L(∂t ~u + ∂t w,
~ ∂x ~u + w)
~ − L(∂t ~u, ∂x ~u))dxdt
0 0
Z T Z a d d d d
0
(I (u), w) = − [w1 [ (∂p1 L) + (∂q1 L)] + w2 [ (∂p2 L) + (∂q L)]]dtdx
0 0 dt dx dt dx 2
et la condition d’Euler conduit aux deux équations
(
d d
dt (∂p1 L) + dx (∂q1 L) =0
d d
dt (∂p2 L) + dx (∂q2 L) = 0.
(on pourra pour cela dériver la fonction composée ∂t (L(∂t u0 , ∂x u0 )) et une autre ex-
pression)
On dérive la fonction composée. On trouve ∂t (L(∂t ~u0 , ∂x ~u0 ) = ∂t22 ~u0 · ∂p L +
2 ~
∂tx u0 ∂q L.
En utilisant l’équation d’Euler, on trouve
d Ra
dt ( 0 [L(∂t ~
u0 ∂x ~u0 )
− ∂t~u0 · ∂p L(∂t ~u0 , ∂x ~u0 )](y, t)dy)
=
Ra 2 2 2 d
0 [∂t2 ~
u0 · ∂p L + ∂tx ~u0 ∂q L − ∂t2 ~u0 ∂p L − ∂t ~u0 dt (∂p L(∂t ~u0 , ∂x ~u0 ))]dy
=
Ra 2 d
0 [∂tx ~
u0 ∂q L + ∂t ~u0 dx (∂q L(∂t ~u0 , ∂x ~u0 ))]dy
inf I(u)
inf I(u) inf I(u)
u(x, 0) = u0 (x)
u(x, 0) = u0 (x) u(x, 0) = u0 (x)
(P1 ) (P2 ) (P3 ) u(x, T ) = uf (x) .
u(x, T ) = uf (x) u(x, T ) = uf (x)
u(0, t) = 0
u(0, t) = 0
u(a, t) = 0
a) Etablissement de l’équation
On étudie les petits déplacements d’une corde autour de sa position d’équilibre
(OA), O(0,0,0), A(a, 0,0).
La position d’un point de la courbe est (x, u1 (x, t), u2 (x, t)) = (x, u(x, t)).
La densité de la corde est ρ0 , et cette corde est soumise à la tension T~0 , de module
constant T0 , dirigée suivant le vecteur tangent unitaire τ .
Ecrire le bilan des forces et la relation fondamentale de la dynamique pour un
segment [x, x + ∆x] en négligeant tous les termes d’ordre au moins 2 en u. En faisant
tendre ∆x vers 0, en déduire l’équation
∂ 2 ~u ∂ 2 ~u
ρ0 = T0 .
∂t2 ∂x2
laissé en exercice (voir méthodes mathématiques pour la physique, de L. Schwartz)
b) Etablir la relation, pour ~u0 solution de l’équation précédente
dE d
Z a 1 ∂~u ∂~u
= (ρ0 ( )2 + T0 ( )2 )(y, t)dy = ∂t ~u∂x ~u(a, t) − ∂t~u∂x ~u(0, t).
dt dt 0 2 ∂t ∂x
1 ∂~u 2
∂t ( (ρ0 ( )2 ) = T0 ∂t ~u0 ∂x22 ~u0 = T0 ∂x (∂t ~u0 ∂x ~u0 ) − T0 ∂tx (~u0 )∂x ~u0
2 ∂t
et on intègre sur [0, a], remarquant que le dernier terme est la dérivée par rapport à t
de 12 T0 (~u0 )2 .
Donner les solutions L(p, q) de l’égalité
1 ∂L
(ρ0 p2 + T0 q 2 ) = L(p, q) − p (p, q).
2 ∂p
(on dérivera cette égalité par rapport à p1 et p2 ).
En dérivant par rapport à p, on trouve ρ0 p = −p∂p22 L, ce qui donne ρ0 = −∂p22 L.
Ainsi L = − 21 ρ0 p2 +C(q)p+D(q). On remplace dans l’équation et on trouve − 21 ρ0 p2 +
C(q)p + D(q) + ρ0 p2 − pC(q) = 12 (ρ0 p2 + T0 q 2 ), donc C(q) est indeterminé et D(q) =
1 2
2 T0 q .
c) Montrer que l’équation des cordes vibrantes est le système des équations d’Euler
pour le Lagrangien L(p, q) = 21 T0 q 2 − 12 ρ0 p2 . Peut-on appliquer la théorie classique de
minimisation?
On applique le résultat du 1, a), car ∂p L = −ρ0 p, ∂q L = T0 q.
Déduire de 1) que
• lorsque les deux extrémités de la corde sont fixées, les conditions en 0 et a sont
les conditions de Dirichlet homogènes u = 0
• lorsqu’une extrémité de la corde est libre, la condition à cette extrémité s’écrit
∂~u
∂x = 0, qui est la condition de Neumann. En déduire que l’énergie E est conservée.
C’est la traduction des résultats de 1).
8.5 Partie II
On cherche à minimiser la valeur moyenne de la tension J:
8.5. PARTIE II 127
1
Z T
J(v0 ) = v0 (t)dt
T 0
sous les conditions v0 (0) = 0, v0 (T ) = V (c’est à dire un système dans lequel on établit
une tension V en un temps T )
et sous la contrainte d’énergie dissipée par effet Joule constante:
Z T
K= Ri2 (t)dt
0
où le courant électrique est produit par la mise sous tension v0 (t) d’un condensateur
C et d’une résistance R disposés en parallèle (même tension).
a) Peut-on résoudre ce problème en considérant une perturbation εw(t) de la ten-
sion v0 (t)? Justifier.
b) On se donne ε1 et ε2 , et on perturbe la solution cherchée par ε1 w1 (t) + ε2 w2 (t).
Ecrire les conditions d’optimalité.
Montrer qu’il existe un réel λ tel que ces conditions d’optimalité correspondent aux
conditions d’optimalité du lagrangien augmenté J + λK, K étant considéré comme
une fonction de v(t). On pourra supposer à cet effet w2 fixé. On admettra pour la
suite ce résultat si il n’a pas été démontré.
c) On considère λ ∈ IR. Déterminer v0 qui réalise le minimum de J(v)+λK(v), v(0) =
0, v(T ) = 0.
d) Déterminer λ de sorte que le v0 trouvé au c) conduise à i0 (t) tel que 0T R(i0 (t))2 =
R
[1] J.C. Culioli: Optimisation: Cours à l’Ecole des Mines publié aux éditions Ellipses
(1994)
129