[PDF] Optimisation sans contrainte : conditions doptimalité

View - Download Optimisation sans contrainte : conditions doptimalité

Previous PDF

Next PDF

Optimisation sans contrainte : conditions

d'optimalité

Michel Bierlaire

michel.bierlaire@epfl.ch

EPFL - Laboratoire Transport et Mobilit

´e - ENAC

Optimisation sans contrainte : conditions d'optimalit´e - p. 1/20 Optimisation sans contrainte : conditions d'optimalité

•Problème :

minx?Rnf(x)

•Soitx?un minimum local

•Comment caractériserx??

Optimisation sans contrainte : conditions d'optimalit´e - p. 2/20 Conditions nécessairesConditions nécessaires d'optimalité

Soitx?un minimum local d'une

fonctionf:Rn-→R. Sifest différentiable dans un voisinage ouvertVdex?, alors, ?f(x?) = 0. Il s'agit de lacondition nécessaire du premier ordre. Si, de plus,fest deux fois différentiable surV, alors

2f(x?)est semi définie positive.

etfest localement convexe enx?. Il s'agit de lacondition nécessaire du second ordre(p. 127). Optimisation sans contrainte : conditions d'optimalit´e - p. 3/20

Conditions nécessaires

f(x1,x2) = 100(x2-x21)2+ (1-x1)2 x1x2 Optimisation sans contrainte : conditions d'optimalit´e - p. 4/20

Conditions nécessaires

x ?= (1,1)minimum local ?f(x1,x2) =?

400x31-400x1x2+ 2x1-2

200x2-200x21?

et?f(1,1) = 0.

2f(x1,x2) =?

1200x21-400x2+ 2-400x1

-400x1200? et

2f(1,1) =?

802-400

-400 200? Optimisation sans contrainte : conditions d'optimalit´e - p. 5/20

Conditions nécessaires

•Valeurs propres positives : 0.39936 et 1001.6

•Mauvais conditionnement : 2508

Optimisation sans contrainte : conditions d'optimalit´e - p. 6/20

Conditions nécessaires

f(x1,x2) =-x41-x42 x1x 2 Optimisation sans contrainte : conditions d'optimalit´e - p. 7/20

Conditions nécessaires

x ?= (0,0)vérifie les cond. néc. d'optimalité ?f(x1,x2) =? -4x31 -4x32? et?f(0,0) = 0

2f(x1,x2) =?

-12x210

0-12x22?

et?2f(0,0)est semi défini positif. (0,0)n'est pas un minimum local Optimisation sans contrainte : conditions d'optimalit´e - p. 8/20

Conditions nécessaires

f(x1,x2) = 50x21-x32 x1x2 Optimisation sans contrainte : conditions d'optimalit´e - p. 9/20

Conditions nécessaires

x ?= (0,0)vérifie les cond. néc. d'optimalité ?f(x1,x2) =? 100x1
-3x22? et?f(0,0) = 0

2f(x1,x2) =?

100 0

0-6x2?

et?2f(0,0)est semi déf. pos. Optimisation sans contrainte : conditions d'optimalit´e - p. 10/20

Conditions nécessaires

•Considérons la directiond= (0,1)Ten(0,0).

•Avançons d'un pasα. On obtient

0 0? 0 1? 0 et f? 0 =-α3<0 =f? 0 0? (0,0)n'est pas un minimum local Optimisation sans contrainte : conditions d'optimalit´e - p. 11/20

Conditions nécessaires

•Considérons la directiond= (0,-1)Ten(0,0).

•Avançons d'un pasα. On obtient

0 0? 0 -1? 0 et f? 0 =α3>0 =f? 0 0? (0,0)est un point de selle Optimisation sans contrainte : conditions d'optimalit´e - p. 12/20

Conditions nécessairesPoint critique

Soitf:Rn-→Rune fonction différentiable. Tout vecteurx?Rntel que

?f(x) = 0est appelépoint critiqueoupoint stationnairedef•En pratique les algorithmes cherchent les points critiques

•Ils seront conçus pour se diriger vers les minima, et pas versles autres points critiques Optimisation sans contrainte : conditions d'optimalit´e - p. 13/20 Conditions suffisantesConditions suffisantes d'optimalité

Soit une fonctionf:Rn-→R

deux fois différentiable dans un sous-ensemble ouvertVdeRn, et soitx??V qui vérifie les conditions ?f(x?) = 0. et

2f(x?)est définie positive.

Alors,x?est un minimum local strict def.(p. 132)

Optimisation sans contrainte : conditions d'optimalit´e - p. 14/20

Conditions suffisantes

f(x1,x2) =1

2x21+x1cosx2,

-1.5-1-0.500.511.5x1-6 -4-20246x 2-1 0123
Optimisation sans contrainte : conditions d'optimalit´e - p. 15/20

Conditions suffisantes

f(x1,x2) =1

2x21+x1cosx2,

-1.5 -1 -0.5 0 0.5 1 1.5 -6-4-20246 x -2x -1x 0x 1x 2 ¯x

0¯x

1 ¯x -1 ¯x -2 x1x 2 Utilisons les cond. d'opt. pour identifier les minima locaux Optimisation sans contrainte : conditions d'optimalit´e - p. 16/20

Conditions suffisantes

?f(x1,x2) =? x

1+ cosx2

-x1sinx2?

Le gradient s'annule pour

•x?k= ((-1)k+1,kπ)T,k?Z,

•¯xk= (0,π

2+kπ)T,k?Z.

Optimisation sans contrainte : conditions d'optimalit´e - p. 17/20

Conditions suffisantes

2f(x1,x2) =?

1-sinx2

-sinx2-x1cosx2?

2f(x?k) =?

1 0 0 1?

2f(¯xk) =?

1 (-1)k+1

(-1)k+10? Optimisation sans contrainte : conditions d'optimalit´e - p. 18/20

Conditions suffisantes

•x?kvérifie les conditions suffisantes d'optimalité pour toutk •¯xkne vérifie les conditions nécessaires d'optimalité pour aucun k. Optimisation sans contrainte : conditions d'optimalit´e - p. 19/20 Conditions suffisantesConditions suffisantes d'optimalité globale

Soit une fonction

f:Rn-→Rdeux fois différentiable dansRn, et soitx??Rnun minimum local def. Sifest une fonction convexe, alorsx?est un minimum global def. Si de plusfest strictement convexe,x?est l'unique minimum global def.(p. 134) Optimisation sans contrainte : conditions d'optimalit´e - p. 20/20quotesdbs_dbs23.pdfusesText_29

[PDF] Circulaire du 26 janvier 2017 concernant les budgets primitifs 2017

[PDF] Conditions tarifaires de location de Véhicules RENT A CAR au 1er

[PDF] Exemple conducteur emission

[PDF] conducteurs en equilibre electrostatique - usthb

[PDF] Travaux dirigés : Conductance et Conductivité - Lycée Gustave

[PDF] Ch3 - EXERCICES Courant électrique dans les solutions aqueuses

[PDF] TRANSFERTS DE CHALEUR - Exercices de références - Doc 'INSA

[PDF] Vapeur - ThermExcel

[PDF] La Conductivité thermique de quelques matériau de construction

[PDF] Propriétés thermiques des matériaux et références métrologiques

[PDF] fimo / fco - Pardessuslahaie

[PDF] Conduire en France avec un permis étranger et son échange I

[PDF] conduite ? tenir devant une femme ayant une cytologie - Aly Abbara

[PDF] Scorpion - Centre AntiPoison et de Pharmacovigilance du Maroc

[PDF] PDF 241 ko Gestion de projet - FOAD