Optimisation non linéaire sans contraintes Recherche opérationnelle GC-SIE.

  • Published on
    04-Apr-2015

  • View
    104

  • Download
    2

Embed Size (px)

Transcript

  • Page 1
  • Optimisation non linaire sans contraintes Recherche oprationnelle GC-SIE
  • Page 2
  • Conditions doptimalit
  • Page 3
  • Conditions d'optimalitMichel Bierlaire3 Fonctions une variable min f(x), x IR Dfinitions : x* est un maximum local de f sil existe a > 0 tel que f(x*) f(x) pour tout x ]x*- a,x*+a[ x* est un minimum local de f sil existe a > 0 tel que f(x*) f(x) pour tout x ]x*- a,x*+a[ Lintervalle ]x*-a,x*+a[ est appel un voisinage de x*
  • Page 4
  • Conditions d'optimalitMichel Bierlaire4 Fonctions une variable Dfinitions : x* est un maximum local strict de f sil existe a > 0 tel que f(x*) f(x) pour tout x ]x*-a,x*+a[ x* est un minimum local strict de f sil existe a > 0 tel que f(x*) f(x) pour tout x ]x*-a,x*+a[
  • Page 5
  • Conditions d'optimalitMichel Bierlaire5 Fonctions une variable Dfinitions : x* est un maximum global de f si f(x*) f(x) pour tout x IR x* est un minimum global de f si f(x*) f(x) pour tout x IR Un extremum est un minimum ou un maximum.
  • Page 6
  • Conditions d'optimalitMichel Bierlaire6 Fonctions une variable Minimum global Minimum local Maximum local 2a
  • Page 7
  • Conditions d'optimalitMichel Bierlaire7 Fonctions une variable Dfinition : Un point x o la tangente est horizontale, cest--dire tel que f(x)=0, est appel un point critique ou point stationnaire. Thorme de Fermat : Si une fonction continue f possde un extremum local en x*, et si f(x*) existe, alors f (x*) = 0.
  • Page 8
  • Conditions d'optimalitMichel Bierlaire8 Fonctions une variable La condition f(x*) = 0 est une condition ncessaire doptimalit pour une fonction diffrentiable. Attention : ce nest pas une condition suffisante. Rappel: Si P Q, alors P est suffisante et Q est ncessaire. x* optimal f(x*) = 0
  • Page 9
  • Conditions d'optimalitMichel Bierlaire9 Fonctions une variable Tangente horizontale mais pas un maximum, ni un minimum
  • Page 10
  • Conditions d'optimalitMichel Bierlaire10 Fonctions une variable Test de premier ordre : Soit une fonction diffrentiable f, et x* un point critique. Sil existe a > 0 tel que f(x) > 0 si x*-a < x < x* f(x) < 0 si x* < x < x*+a Alors x* est un maximum local de f. Soit une fonction diffrentiable f, et x* un point critique. Sil existe a > 0 tel que f(x) < 0 si x*-a < x < x* f(x) > 0 si x* < x < x*+a Alors x* est un minimum local de f.
  • Page 11
  • Conditions d'optimalitMichel Bierlaire11 Fonctions une variable Soit f(x) = x 3 + 6 x 2 + 9 x + 8 f '(x) = 3 x 2 + 12 x + 9 = 3(x+3)(x+1) Points critiques : x 1 = -3 et x 2 = -1 Signes de f '(x) : x 1 maximum local x 2 minimum local -3 + + -
  • Page 12
  • Conditions d'optimalitMichel Bierlaire12 Fonctions une variable f (x)>0f (x)0
  • Page 13
  • Conditions d'optimalitMichel Bierlaire13 Fonctions une variable Test de premier ordre : Condition suffisante doptimalit dun point critique. Inconvnient : il faut de linformation sur f dautres points que le point critique.
  • Page 14
  • Conditions d'optimalitMichel Bierlaire14 Fonctions une variable Test de second ordre : Si la fonction f possde une drive seconde continue dans un voisinage dun point critique x*, alors f ''(x*) < 0 est une condition suffisante pour que x* soit un maximum local, et f ''(x*) > 0 est une condition suffisante pour que x* soit un minimum local.
  • Page 15
  • Conditions d'optimalitMichel Bierlaire15 Fonctions une variable Soit f(x) = x 3 + 6 x 2 + 9 x + 8 f '(x) = 3 x 2 + 12 x + 9 = 3(x+3)(x+1) Points critiques : x 1 = -3 et x 2 = -1 f(x) = 6 x + 12 f(-3) = -6 < 0 x 1 maximum local f(-1) = 6 > 0 x 2 minimum local
  • Page 16
  • Conditions d'optimalitMichel Bierlaire16 Fonctions multivariables Rappels : Soit f : IR n IR : (x 1,,x n ) T f(x 1,,x n ) Si la limite existe, elle est appele la i ime drive partielle de f. e i tant le i ime vecteur unit, compos de zros, sauf la i ime composante qui est 1. Elle est note ou
  • Page 17
  • Conditions d'optimalitMichel Bierlaire17 Fonctions multivariables Rappels: Si toutes les drives partielles existent, le gradient de f en x est le vecteur colonne
  • Page 18
  • Conditions d'optimalitMichel Bierlaire18 Fonctions multivariables Rappels : Soit f: IR n IR m. Si chaque composante f i, i=1,m, est (continment) diffrentiable, alors f est dite (continment) diffrentiable. La matrice n x m dont la colonne i est le gradient f i (x) est la matrice gradient de f en x. La transpose de la matrice gradient est appele matrice jacobienne ou Jacobien de f en x.
  • Page 19
  • Conditions d'optimalitMichel Bierlaire19 Fonctions multivariables Rappels : Soit x et d IR n. La drive directionnelle de f en x dans la direction d est condition que la limite existe. Si toutes les drives directionnelles de f en x existent, alors f est (Gateaux) diffrentiable en x.
  • Page 20
  • Conditions d'optimalitMichel Bierlaire20 Fonctions multivariables Rappels : Si f est diffrentiable sur un ensemble ouvert S, et le gradient f(x) est une fonction continue de x, alors f est continment diffrentiable sur S. Si toutes les drives partielles de f sont continment diffrentiables, alors 2 f/ x i x j (x) est la i ime drive partielle de f/ x j en x.
  • Page 21
  • Conditions d'optimalitMichel Bierlaire21 Fonctions multivariables R appels : La matrice symtrique 2 f(x), dont la cellule (i,j) est 2 f/ x i x j (x) est appele la matrice des drives secondes, ou matrice hessienne, ou encore le Hessien de f en x. Soient f:IR k IR m et g:IR m IR n deux fonctions continment diffrentiables, et h leur compose, c--d h(x)=g(f(x)).Alors, h(x) = f(x) (g(f(x)). Notamment, (f(Ax)) = A T f(Ax), o A est une matrice.
  • Page 22
  • Conditions d'optimalitMichel Bierlaire22 Fonctions multivariables Rappels : Soit f:IR n IR deux fois continment diffrentiable sur une sphre ouverte S centre en x. Pour tout d tel que x+d S, il existe 0 1 tel que f(x+d)=f(x) + d T f(x) + d T 2 f(x+ d) d. Pour tout d tel que x+d S, f(x+d) = f(x) + d T f(x) + d T 2 f(x) d +o(d 2 )
  • Page 23
  • Conditions d'optimalitMichel Bierlaire23 Fonctions multivariables Rappels : notation o(.) Soit p un entier positif Soit h: IR n IR m Alors ssi pour toute suite {x k }, sans lment nul, et convergeant vers 0.
  • Page 24
  • Conditions d'optimalitMichel Bierlaire24 Fonctions multivariables Conditions ncessaires doptimalit Soit x* un minimum local de f: IR n IR. Si f est continment diffrentiable sur un ouvert S contenant x*, alors f(x*)=0. Si, de plus, f est deux fois continment diffrentiable sur S, alors 2 f(x*) est semi dfinie positive d T 2 f(x*) d 0 pour tout d IR n
  • Page 25
  • Conditions d'optimalitMichel Bierlaire25 Fonctions multivariables Conditions suffisantes doptimalit Soit f: IR n IR une fonction deux fois continment diffrentiable sur un ouvert S. Si x* S satisfait les conditions f(x*)=0 et 2 f(x*) est dfinie positive d T 2 f(x*) d 0 pour tout d IR n, d 0 Alors x* est un minimum local strict de f