Optimisation sans contraintes - Le Cermics

´
Deux exemples tir´es du cours d’Economie
Consommation : maximisation d’utilit´e sous contrainte de budget
N
sup U (x1 . . . xN ),
x∈K
K=
x ∈ RN ; xi
Optimisation sans contraintes
0,
pi xi
R
i=1
U : fonction d’utilit´e, xi : quantit´e de bien i consomm´ee,
pi : prix du bien i, R : budget disponible
Gabriel STOLTZ
Production : minimisation du coˆut `a contrainte de production fix´ee
[email protected]
(CERMICS, Ecole des Ponts & Equipe-projet MATHERIALS, INRIA Rocquencourt)
N
inf
x∈K
i=1
,
K = x ∈ RN ; xi
0, f (x1 . . . xN ) = y
xi : facteur de production, pi : prix du facteur de production i,
y : quantit´e de bien `a produire, f : fonction de production
Calcul scientifique, Ecole des Ponts, 19 f´evrier 2015
Gabriel Stoltz (ENPC/INRIA)
p i xi
Ecole des Ponts, f´
evrier 2015
1/1
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
1 / 29
Exemples tir´e des cours de m´ecanique
Membrane ´elastique `a l’´equilibre sous un chargement vertical f
inf E(v),
v∈V
V = H01 (Ω),
E(v) =
1
2
ˆ
Ω
|∇v|2 −
ˆ
fv
Ω
u : d´eplacement (vertical), Ω : configuration de r´ef´erence
f
Formalisation math´ematique
Ω
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
1111111111111111111111111
0000000000000000000000000
0000000000000000000000000
1111111111111111111111111
∂Ω
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
0000000000000000000000000
1111111111111111111111111
u
Minimisation de l’´energie ´electronique de l’atome d’hydrog`ene
inf
ψ∈K
ˆ
R3
1
|ψ(x)|2
|∇ψ(x)|2 −
dx ,
2
|x|
Gabriel Stoltz (ENPC/INRIA)
K = ψ ∈ H 1 (R3 , C)
ψ
L2
Ecole des Ponts, f´
evrier 2015
=1
2 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
3 / 29
Un peu de vocabulaire (1)
Un peu de vocabulaire (2)
• On dit que u est un minimiseur local de J sur V si
• On consid`ere...
u∈V
un espace de Hilbert V , de dimension finie ou infinie
une fonctionnelle J : V → R : crit`ere ou fonction coˆ
ut
et
∃δ > 0, J(u)
o`
u BV (u, δ) = {v ∈ V ; u − v
V
J(v) ∀v ∈ BV (u, δ)
δ}
• Exemple 1D: V = R si bien que J : R → R
Probl`eme d’optimisation sans contrainte
J(v)
Chercher u tel que
u∈V
et
J(u)
J(v)
∀v ∈ V
minimiseurs locaux
minimiseur global
• On a donc J(u) = inf J(v) = minJ(v)
v∈V
v∈V
v∈R
• On dit que u est un minimiseur global de J sur V
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
4 / 29
• On ne consid`ere que des probl`emes de minimisation
→ maximiser J revient `a minimiser −J !
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
Un peu de vocabulaire (3)
Objectifs du chapitre d’optimisation
• Ensemble des ´etats admissibles : sous-ensemble non-vide K ⊂ V
• Minimisation : avec et sans contraintes, en dimension finie ou infinie
Probl`eme d’optimisation avec contraintes
• Etude th´
eorique :
Chercher u tel que
u∈K
et
J(u)
J(v)
connaitre des conditions suffisantes d’existence et unicit´e du
minimiseur global
´
Etablir
des conditions n´ecessaires d’optimalit´e permettant de
caract´eriser un minimiseur (local)
∀v ∈ K
• On a donc J(u) = inf J(v) = minJ(v)
v∈K
v∈K
• M´
ethodes num´
eriques : fond´ees sur ladite caract´erisation
• On dit que u est un minimiseur global de J sur K
• On dit que u est un minimiseur local de J sur K si
u∈K
et
∃δ > 0, J(u)
• Contraintes : deux situations g´en´eriques
J(v) ∀v ∈ BV (u, δ) ∩ K
K=
• Question : les exemples du d´ebut du cours sont-ils en dimension finie
ou infinie ? Avec ou sans contrainte ?
Gabriel Stoltz (ENPC/INRIA)
5 / 29
Ecole des Ponts, f´
evrier 2015
{v ∈ V ; Φ(v) = 0}
{v ∈ V ; Φ(v) 0}
o`
u Φ : V → Rm et Φ(v)
6 / 29
Gabriel Stoltz (ENPC/INRIA)
contraintes ´egalit´e
contraintes in´egalit´e
0 signifie Φi (v)
0, ∀i ∈ {1 . . . m}
Ecole des Ponts, f´
evrier 2015
7 / 29
Diff´erentiation et convexit´e : motivation 1D
• V = R et J : R → R, suppos´ee d´erivable
• Si v est minimiseur local de J sur V , alors J (v) = 0. On dit que v est
point critique de J
J(v)
points critiques
maximiseur local
Outils techniques :
diff´erentiation et convexit´e
minimiseurs locaux
minimiseur global
v∈R
ˆ
• Etre
point critique est condition n´ecessaire d’optimalit´e locale
• Si J convexe : ˆetre point critique est une condition suffisante
d’optimalit´e globale
J(v)
minimiseur global et unique point critique
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
8 / 29
Diff´erentiation (1)
v∈R
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
9 / 29
Diff´erentiation (2)
• Soit V un espace de Hilbert et J : V → R
Diff´erentiabilit´e
• J est diff´erentiable sur V si J est diff´erentiable en tout v ∈ V
On dit que J est diff´erentiable en v ∈ V s’il existe une forme lin´eaire
continue J (v) ∈ V telle que, pour tout w ∈ V ,
• La diff´erentielle de J est l’application J : V → V
J(v + w) = J(v) + J (v), w
V ,V
+ o( w
• Exemple : en dimension finie avec V = RN , on a
V)
N
∀w = (w1 . . . wN ) ∈ RN ,
• En pratique :
d´evelopper J(v + w) autour de J(v)
v´erifier que T1 (v, w) est lin´eaire et continue en w ∈ V
Gabriel Stoltz (ENPC/INRIA)
i=1
∂J
(v)wi = ∇J(v), w
∂vi
V
• Relation diff´erentielle/gradient plus subtile en dimension infinie
→ utiliser plutˆ
ot la diff´
erentielle
J(v + w) = J(v) + T1 (v, w) + T2 (v, w)
V
V ,V
=
→ on peut ainsi identifier diff´erentielle et gradient
regrouper les termes d’ordre 1 en w et les termes d’ordre sup´erieur
montrer que T2 (v, w)/ w
J (v), w
→ 0 lorsque w → 0 dans V
Ecole des Ponts, f´
evrier 2015
10 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
11 / 29
Convexit´e (1)
Convexit´e (2)
• Soit V un espace vectoriel r´eel
D´efinition de la convexit´e
• Illustration 1D de la forte convexit´e : V = R, J : R → R
La fonctionnelle J : V → R est convexe sur V si, ∀(v, w) ∈ V × V ,
∀θ ∈ [0, 1],
J(θv + (1 − θ)w) θJ(v) + (1 − θ)J(w)
θJ(v) + (1 − θ)J(w)
• Soit V un espace vectoriel r´eel norm´e
D´efinition de la forte convexit´e
La fonctionnelle J : V → R est fortement convexe de param`etre α > 0 sur
V si, ∀(v, w) ∈ V × V , ∀θ ∈ [0, 1],
J(θv + (1 − θ)w)
J(w)
J(v)
θ(1 − θ)
θJ(v) + (1 − θ)J(w) − α
v−w
2
2
V
α
θ(1 − θ)
v−w
2
2
V
J(θv + (1 − θ)w)
v θv + (1 − θ)w
w
On dit aussi que J est α-convexe
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
12 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
Convexit´e : caract´erisations alternatives (1)
Convexit´e : caract´erisations alternatives (2)
• Fonctionnelles J : V → R diff´erentiables
• Illustration 1D : V = R, J : R → R
13 / 29
• La fonctionnelle J est convexe sur V si et seulement si
∀(v, w) ∈ V × V , J(w)
J(v) + J (v), w − v
∀(v, w) ∈ V × V , J (w) − J (v), w − v
V ,V
V ,V
J(w)
0
• La fonctionnelle J est α-convexe sur V si et seulement si
∀(v, w) ∈ V × V , J(w)
J(v) + J (v), w − v
∀(v, w) ∈ V × V , J (w) − J (v), w − v
V ,V
α
w−v
V ,V
2
α w − v 2V
+
2
V
J (w), w − v
J(v)
• En pratique, les caract´
erisations “sym´
etriques” sont souvent les
plus utiles !
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
J (v), w − v
14 / 29
v
Gabriel Stoltz (ENPC/INRIA)
w
Ecole des Ponts, f´
evrier 2015
15 / 29
Convexit´e : un exemple
• V Hilbert, u ∈ V fix´e, J : V → R avec J(v) =
1
v−u
2
2
V
• Montrons que J est 1-convexe (avec ´egalit´e)
• Calcul direct : consid´erer (v, w) ∈ V × V , θ ∈ [0, 1], et se lancer...
1
1
θv + (1 − θ)w − u 2V =
θ(v − u) + (1 − θ)(w − u) 2V
2
2
1
1
= θ2 v − u 2V + (1 − θ)2 w − u 2V + θ(1 − θ)(v − u, w − u)V
2
2
1
= θJ(v) + (1 − θ)J(w) − θ(1 − θ) v − u 2V + w − u 2V − 2(v − u, w − u)V
2
1
= θJ(v) + (1 − θ)J(w) − θ(1 − θ) v − w 2V
2
J(θv + (1 − θ)w) =
• Utilisation de la diff´erentielle : J (v), w
On a J (w) − J (v), w − v
V ,V
V ,V
= (v − u, w)V
= (w − u) − (v − u), w − v
Gabriel Stoltz (ENPC/INRIA)
V
= w−v
2
V
Ecole des Ponts, f´
evrier 2015
16 / 29
Existence d’un minimiseur global
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
• Unicit´e du minimiseur si J strictement convexe
v∈V
∀(v, w) ∈ V × V, ∀θ ∈ ]0, 1[,
Conditions suffisantes d’existence d’un minimiseur global
J est continue V → R
V
• Si J est fortement convexe, alors J est strictement convexe et il existe
γ > 0, δ ∈ R tels que
→ +∞)
J est convexe (inutile si V est de dimension finie)
∀v ∈ V,
• Quelques commentaires sur ces hypoth`eses...
J(v)
γ v
2
V
+δ
• R´esultat tr`es utile en pratique :
Il peut y avoir plusieurs minima globaux/une infinit´e. Exemple ?
Conditions suffisantes d’existence/unicit´e du minimiseur global
Si J est diff´erentiable alors elle est continue (utile en pratique)
V est un espace de Hilbert
Convexit´e n’implique pas continuit´e en dimension infinie
J pas coercive : infimum (et pas minimum) en g´en´eral. Exemple ?
Ecole des Ponts, f´
evrier 2015
J(θv + (1 − θ)w) < θJ(v) + (1 − θ)J(w)
Preuve : u1 = u2 deux minimiseurs, contradiction car
1
u1 + u2
1
J
< J(u1 ) + J(u2 ) = inf J(v)
v∈V
2
2
2
V est un espace de Hilbert
Gabriel Stoltz (ENPC/INRIA)
17 / 29
Existence/unicit´e du minimiseur global
• Probl`eme inf J(v) pour V espace vectoriel
J est coercive (i.e. J(v) → +∞ lorsque v
Minimisation sans contrainte :
r´esultats th´eoriques
18 / 29
J est continue V → R
J est α-convexe
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
19 / 29
Condition d’Euler (1)
• On dit que v est point critique de J si J (v) = 0 (∈ V ), i.e.
∀w ∈ V,
J (v), w
V ,V
=0
Condition n´
ecessaire pour ˆetre minimiseur local
Conditions n´ecessaires
voire suffisantes
V espace de Hilbert, J : V → R fonctionnelle diff´erentiable
u minimiseur local de J =⇒ u point critique de J : J (u) = 0 (∈ V )
• La condition J (u) = 0 porte le nom de condition d’Euler
• Preuve : Soit v ∈ V arbitraire. Pour t ∈ R assez petit,
J(u)
J(u + tv) = J(u) + t J (u), v
V ,V
+ o(t)
limite t → 0+ : J (u), v V ,V
0
changer v en −v : J (u), v V ,V = 0
v ´etant arbitraire, on a J (u) = 0 (∈ V )
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
20 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
Condition d’Euler (2)
Cas des fonctionnelles quadratiques (1)
Condition n´ecessaire et suffisante
• En dimension finie : V = RN , A ∈ RN,N , b ∈ RN et
1
1
J(v) = (v, Av)RN − (b, v)RN =
2
2
Si J est convexe, la condition d’Euler est une condition suffisante
d’optimalit´e globale
J (u) = 0 (∈ V ) =⇒ u est un minimiseur global de J sur V
• Par un calcul facile :
1
∂J
(v) =
∂vi
2
• Cons´equence imm´ediate du fait que, par convexit´e de J,
∀v ∈ V,
J(v)
J(u) + J (u), v − u
∇J(v) =
V ,V
J(u) + 0
i,j=1
N
Aij vi vj −
bi vi
i=1
N
j=1
(Aij + Aji )vj − bi (1
i
N ), soit
1
A + AT v − b
2
Lorsque A est sym´
etrique
= J(u)
Gabriel Stoltz (ENPC/INRIA)
N
21 / 29
R´esoudre le syst`eme lin´eaire Av = b revient `a chercher un point critique
de J (car ∇J(v) = Av − b)
Ecole des Ponts, f´
evrier 2015
22 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
23 / 29
Cas des fonctionnelles quadratiques (2)
1
• Dimension infinie : J(v) = a(v, v) − b, v
2
V ,V
• a forme bilin´eaire continue sur V × V , b forme lin´eaire continue sur V
• J est diff´erentiable sur V avec
1
a(v, w) + a(w, v) − b, w
J (v), w V ,V =
2
∀w ∈ V
V ,V
M´ethodes num´eriques
Lorsque a est sym´
etrique (a(v, w) = a(w, v))
R´esoudre le probl`eme a(v, w) = b, w
point critique de J
V ,V
∀w ∈ V , revient `a chercher un
• Si a sym´etrique : a coercive (de param`etre α) ssi J est α-convexe
J (w) − J (v), w − v
V ,V
= a(w, w − v) − b, w − v
V ,V
− a(v, w − v) + b, w − v
= a(w − v, w − v)
Gabriel Stoltz (ENPC/INRIA)
α w−
V ,V
v 2V
Ecole des Ponts, f´
evrier 2015
24 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
M´ethode de gradient (1)
M´ethode de gradient (2)
• Dimension finie : discr´etisation du probl`eme sur une base idoine,
fonctionnelle J diff´erentiable
• Initialisation
choisir v 0 ∈ V et poser k := 0
choisir le pas λ > 0
• Objectif : construire une suite (v k )k∈N := v 0 , v 1 , . . . telle que
vk → v
o`
u
fixer un seuil de convergence ε > 0
∇J(v) = 0
• It´
erations (boucle sur k)
On construit donc un point critique de J de mani`ere it´erative
calculer ∇J(v k )
choisir comme direction de descente dk = −∇J(v k )
• Principe : pour v k ∈ V donn´e, chercher une direction de descente
dk ∈ V telle que
pour t suffisamment petit,
J(v k + tdk )
Comme J v k + tdk = J(v k ) + t ∇J(v k ), dk
V
d´eterminer v k+1 selon la formule
v k+1 = v k + λdk
J(v k )
+ o(t), on peut proposer
dk = −∇J(v k )
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
25 / 29
26 / 29
test de convergence :
v k+1 − v k
v0 V
V
ε ou
|J(v k+1 ) − J(v k )|
J(v 0 )
• M´ethode de gradient `
a pas fixe : choix de λ ? convergence ?
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
ε
27 / 29
M´ethode de gradient (3)
En r´esum´e et `a venir...
Aujourd’hui : optimisation sans contraintes
exemples de probl`emes d’optimisation, vocabulaire
diff´erentiabilit´e, convexit´e
existence/unicit´e de minimiseurs (optimisation sans contraintes)
conditions n´ecessaires (voire suffisantes) d’optimalit´e
algorithme de gradient
Jeudi 5 mars : optimisation avec contraintes
existence/unicit´e de minimiseurs
conditions n´ecessaires : in´equations d’Euler–Lagrange
Jeudi 12 mars : m´ethodes num´eriques
convergence de l’algorithme du gradient
gradient projet´e (contraintes)
TP informatique : jeudi 12 mars
• La convergence est tr`es lente si λ est trop petit
• Si λ est trop grand, on peut ne pas converger !
Gabriel Stoltz (ENPC/INRIA)
TDs : 5 et 26 mars
Ecole des Ponts, f´
evrier 2015
28 / 29
Gabriel Stoltz (ENPC/INRIA)
Ecole des Ponts, f´
evrier 2015
29 / 29

Download Report