[PDF] Optimisation 7. feb. 2019 5 Optimisation

View - Download Optimisation

Previous PDF

Next PDF

Optimisation

thierry.chonavel@imt-atlantique.fr

IMT-Atlantique - Rennes I

Automne 2018

7 fevrier 2019 1 / 37

Sommaire

1Rappels

Rappels de topologie et de calcul dierentiel

Convexite

2Optimisation

Generalites

Optimalite

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

Generalites

Conditions d'optimalite

5Optimisation sous contraintes d'inegalite

Generalites

Conditions d'optimalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 2 / 37

Introduction

Rappels de calcul dierentiel.

Convexite et optimisation.

Optimisation sous contraintes d'egalite

!multiplicateurs de Lagrange.Optimisation sous contraintes d'inegalite !conditions de Khun et Tucker.Exemples.

7 fevrier 2019 3 / 37

Objectifs du cours

Preparer a l'examen de master SISEA.

Conna^tre des notions de base de l'optimisation continue I dierentiation, convexite, points reguliers

Imultiplicateurs de Lagrange

Iequations de Khun-Tucker.Savoir resoudre rapidement des problemes d'optimisation souscontraintes d'egalite et d'inegalite du type de ceux poses a l'examen de

master.7 fevrier 2019 4 / 37

Sommaire

1Rappels

Rappels de topologie et de calcul dierentiel

Convexite

2Optimisation

Generalites

Optimalite

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

Generalites

Conditions d'optimalite

5Optimisation sous contraintes d'inegalite

Generalites

Conditions d'optimalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 5 / 37

Sommaire

1Rappels

Rappels de topologie et de calcul dierentiel

Convexite

2Optimisation

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

5Optimisation sous contraintes d'inegalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 6 / 37

Rappels de topologie

NormeLp:x2Rn,kxkp=Pn

i=1xp i

1=pEnsemble ouvert, point interieur, voisinage d'un point, adherence d'un ensemble,

