COURS OPTIMISATION Cours à l'ISFA, en M1SAF Ionel Sorin ...

Publié par

  • cours - matière potentielle : en amphi
  • cours - matière potentielle : optimisation
COURS OPTIMISATION Cours à l'ISFA, en M1SAF Ionel Sorin CIUPERCA 1
  • classe cm sur ω
  • applications de la théorie du point selle
  • méthodes de relaxation
  • inégalité de cauchy-schwarz
  • optimisation avec contraintes
  • général difficile
  • vecteurs
  • vecteur
Publié le : mercredi 28 mars 2012
Lecture(s) : 135
Tags :
Source : math.univ-lyon1.fr
Nombre de pages : 65
Voir plus Voir moins

COURS OPTIMISATION
Cours à l’ISFA, en M1SAF
Ionel Sorin CIUPERCA
1Table des matières
1 Introduction 4
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Le problème général d’optimisation . . . . . . . . . . . . . . . . . . . . . . 4
2 Quelques rappels de calcul différentiel, analyse convexe et extremum 5
2.1 Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.1 Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.1.2 Rappel gradient et hessienne . . . . . . . . . . . . . . . . . . . . . 6
2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.1 Rappel fonctions convexes . . . . . . . . . . . . . . . . . . . . . . . 9
2.2.2 Fonctions elliptiques, fonctions coercives . . . . . . . . . . . . . . . 11
2.2.3 Exemples des fonctions elliptiques . . . . . . . . . . . . . . . . . . . 14
2.3 Conditions nécéssaires de minimum . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Existence et unicité d’un point de minimum . . . . . . . . . . . . . . . . . 17
3 Optimisation sans contraintes 20
3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 24
3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2.1 Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 26
3.2.2 Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 27
3.3 La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 30
3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.3.2 Cas d’une fonction J quelconque . . . . . . . . . . . . . . . . . . . 35
4 Optimisation avec contraintes 36
4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 37
4.2 Optimisation sous contraintes d’inégalités . . . . . . . . . . . . . . . . . . . 38
4.2.1 Conditionsd’optimalitédepremierordre:multiplicateursdeKarush-
Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.2.2 Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 46
24.2.3 Applications de la théorie du point selle à l’optimisation . . . . . . 48
4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 50
4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.2des de projection . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3.3 Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 56
4.3.4de d’Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3Chapitre 1
Introduction
1.1 Motivation
Voir cours en amphi
1.2 Le problème général d’optimisation
On se donne :
n1. Une fonction J : IR 7! IR (fonction coût)
n2. Un ensemble U IR (ensemble des contraintes)
On cherche à minimiser J sur U, c’est à dire, on cherche x 2U tel que
J(x ) = minJ(x)
x2U
ou équivalent
J(x )J(x); 8x2U:
46
Chapitre 2
Quelques rappels de calcul différentiel,
analyse convexe et extremum
2.1 Rappel calcul différentiel
2.1.1 Quelques Notations
n
1. Pour toutn2 IN ; IR désigne l’espace euclidien IRIRIR ( “produitn fois”).
n TEn général un vecteur x2 IR sera noté x = (x ;x ;x ) (vecteur colonne).1 2 n
n
2. On note e ;e ;e les éléments de la base canonique de IR , où e est le vecteur1 2 n i
nde IR donné par :

0 si j =i
(e ) = = ; 8i;j = 1; 2n (2.1)i ijj 1 si j =i
(symboles de Kronecker).
n3. Pour tous x;y2 IR on note par < x;y >2 IR le produit scalaire de x et y, qui
est donné par
nX
<x;y>= x y:i i
i=1
n4. Pour tout x2 IR on note parkxk 0 la norme euclidienne de x, donnée par
v
u nXup t 2kxk = <x;x> = x :i
i=1
nPour tous x2 IR et r > 0 on notera par B(x;r) la boule ouverte du centre x et
rayon r, donnée par
nB(x;r) =fy2 IR ; ky xk<rg:
5n n5. Si a;b2 IR on note [a;b] le sous-ensemble de IR donné par
[a;b] =fa +t(b a) (1 t)a +tb; t2 [0; 1]g:
L’ensemble [a;b] est aussi appellé le segment reliant a à b.
Remarques :
[a;b] = [b;a] (Exo!)
Si a;b2 IR avec a < b alors on retrouve le fait que [a;b] désigne l’intervalle des
nombres x2 IR tels que axb.
6. Rappellons aussi l’inégalité de Cauchy-Schwarz :
nj<x; y>jkxkkyk 8x;y2 IR :
2.1.2 Rappel gradient et hessienne
nSoit
IR un ouvert et f :
! IR.
m m1. On dit que f est de classe C sur
(f 2 C ( )) si toutes les dérivées partielles
jusqu’à l’ordre m existent et sont continues.
2. Pour tout x2
et tout i2f1; 2; ;ng on note (quand9)
@f 1
(x) = lim [f(x +te ) f(x)]:i
t7!0@x ti
(c’est la dérivée partielle de f en x de direction x .)i
3. Pour tout x2
on note (quand9)
T
@f @f @f nrf(x) = ; ; 2 IR ; 8x2

