TD 1 Optimisation non linéaire : Généralités PDF

Optimisation non-linéaire

Exercice I.4 Calculer le gradient et la matrice Hessienne des fonctions suivantes : f(xy) = x3 + 3xey

RO04/TI07 - Optimisation non-linéaire

Exercices. Documents section ? suivant ?. 7. ??. Formulation générale des problèmes d'optimisation non linéaire. La forme générale d'un problème

Optimisation non linéaire : correction des TD

17 jan. 2008 Dans cet exercice nous chercherons à optimiser la fonction sans contrainte puis nous vérifierons a posteriori que l'optimum se trouve dans le ...

TD 1 Optimisation non linéaire : Généralités

Optimisation non linéaire : Généralités. Exercice 1 :Étude des fonctions quadratiques. Soient Q une matrice de Rn×n b un vecteur de Rn et f : Rn ? R la

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

systèmes non linéaires optimisation). Pour chaque semaine

RO04/TI07 - Optimisation non-linéaire

Exercices. Documents chapitre ? section suivante ?. 5. I.1 Motivations. I.1.1. Formulation générale des problèmes d'optimisation non linéaire .

1 Les conditions de Kuhn-Tucker

Corrigés d'optimisation convexe et quadratique Exercices corrigés . ... cas de la programmation linéaire ces conditions sont réalisée car une fonction.

Optimisation Non Linéaire Travaux Pratiques I Optimisation sans

Optimisation Non Linéaire. Travaux Pratiques I. Mehmet Ersoy. Optimisation sans contraintes : algorithmes. Le but de ce TP est de tester différentes

Exercices sur le cours “Optimisation et programmation dynamique” 1

“Optimisation et programmation dynamique” o`u s et c sont des vecteurs de Rn non nuls. ... 1.3.2 Programmation linéaire et algorithme du simplexe.

Méthodes numériques pour loptimisation non linéaire déterministe.

f(xk). Démonstration. En exercice. d. Théorème 1.1 f est convexe si et seulement si son épigraphe epi(f) =

TD1

Exercice1:Etudedesfonctionsquadratiques

f(x)=1

2xTQx+bTx,x?Rn.

1. ontrerquefestdi ´erentiableausensde r´echetetque

@f @x(x)=12xT(Q+QT)+bT,x?Rn:

2. ontrerquefestdeuxfoisdi ´erentiable.CalculerleHessien@2f(x)

@x2.Quelleest l"expressiondef00(x)(v)(v)? .OnsupposequeQestsym´etrique. ontrerquefestconvexe(resp.strictementcon- d´emonstrations: a)festconvexesietseulementsi f(y) f(x)+@f @x(x)(y-x),8x,y?Rn: b)Si f(y)>f(x)+@f @x(x)(y-x),8x6=y?Rn, alorsfeststrictementconvexe. 1

Exercice2:Approximationdefonctions

Onconsid`ereunefonction :R!R.Onconnaˆtlesvaleurs (x1), , (xm)queprend aux pointsx1, ,xm.Onsouhaitetrouveruneapproximationdelafonction parunpolynˆome hdedegr´end´efinipar h(x)=anxn+an-1xn-1+ +a0,x?R, avecn m. rouverlescoecientsdeh,telsquehconstituelameilleureapproximationde ausensdesmoindrescarr´es. Onappliqueralesr´esultatsauxvaleursx1=1,x2=2,x = , (x)=5x2+2x+1et h(x)=a1x+a0.

Exercice3:Production

premi`eressontp1, ,pn.Leprixdeventeunitaireduproduitfiniestq. valeursx1,:::,xnquimaximisentleprofit.

31x132,puisaucas

1=2,p2=1,q=1eth(x1,x2)=x2

1+x2 2. 2 TD2

Optimisationaveccontrainte:Qualication

Soitlesous-ensembleΩde 2d´efinipar

Ω=f(x;y)2 2:(x 1)2+y2 1=0etx2+(y 1)2 1=0g:

a)graphiquement;

2.Quelestl"ensembledesdirectionsadmissiblessiΩestunsous-ensemblede 3?

Ω=f(x;y)2 2:(x 1)2+y2 10etx2+(y 1)2 10g:

Exercice2

Soientlesdeuxprobl`emesd"optimisation

(P1):minx2

1( x1)et(P2):minx2

2( x1);avec

1=f(x1;x2)2 2:x1+x2 10; x1 2x2+10; x10; x20g;