ensemble fermeEnsemble compact Theoreme (de Weierstrass)Soit une fonction continuef:KRn!RavecKcompact. Alors, il existexmetxMde Ktels que minx2Kf(x) =f(xm) et maxx2Kf(x) =f(xM).Corrolaire Sifest continue surRnetlimkxk!1f(x) = +1, alorsf(R) = [m;1[ et il existexmde Rntel quem= minx2Rf(x) =f(xm).7 fevrier 2019 7 / 37

Rappels de calcul dierentiel

Pourf:URn!Rm, on dit quefest derivable enx2Usi

9f0(x)2Rmn;8h;x+h2U;f(x+h) =f(x) +f0(x)h+khk"(h)

(1) avec lim h!0"(h) = 0.On noterf(x) = [f0(x)]T.rf(x) est appele le jacobien dex: [rf(x)]ij=@fj(x)@xi(2)Pourm= 1,rf(x) = [@f(x)@x1;:::;@f(x)@xn]T7 fevrier 2019 8 / 37

Matrice hessienne

Developpement de Taylor au second ordre :f:Rn!R

f(x+h) =f(x) +rf(x)Th+12 hTr2f(x)h+khk2(h) (3) ou lim h!0(h) = 0 etr2f(x)2Rnnavec [r2f(x)]ij=@2f(x)@xi@xj:(4)7 fevrier 2019 9 / 37

Convexite

Ensemble convexe :ARnest convexe si

8x;y2A;[x;y]A;c:a:d:82[0;1]; x+ (1)y2A:(5)Fonction convexe : la fonctionf:ARn!RavecAensemble

convexe, est convexe si

8x;y2A;82[0;1];f(x+(1)y)f(x)+(1)f(y):(6)sif2 C1(A),fest convexe ssi

8x;y2A;f(y)f(x) +rf(x)T(yx) (7)sif2 C2(A),fest convexe ssi

8x;y2A;(yx)Tr2f(x)(yx)0 (8)7 fevrier 2019 10 / 37

Sommaire

1Rappels

2Optimisation

Generalites

Optimalite

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

5Optimisation sous contraintes d'inegalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 11 / 37

Optimisation : generalites

Notions de minimum local, global, strict.

Direction admissible. Soitf:ARn!Retx2A. On dit quedest une direction admissible enxsi

9 >0;82[0;];x+d2A(9)Direction de descente : une direction admissibledest une direction de

descente enxsi

9 >0;82[0;];f(x+d)f(x):(10)7 fevrier 2019 12 / 37

Conditions d'optimalite

Conditions necessaires du premier ordre

Si f2 C1(A) admet un

minimum local enx, pour tout vecteurddirection admissible enx,

[rf(x)]Td0 (inegalite d'Euler).En particulier, six2Int(A),rf(x) = 0.Conditions necessaires du second ordreSi f2 C2(A) admet un

minimum local enx, pour tout vecteurddirection admissible enx, soit [rf(x)]Td0; soit [rf(x)]Td= 0 etdTr2f(x)d0(11)Conditions susantes du second ordreSi x2Int(A), avecrf(x) = 0 etr2f(x)>0, alorsxest un minimum local strict def.7 fevrier 2019 13 / 37

Minimisation : cas convexe

Sifest convexe, alors1Tout minimum local est un minimum global

2xest un minimum global si et seulement si

8y2A;[rf(x)]T(yx)0:(12)7 fevrier 2019 14 / 37

Sommaire

1Rappels

2Optimisation

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

5Optimisation sous contraintes d'inegalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 15 / 37

Criteres quadratiques et elliptiques

fonctions quadratiques : f(x) =xTAx+xTb+c. Minimisation et convexiteExtension : fonctions elliptiques I denition :9 >0;(rf(y) rf(x))T(yx)kyxk2 I proprietes : sifest elliptique, elle est strictement convexe et f(y)f(x) rf(x)T(yx) +2 kyxk2: I f2C2est elliptique si et seulement sidTr2f(x)dkdk2.7 fevrier 2019 16 / 37

Methode de relaxation

La plupart des methodes de minimisation classiques procedent en cherchant a minimiserf(x) dans des directions successives : x

k+1=xk+kdkSi on optimise cycliquement la fonction vis a vis des axes decoordonnees (dk=ek) on obtient la methode dite de relaxation et on

note f(xk;l) = minf(xk;l1+el) ouxk;l= [xk+11;:::;xk+1 l;xkl+1;:::;xkn]T.Convergence de la methode de relaxation La methode de relaxation converge pour les fonctions elliptiques

Importance de l'hypothese de derivabilite

7 fevrier 2019 17 / 37

Algorithme du gradient (pas optimal)

x k+1=xk+kdk. Idee : choisir la direction de decroissance la plus rapide def(x)Algorithme du gradient!dk/ rf(xk)algorithme du gradient a pas optimal : x k+1=xkkrf(xk)

aveck= argminf(xkkrf(xk)).Convergence de la methode du gradient a pas optimalLa methode du gradient a pas optimal converge pour les fonctions elliptiquesExemple : cas des fonctions quadratiques

7 fevrier 2019 18 / 37

Algorithme du gradient (pas constant et pas variable) gradient a pas xe et variable : x k+1=xkrf(xk) etxk+1=xkkrkf(xk):Convergence des methodes du gradient : cas elliptique Sifest elliptique de coecientet qu'il existeM>0 tel que k rf(y) rf(x)kMkyxk, et si 0Methodes de directions conjuguees min xf(x) =12 xTAxbTx,A2Rnn,A>0Directions conjugueesd0;:::;dn1avecdTiAdj= 0 pouri6=j. d

0;:::;dn1forme une base deRnx

solution)x=Pn1 k=0dTkbd

TkAdkd

kTheoreme

Pourx02Rnetxk+1=xkdTk[Axkb]d

TkAdkd

k, on axn=x7 fevrier 2019 20 / 37

Algorithme du gradient conjugue

Initialisation :x02Rn,d0=g0=bAx0,Iterations :

x k+1=xk+kdk;ouk= argminf(xk+dk) : k=gTkdkd

TkAdketgk=Axkb(=rf(xk))

d k+1=gk+1+kdk k=gTk+1Adkd

TkAdk(=gTk+1(gk+1gk)g

Tkgk=gTk+1gk+1g

Tkgk)(13)

7 fevrier 2019 21 / 37

Extension non quadratique du gradient conjugue

On prendgk=rf(xk)On calculeken minimisant directementf(xk+dk)On prenddk+1=gk+1+kdkOn peut choisir I k=gTk+1gk+1g

Tkgk(Fletcher-Reeves).

I k=(gk+1gk)Tgk+1g

Tkgk(Polak-Ribiere).

7 fevrier 2019 21 / 37

Algorithmes de Newton

x

k+1=xkk[r2f(xk)]1rf(xk)Choix dek: optimum ou dichotomie sur [0;1]Probleme lorsqu'on n'a pasr2f(xk)>0!perturbationr2f(xk)+"IPerturbations de rang faible.

7 fevrier 2019 22 / 37

Sommaire

1Rappels

2Optimisation

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

Generalites

Conditions d'optimalite

5Optimisation sous contraintes d'inegalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 23 / 37

Optimisation sous contraintes d'egalite

Probleme :

minxf(x) h(x) = 0(14) avech= [h1;:::;hm]T:Rn!Rm(mEspace tangent

Denition

L'espace tangent aVen un pointxregulier, noteT(x), est l'espace engendre par les vecteurs tangents aVenx.Theoreme

Sixest un point regulier,

T(x) =fy2Rn; [rh(x)]Ty= 0g(15)7 fevrier 2019 25 / 37

Espace tangent (preuve)

CN : Siy2 T(x), alors [rh(x)]Ty= 0CS : theoreme des fonctions implicites

Theoreme des fonctions implicites

(i)g2 C1:ORnmRm!Rm, (x1;x2)7!g(x1;x2) (ii)g(a1;a2) =b, etrx2g(a1;a2)2Rmminversible Alors, il existe un voisinage ouvertO1O2de (a1;a2) eth:Rnm!Rm t.q. f(x1;x2)2O1O2;g(x1;x2) =bg=f(x1;h(x1));x12O1g:(16) etrx1h(a1) =rx1g(a1;a2)[rx2g(a1;a2)]1:7 fevrier 2019 26 / 37

Conditions d'optimalite (contraintes d'egalite)

Theoreme (CN1)

Sixest un point regulier deV. Sifest minimum enx,

92Rm;rxf(x) +rxh(x)= 0:(17): vecteur de multiplicateurs de LagrangeL(x;) =f(x) +Th(x) : lagrangien du probleme d'optimisation7 fevrier 2019 27 / 37

Conditions d'optimalite (contraintes d'egalite)

Theoreme (CN2)

Sixest un point regulier deV. Sifest minimum enx, alors il existe

2Rmtel que

r xL(x;) =rxf(x) +rh(x)= 0 (I) r

2xL(x;) estsemi-d eniep ositivesur T(x) (II)(18)Theoreme (CS2)

Sixest un point regulier deV. Si il existe2Rmtel que (I) soit verieeetr2xL(x;) estd eniep ositivesur T(x), alorsfa un minimum local strict

enx.7 fevrier 2019 28 / 37

Sommaire

1Rappels

2Optimisation

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

5Optimisation sous contraintes d'inegalite

Generalites

Conditions d'optimalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 29 / 37

Optimisation sous contraintes d'inegalite

minxf(x)

h(x)0(19)U=fx2Rn;hi(x)0;i= 1;:::;mgOn dit que la contraintehi(x)0 est active enxsihi(x) = 0.Notation :

I

I(x) =fi;hi(x) = 0;i= 1;:::;mg,

IV(x) =fy2Rn;hi(y) = 0;i2 I(x)g.On noteraT(x) l'espace tangent aV(x)On dit quexest un point regulier sifrhi(x);i2 I(x)gforme une

famille libre.

7 fevrier 2019 30 / 37

Conditions d'optimalite (contraintes d'inegalite)

