´ 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
© Copyright 2024 ExpyDoc