2=f(x1;x2)2 2:(x1+x2 1)(x1+2x2 1)0; x10; x20g:

G ^x=fv2 2:@ i @x(ˆx)v0;i2A(ˆx)g associ´es`acessolutions. .Interpr´eterlesr´esultats. 1

Exercice3

Soitm2 unparam`etre.Ond´efinitlafonctionparam`etr´ee{m: 3! par m(x)=mx3 1+ 2x2 1+x2 2+ x2

3 2x2;x=(x1;x2;x3)T2 3:

SoitΩunsous-ensemblede 3et(P

)leprobl`emed"optimisation: (P ):minx2 {m(x):

1.R´esoudre(P

)pourΩ=fx2 3:x2>0g

2.R´esoudre(P

)pourΩ=fx2 3:x2>1g .Discuterdesprobl`emessoulev´esparlacontrainteΩ=fx2 3:x22g 2 BE1

Optimisationsanscontrainte:Algorithmedu

gradient grandepente f(x)=1

2xTQx-bTx,x?Rn,

(P):minx?Rnf(x): x k+1=xk-k?f(xk),xk?Rn,k=1,2,:::, o`ukminimisef(xk-k?f(xk)).

1. ontrerque

k= Tk k

TkQ kavec k=?f(xk)=Qxk-b:

2.Ond´esigneparx lasolutionde(P).SoitE(x)=1

2(x-x )TQ(x-x ). ontrerque

E(xk)-E(xk+1)

E(xk)=( Tk k)2( TkQ k)( TkQ-1 k):

.Ondonnel"in´egalit´edeKantorovich ( Tk k)2 ( TkQ k)( TkQ-1 k) 4aA(a+A)2, delaquestion(2)que A+a? 2

E(xk):

End´eduirequel"algorithmeconverge.

1 Remarque:Poursimplifierlescalculs,onsupposeraqueb=0.Ils"ensuitquex =0. fonction

Aulieuder´esoudreleprobl`eme

(P):minx?Rnf(x), plusgrandepenteauprobl`eme (P?):minx?Rn??f(x)?2:

Onsupposequef(x)=1

3Application2:Methodedepenalite

Onconsid`ereleprobl`eme

(P?):minh(x)=0f(x), r´esoudreleprobl`emesanscontrainte (P):minx?Rn? f(x)+1

2?h(x)?2?

o`uestgrand.Onsupposequef(x)=1

2xTQx,x?RnetquelamatriceQestdiagonale,

aveccT=(1,0, ,0). 2 TD ro lemesaveccontraintes´egalit´e

Exercice1