Theoreme (CN1 - conditions de Khun et Tucker)

Sixest un point regulier deVet sifest minimum enx, alors il existe

2Rm+tel que

r xf(x) +rh(x)= 0 ihi(x) = 0;i= 1;:::;m:(20)Dans le cas convexe, ces conditions sont necessaires et susantes.

7 fevrier 2019 31 / 37

Conditions d'optimalite (contraintes d'inegalite)

Theoreme (CN2)

Sixest un point regulier deV. Sifest minimum enx, alors il existe

2Rm+tel que

r xL(x;) =rxf(x) +rh(x)= 0 (I)

Th(x) = 0 (II)

r

2xL(x;) estsemi-d eniep ositivesur T(x) (III)Theoreme (CS2)

Sixest un point regulier deVet si il existe2Rm+tel que (I) et (II) soient veriees etr2xL(x;) estd eniep ositivesur T(x), alorsfa un minimum local strict enx.7 fevrier 2019 32 / 37

Sommaire

1Rappels

2Optimisation

3Algorithmes d'optimisation sans contraintes

4Optimisation sous contraintes d'egalite

5Optimisation sous contraintes d'inegalite

6Algorithmes d'optimisation avec contraintes

7 fevrier 2019 33 / 37

Dualite

minxf(x)

h(x) = 0(21)Solution (x;) : on arL(x;) = 0 etr2L(x;)0Sir2L(x;)>0 surT(x),xest solution de minxL(x;)Pour2 V, on notex= argminxL(x;)Fonction duale :() = minxL(x;)7 fevrier 2019 34 / 37

Dualite

Lemme r () =h(x),r2() =[rxh(x)]Tr2xL(x;)rxh(x)est concave au voisinage dexTheoreme

Si (x;) est solution avecxregulier etr2xL(x;)>0,

max () =() =f(x) etx=x.Doncf(x) = maxminxL(x;)!algorithme d'Uzawa : x k+1=xkkrxL(x;k) k+1=k+kh(xk)(22)7 fevrier 2019 35 / 37

Lagrangien augmente : contraintes d'egalite

(I)minxf(x) h(x) = 0,(II)( min xf(x) +12 ckh(x)k2 h(x) = 0(23)

II() = minx

L

I(x;) +12

ckh(x)k2 =LI(x;) +12 ckh(x)k2.r II() =ch(x) et sir2II()<0 surVon peut actualiserpar !+ch(x). D'ou l'algorithme x k+1= argminxLI(x;) +12 kh(x)k2 k+1=k+ch(xk)(24)

7 fevrier 2019 36 / 37

Lagrangien augmente : contrainte d'inegalite

(I)minxf(x) h(x)0,(II)( min xf(x) +12 ckh(x) +vk2 h(x) +v= 0;v0(25)

II() = minx;v0(f(x) +T(h(x) +v) +12

ckh(x) +vk2)v= max[0;h(x)=c] et

II() = minx(f(x) +12cP

m k=1(max[0;k+chk(x)])22kAlgorithme : x k+1= argminx(f(x) +12cP m k=1(max[0;k+chk(x)])22k k+1=k+c(h(xk) + max[0;h(xk+1)k=c])(26)

7 fevrier 2019 37 / 37

quotesdbs_dbs28.pdfusesText_34

[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