@x @x @x1 2 n
(le gradient de f en x).
n4. Pour tous x2
et h2 IR on note (quand9)
@f 1
(x) = lim [f(x +th) f(x)]:
t7!0@h t
(c’est la dérivée directionnelle de f en x de direction h).
Remarques :
@fi) (x) = 0
@0
@f @fii) (x) = (x)
@x @ei i
Nous rappellons aussi la formule :
@f n(x) =<rf(x);h>; 8x2
8h2 IR :
@h
66
6
6
6
25. Pour x2
on note (quand9)r f(x) = la matrice carrée2M (IR) donnée parn
2 @ f2r f(x) = (x); 8i;j = 1; 2;n:
ij @x@xi j
2(r f(x) s’appelle aussi la matrice hessienne de f en x).
2 2Remarque : Si f2 C ( ) alorsr f(x) est une matrice symmétrique 8x2

(c’est le Théorème de Schwarz).
2Proposition 2.1. (lien entrer etr )
2a) La i - ème ligne der f(x) est le transposé du gradient du i - ème élément derf.
b) On a
2 nr f(x)h =r<rf(x);h>; 8x2
;8h2 IR :
Démonstration. a) évidente
b) On a :
!
n n 2X X @ @ @f @ f 2<rf(x);h>= (x)h = (x)h = r f(x)h :j j i@x @x @x @xxi i j i j
j=1 j=1
Quelques exemples importantes :
n 21. Si f : IR ! IR est une fonction constante alorsrf =r f = 0.
n2. Soit f : IR ! IR définie par
nf(x) =<a; x> 8x2 IR ;
noù a2 IR est un vecteur donné (c’est à dire,f est une fonction linéaire). Alors on
@fcalcule facilement : =a ; donck@xk
rf =a
(le gradient est constant).
Ceci nous donne
2r f = 0:
n3. Soit f : IR ! IR donnée par
nf(x) =<Ax; x> 8x2 IR ;
où A2M (IR) est un matrice carrée, réelle, de taille n (c’est à dire, f est unen
fonction quadratique). Alors pour un p2f1; 2;ng fixé, on peut écrire
n n n nX X X X
2f(x) = A xx =A x + A x x + A xx + A xxij i j pp pj p j ip i p ij i jp
i;j=1 j=1;j=p i=1;i=p i;j=1;i=p;j=p
76
6
ce qui nous donne
n n n nX X X X@f T= 2A x + A x + A x = A x + A x = (Ax) +(A x) :pp p pj j ip i pj j ip i p p
@xp
j=1;j=p i=1;i=p j=1 i=1
Nous avons donc obtenu :
T nrf(x) = (A +A )x; 8x2 IR :
On peut aussi écrire
nX@f T(x) = (A +A ) x ; 8i = 1; ;n:ik k
@xi
k=1
On a alors immédiatement :
2@ f T(x) = (A +A ) ; 8i;j = 1; ;n:ij
@x@xi j
c’est à dire
2 T nr f(x) =A +A ; 8x2 IR
(donc la hessienne de f est constante).
TRemarque : En particulier, si A est symmétrique (c’est à dire A =A ) alors
nr <Ax; x> = 2Ax; 8x2 IR :
2 nr <Ax; x> = 2A; 8x2 IR :
2.1.3 Rappel formules de Taylor
Proposition 2.2. (sans preuve)
n nSoit
IR ouvert, f :
7! IR;a2
et h2 IR tels que [a;a +h]
. Alors :
11. Si f2C ( ) alors
R 1
i)f(a +h) =f(a) + <rf(a +th);h> dt
0
(formule de Taylor à l’ordre 1 avec reste intégral).
ii)f(a +h) =f(a)+<rf(a +h);h> avec 0<< 1
(formule de Taylor - Maclaurin à l’ordre 1)
iii)f(a +h) =f(a)+<rf(a);h> +o(khk)
(formule de Taylor - Young à l’ordre 1)
22. Si f2C ( ) alors
R 1 2i)f(a +h) =f(a)+<rf(a);h> + (1 t)<r f(a +th)h;h> dt
0
(formule de Taylor à l’ordre 2 avec reste intégral).
1 2ii)f(a +h) =f(a)+<rf(a);h> + <r f(a +h)h;h> avec 0<< 1
2
(formule de Taylor - Maclaurin à l’ordre 2)
1 2 2iii)f(a +h) =f(a)+<rf(a);h> + <r f(a)h;h> +o(khk )
2
(formule de Taylor - Young à l’ordre 2).
86
kRemarque : Dans la proposition précédente la notation o(khk ) pour k2 IN signifie
k kune expression qui tend vers 0 plus vite quekhk (c’est à dire, si on la divise parkhk , le
résultat tend vers 0 quandkhk tend vers 0).
2.2 Convexité
2.2.1 Rappel fonctions convexes
nDéfinition 2.3. Un ensemble U IR est dit convexe si8x;y 2 U on a [x;y] U
(quelque soit deux points dans U, tout le segment qui les unit est dans U).
nDéfinition 2.4. Soit U IR un ensemble convexe et f :U! IR une fonction.
1. On dit que f est convexe sur U si
f(tx + (1 t)y)tf(x) + (1 t)f(y); 8x;y2U; 8t2 [0; 1]
2. On dit que f est strictement convexe sur U si
f(tx + (1 t)y)<tf(x) + (1 t)f(y); 8x;y2U avecx =y; 8t2 ]0; 1[:
3. On dit quef estconcave (respectivement strictement concave) si f est convexe
(respectivement strictement convexe).
Remarque : Il est facile de voir que toute fonction strictement convexe est convexe,
mais que la réciproque n’est pas vraie en général.
Par exemple une application affine f(x) =Ax +b est convexe (et aussi concave) mais elle
n’est pas strictement convexe (ni strictement concave).
On montre facilement le résultat utile suivant :
n Proposition 2.5. SoitU IR un ensemble convexe, p2 IN ,f ;f ; ;f :U! IR des1 2 p
fonctions convexes et ; ; ; des constantes strictement positives.1 2 n
Posons f = f + f + f . Alors on a :1 1 2 2 p p
a) La fonction f est convexe (donc toute combinaison linéaire avec des coefficients stric-
tement positifs de fonctions convexes est convexe).
a) Si au moins une des fonctionsf ; ;f est strictement convexe alorsf est strictement1 p
convexe.
Démonstration. Laissée en exercice!
Il est en général difficile de vérifier la convexité d’une fonction en utilisant uniquement
2 4la définition (essayez avec f(x) = x ou avec f(x) = x !) La proposition suivant donne
des critères de convexité plus faciles à utiliser pour montrer la convexité ou la convexité
stricte d’une fonction.
96
6
6
6
nProposition 2.6. Soit
IR ouvert,U
avecU convexe etf :
7! IR une fonction.
Alors on a :
Partie I (caractérisation de la convexité avec “r”).
1Supposons que f est de classe C . Alors
1. f est convexe sur U si et seulement si :
f(y)f(x) +<rf(x);y x>; 8x;y2U
2. f est strictement convexe sur U si et seulement si :
f(y)>f(x) +<rf(x);y x>; 8x;y2U avec x =y:
3. f est convexe sur U si et seulement sirf est monotone sur U, c’est à dire
<rf(y)r f(x); y x> 0 8x;y2U:
4. Sirf est strictement monotone sur U (c’est à dire :
<rf(y)r f(x); y x>> 0 8x;y2U avec x =y )
alors f est strictement convexe sur U.
2Partie II (caractérisation de la convexité avec “r ”).
2Supposons que f est de classe C . Alors
1. f est convexe sur U si et seulement si :
2<r f(x)(y x);y x> 0; 8x;y2U
2. Si
2<r f(x)(y x);y x>> 0; 8x;y2U avec x =y
alors f est strictement convexe sur U.
Remarques :
n1. Dans le cas particulier où
=U = IR alors les deux inégalités de la Partie II de
la proposition précédente peuvent s’écrire :
2 n<r f(x)h;h> 0; 8x;h2 IR
et respectivement
2 n<r f(x)h;h>> 0; 8x;h2 IR ; avec h = 0:
10

Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.