R´esoudreleprobl`eme

(P):ming(x1;x?)=0f(x1,x2),o`u( f(x1,x2)=2x1+ x2 1 (x1,x2)=x2 1+3 2x2

2 6,(x1,x2)2R2:

Exercice2

rouverleparall´el´epip`ederectanglededimensionx,y, devolumemaximaletdesurface donn´eec.

Exercice3

i=1pi=1.L"entropiedeXest d´efinieparH(X)= Pn i=1pilog2(pi). lavaleurmoyennedeXsoit´egale`am. 1 TD4 ro lemesaveccontraintesin´egalit´e

Exercice1:Programmationquadratique

:f(x)=1

2xTQx bTx

h(x)=aTx c,x2Rn:

Exercice2

R´esoudreleprobl`eme

(P):min h

1(x1,x2)0

2(x1,x2)0(x1+x2),avec(

1(x1,x2)=x2 x1

2(x1,x2)=x2

1+x2

2 1,(x1,x2)2R2:

Exercice3

deuxr´eelsavecc>1 h

1(x)=aTx,8x2Rn,

2(x)=1

2xTQx c,8x2Rn:

R´esoudreleprobl`eme

(P):minx?Ω(aTx b),avecΩ=fx2Rn:h1(x)0eth2(x)0g:

Indication:remarquerqueh1( a) 0eth2( a) 0.

1 TD5

Dualit´e

Exercice1

(P):mina

1x1+a2x2 c0(x2

1+x2 2):

Exercice2:Programmationquadratique

(P):minh(x)0f(x),avec8 :f(x)=1

2xTQx-bTx

h(x)=aTx-c,x?Rn:

Exercice3

Soitunr´eelc 0.Ond´efinitlesfonctionsf,h:Rn→Rpar f(x)=nX i=1x 4 i h(x)= nX i=1x i! -c,x=(x1,:::,xn)T?Rn, etonconsid`ereleprobl`eme (P):minx2

1. ontrerquelafonctionfestconvexesurRn.

=n41 -44

45 =- n44 :

1 BE2

Optimisationaveccontrainte:Algorithmedu

gradientprojet´e

1Presentationduprobleme

f(x)=1

2xTQx-bTx,x?Rn,

Onconsid`ereleprobl`eme

(P):min aT a T

2Solutionanalytique

deRn×2derang2etcvecteurdeR2.

3Algorithmedugradientprojete

cepointsurlesfronti`eresdeΩ. x k+1=PΩ(xk-tk?f(xk)) 1

1.CalculdelaprojectionsurΩ

ladistanceentrexettoutvecteurdeΩ: P (P?)miny?Ω?x-y?

2.Autreversiondel"algorithme

fdansladirectionprojet´eeobtenue.

Danscecas,lepointxk+1v´erifie:

x k+1=xk+tk(PΩ(xk-?f(xk))-xk) 2quotesdbs_dbs18.pdfusesText_24

[PDF] TD 1 Optimisation non linéaire : Généralités

Exercice1:Etudedesfonctionsquadratiques

2xTQx+bTx,x?Rn.

1. ontrerquefestdi ´erentiableausensde r´echetetque

2. ontrerquefestdeuxfoisdi ´erentiable.CalculerleHessien@2f(x)

Exercice2:Approximationdefonctions

Exercice3:Production

31x132,puisaucas

1=2,p2=1,q=1eth(x1,x2)=x2

Optimisationaveccontrainte:Qualication

Soitlesous-ensembleΩde 2d´efinipar

Ω=f(x;y)2 2:(x 1)2+y2 1=0etx2+(y 1)2 1=0g:

2.Quelestl"ensembledesdirectionsadmissiblessiΩestunsous-ensemblede 3?

Ω=f(x;y)2 2:(x 1)2+y2 10etx2+(y 1)2 10g:

Exercice2

Soientlesdeuxprobl`emesd"optimisation

1( x1)et(P2):minx2

2( x1);avec

1=f(x1;x2)2 2:x1+x2 10; x1 2x2+10; x10; x20g;

2=f(x1;x2)2 2:(x1+x2 1)(x1+2x2 1)0; x10; x20g:

Exercice3

3 2x2;x=(x1;x2;x3)T2 3:

SoitΩunsous-ensemblede 3et(P

1.R´esoudre(P

2.R´esoudre(P

Optimisationsanscontrainte:Algorithmedu

2xTQx-bTx,x?Rn,

1. ontrerque

TkQ kavec k=?f(xk)=Qxk-b:

2.Ond´esigneparx lasolutionde(P).SoitE(x)=1

2(x-x )TQ(x-x ). ontrerque

E(xk)-E(xk+1)

E(xk)=( Tk k)2( TkQ k)( TkQ-1 k):

E(xk):

End´eduirequel"algorithmeconverge.

Aulieuder´esoudreleprobl`eme

Onsupposequef(x)=1

3Application2:Methodedepenalite

Onconsid`ereleprobl`eme

2?h(x)?2?

2xTQx,x?RnetquelamatriceQestdiagonale,

Exercice1

R´esoudreleprobl`eme

2 6,(x1,x2)2R2:

Exercice2

Exercice3

Exercice1:Programmationquadratique

2xTQx bTx

Exercice2

R´esoudreleprobl`eme

1(x1,x2)0

2(x1,x2)0(x1+x2),avec(

1(x1,x2)=x2 x1

2(x1,x2)=x2

2 1,(x1,x2)2R2:

Exercice3

1(x)=aTx,8x2Rn,

2(x)=1

2xTQx c,8x2Rn:

R´esoudreleprobl`eme

Indication:remarquerqueh1( a) 0eth2( a) 0.

Dualit´e

Exercice1

1x1+a2x2 c0(x2

Exercice2:Programmationquadratique

2xTQx-bTx

Exercice3

1. ontrerquelafonctionfestconvexesurRn.

45 =- n44 :

Optimisationaveccontrainte:Algorithmedu

1Presentationduprobleme

2xTQx-bTx,x?Rn,

Onconsid`ereleprobl`eme

2Solutionanalytique

3Algorithmedugradientprojete

1.CalculdelaprojectionsurΩ

2.Autreversiondel"algorithme

Danscecas,lepointxk+1v´erifie: