[PDF] Exercices sur le cours “Optimisation et programmation dynamique” 1

View - Download Exercices sur le cours “Optimisation et programmation dynamique” 1

Previous PDF

Next PDF

Exercices sur le cours

\Optimisation et programmation dynamique"

2020-2021

Master mention Mathematiques appliquees 1ere annee

Universite Paris Dauphine

1 Optimisation

1.1 Existence et unicite d'un minimum, convexite

Exercice 1(Existence d'une solution).SoitOun ouvert borne deRdetf:O !Rune fonction continue. 1. On supp osequ efest prolongeable par continuite sur l'adherenceOdeOet qu'il existe x

02 Otel que

infx2@Of(x)> f(x0):

Montrer quefa un minimum surO.

2.

M ^emequestion si

limx2O; x!@Of(x) = +1: Exercice 2(Distance entre deux ensembles).SoientAetBdeux sous-ensembles fermes et non vides deRd. 1.

Mon trerque si Aest compact, alors le probleme

min a2A;b2Bkabk admet (au moins) une solution. 2. Mon trerpar un con tre-exempleque le r esultatest faux en g enerals ion ne supp osepas queAouBest compact, m^eme siAetBsont convexes.

Exercice 3(convexite).

1. Soit KRnun ensemble convexe etf:K!Rune fonction de classeC1dans un voisinage deKet >0. Montrer que les trois assertions suivantes sont equivalentes : (i)fest-fortement convexe surK, c'est-a-dire que f(tx+ (1t)y)tf(x) + (1t)f(y)2 t(1t)kxyk2;8x;y2K; t2[0;1]: (ii)f(y)f(x) +hrf(x);yxi+2 kyxk2;8x;y2K (iii)hrf(y) rf(x);yxi kyxk2;8x;y2K.

On dit alors quefestconvexe surK.

2. Mon trerque si f:Rd!Restconvexe, alorsfest coercive surRd, c'est-a-dire lim kxk!+1f(x) = +1: 3. Soit Aune matriceddsymetrique denie positive,b2Rdetc2Retf:Rd!R denie par f(x) =hAx;xi+hb;xi+c8x2Rd:

Montrer qu'il existe >0 tel quefestconvexe surRd.

1

1.2 Le theoreme de Kuhn et Tucker

Exercice 4.On considere le probleme

max g(x)0f(x) Montrer que, sixest un maximum du probleme et la contrainte est qualiee enx, alors il existe

0 tel que

rf(x) +rg(x) = 0:

Exercice 5.On considere le probleme de la boite

min x i0 x

1x2x3= 2(x1x2+ 2x2x3+ 2x1x3)

1.

Prop oserune in terpretationdu probl eme.

2. On supp oseque le probl emeadmet une solution. Ecrire le sconditions n ecessairesd'opti- malite et calculer cette solution. 3. (dicile) Mon trerque le probl emeadmet bien une solution

Exercice 6.On considere le probleme

max x3+y33xy+1=0(x+y) Calculer la solution de ce probleme (on admet l'existence d'un maximum).

Exercice 7.On considere le probleme

max 0xi42 x

1+ 2x2+ 2x372(x1+x2)

Calculer la solution de ce probleme.

Exercice 8.On considere le probleme

max 0x

0y(1x)3(3x+y)

1. Mon trerque le p oint(0 ;1) est le seul point veriant les conditions necessaires. 2. Mon trerque le p oint(1 ;0) est le minimum du probleme. Exercice 9.SoitAune matrice symetrique de formatnn. 1.

Mon trerque

m= minkxk=1xTAx est la plus petite valeur propre deA. 2

2.Soien tfvigi=1;:::;kune famille de vecteurs propres deA(ouk < n), deux a deux ortho-

gonaux. Montrer que la quantite min kxk= 1; v

Tix= 0;8i= 1;:::;kx

TAx est une valeur propre deA. Exercice 10.SoitPl'hyperplan deRNd'equationcTx=d(ouc2Rnnf0g,d2R). Calculer la projection orthogonale d'un pointydeRnsurP, c'est-a-dire le minimum du probleme min cTx=d12 kxyk2 Exercice 11.Quelles conditions doivent verier les reelsp,q,rpour que la fonction lineaire (x1;x2;x3;x4)!x1+px2+qx3+rx4atteigne son maximum sous les contraintes 0x1x2 x

3x4au point (0;0;13

;23 Exercice 12.Les problemes suivants ont-ils a priori une unique solution? La (les) calculer. min x+y1 x+ 2y+z0 yzx

2+y2+ 2z2min

y0 yx x+y+ 30x 2+y Exercice 13.Calculer, en fonction du parametreu2R, la solution du probleme min 8< :0xyz x+y+z1(xy+uxz+u2yz) Exercice 14.Determiner les points veriant les conditions necessaires d'optimalite et trouver la solution du probleme si celle-ci existe : max 8< :y0; yx x+y+ 30x 2+y

Exercice 15.SoientMla matrice

M=0 @2 1 1 1 2 1

1 1 21

A etSl'ensemble convexe

S=f(x1;x2;x3)2R3jx1+ 2x2+ 3x31; xi0 pouri= 1;2;3g

Montrer que le probleme

maxX2SXTMX admet une unique solution. La calculer.

Ind. L'inverse deMestM1=14

0 @311 1 31 11 31 A 3

Exercice 16.On cherche a resoudre le probleme

(P) min(x;y)2K(x2)2+y2ouK=f(x;y)2R2j2xy21 etx0g: 1. Mon trerque le probl emeadmet au moins une solution. 2. Mon trerque la con trainteest quali eeen tout p oint. 3. Ecrire les conditions n ecessairesd'optimalit edu probl eme. 4. T rouvertous les p ointssatisfaisan tles conditions n ecessairesd'optimalit e. 5. En d eduirela (ou les) solution(s) du probl eme( P).

1.3 Dualite

Exercice 17.Resoudre par dualite le probleme

min x2+y21 y+z012 (x2)2+y2+z2

Exercice 18.Calculer le probleme dual de

min log(x)y0 y1x+12 y2

Exercice 19.Resoudre par dualite le probleme

min 12 xTAx1cTx ouAest une matrice symetrique denie positive de formatnn, etcun vecteur deRn.

Exercice 20.On s'interesse au probleme

(P) minCxd12 xTAx+bTx ouAest une matricenndenie positive,best un vecteur deRn,Cest une matrice de format lnetdest un vecteur deRl. L'expressionCxdsignie que toute composante deCx est inferieure ou egale a la composante correspondante ded. Montrer que le probleme dual du probleme (P) est le probleme suivant max

2Rl+12

bTA1b12

TCA1CT(bTA1CT+dT)

Exercice 21.On considereai(i= 1;:::;n) des reels strictement positifs, etxtel quePn i=1x2i=a2i>

1, c'est-a-dire quexn'appartient pas a l'ellipsode

E=fu2RnjnX

i=1x

2i=a2i1g

4

Calculer le probleme dualG() du probleme

min u2Ekuxk2

Montrer que le maximum deG() verie

n X i=1a

2ix2i(a2i+)2= 1:

Exercice 22.Resoudre par dualite le probleme

min hs;xi012 kxk2 hc;xi ousetcsont des vecteurs deRnnon nuls.

Exercice 23.On considere le probleme

min

Ax=b12

kxk2 ouAest une matricemnetbun vecteur deRm. 1. Quelle est la signication g eometriquede ce probl eme. 2.

Calculer le probl emedual ( D).

3. A quelle condition le probl emed ualadmet-il une unique solution ? 4. Calculer dans ce cas ce ttesolution en fonction de Aetb. (On admettra que la methode de dualite fonctionne aussi pour des contraintes d'egalite anes)

1.4 Methodes numeriques

1.4.1 Methodes de penalisation

Exercice 24(Methode de penalisation interieure).Soientf:Rd!Retg:Rd!Rdeux fonctions continues surRd, strictement convexes avecgcoercive. On suppose qu'il existe un pointx0tel queg(x0)<0. 1.

Mon trerque le probl emesous con trainte

min x2Kf(x) ouK:=fx2Rd:g(x)0g possede une unique solution x. L'objectif du probleme est d'approcher xpar une methode de penalisation. Pour tout >0, on pose J (x) :=f(x)g(x)8x2Int(K) =fx2Rd:g(x)<0g: 2. Mon trerque Jpossede un unique minimumxdansInt(K). 3. Soit x2Int(K). Veriez queJ(x)J(x)f(x). En deduire que, si ~xest une valeur d'adherence de (x) lorsque!0, alorsf(x)f(~x). 4.

Conclure que ( x) tend vers xlorsque!0.

5

5.On s upposeque fetgsont de classeC1surRd. Ecrire la condition d'optimalite pourx

et redemontrer l'existence d'un multiplicateur0 pour x. 6. Sugg ererune m ethoden umeriqued'appro ximationde x. Exercice 25(Methode de penalisation exterieure).Soientf:Rd!Retg:Rd!Rdeux fonctions continues surRd, strictement convexes avecfcoercive. On note xl'unique solution du probleme sous contrainte min x2Kf(x) ouK:=fx2Rd:g(x)0g L'objectif du probleme est d'approcher xpar une methode de penalisation exterieure. Pour tout >0, on pose J (x) :=f(x) +1 (maxf0;g(x)g)28x2Rd: 1.

Mon trerque Jpossede un unique minimumxdansRd.

2. Mon trerque la famille ( x) est bornee pour2(0;1). 3. Soit x2K. Veriez queJ(x)J(x)f(x). En deduire que, si ~xest une valeur d'adherence de (x) lorsque!0, alorsf(x)f(~x). 4.

Conclure que ( x) tend vers xlorsque!0.

5. On supp oseque fetgsont de classeC1surRd. Verier queJest de classeC1et suggerer une methode numerique d'approximation de x. 6. On supp oseq uefetgsont de classeC1surRdet que la contrainteKest qualiee. On dit que la penalisation est exacte si il existe0>0 tel quex= xpour tout2]0;0[. Verier que la penalisation est exacte, si et seulement si, le multiplicateur dans la condition necessaire d'optimalite pour xest nul. 7. Comparer les r esultatsa vecla m ethodede p enalisationin terieurede l'exercice pr ecedent. Exercice 26(Methode de penalisation exacte).Soientf:Rd!Retg:Rd!Rdeux fonctions de classeC1surRd, strictement convexes avecfcoercive. On note xl'unique solution du probleme sous contrainte min x2Kf(x) ouK:=fx2Rd:g(x)0g On suppose que la contrainteKest qualiee et on notele multiplicateur dans la condition necessaire d'optimalite pour x.

Pour tout >0, on pose

J (x) :=f(x) +1 (maxf0;g(x)g)8x2Rd: 1.

Mon trerque Jpossede un unique minimumxdansRd.

2.

Mon trerque si 2]0;1=[, alorsx= x.

3. En pratique, la v aleurde est inconnue et on doit chercher a l'estimer. Montrer que x = xsi2]0;M1[ avecM:= maxx2Kkrf(x)k=minx2@Kkrg(x)k. 6

1.4.2 Programmation lineaire et algorithme du simplexe

Exercice 27.L'objectif de l'exercice est de montrer qu'on peut mettre tout probleme d'opti- misation avec critere et contraintes anes sous la forme standard de la programmation lineaire.

SoitCune matrice de formatmn,a2Rnetd2Rm.

1.

On consid erele probl eme

(P1) infx2Kha;xiouK:=fx2Rn+; Cxdg: On denit alors ~a= (a;0)2Rn+m,~C:= (C Im) de formatm(n+m). Montrer que le probleme (P1) est \equivalent" au probleme (P2) inf (x;y)2~Kh~a;(x;y)iou~K:=f(x;y)2Rn+m+;~C(x;y) =dg au sens ou la valeur de l'inmum est la meme et ou l'on peut construire les solutions de l'un a partir des solutions de l'autre. 2.

On consid erele probl eme

(P3) infx2Kha;xiouK:=fx2Rn; Cx=dg: On pose ~a= (a;a) et~C= (C;C). Montrer que le probleme (P3) est \equivalent" au probleme (P4) inf (x;y)2~Kh~a;(x;y)iou~K:=f(x;y)2R2n+;~C(x;y) =dg

Exercice 28.Soit

K:=fx= (x1;:::;x5)2R5+:x1+x2+x3x4x5= 1; x1x2+x3x4= 1g:

Determiner les sommets deK.

Exercice 29.On rappelle qu'un point extremal d'un ensemble convexe fermeKRnest un pointxdeKtel que, s'il existex1;x22Ket2]0;1[ tels quex=x1+ (1x2), alors x

1=x2=x.

Montrer qu'un ensemble convexe compactKpossede toujours un point extremal. Est-ce encore le cas siKn'est pas compact? (Indication : on pourra considerer le pointxdeKde norme euclidienne maximale.) Exercice 30.On rappelle que, si est une matrice de formatMN, l'ensemblefx; x2RN+g est un ferme deRM. On considere le probleme de programmation lineaire (P) infx2Kha;xiouK:=fx2Rn+; Cx=dg: Montrer que soit l'inmum est1, soit le probleme admet un minimum. (Indication : on pourra considerer l'ensemblef(Cx;ha;xi); x2Rn+g.) 7

2 Programmation dynamique

2.1 Contr^ole optimal en temps discret

Exercice 31.Pourx0 etN2N, on considere le probleme

W(x) := inffN1X

i=0u

2i;ouui0;N1X

i=0u i=xg

On se propose de comparerW(x) par deux methodes :

1. Calculer W(x) en utilisant les conditions necessaires de Kuhn et Tucker. 2. Ecrire le probl emecomme un probl emede con tr^ole ahorizon Net utiliser le principe de programmation dynamique. Pour cela, (a) R eecrirele probl emeen p osantUn(x) = [0;x] pournN2,UN1(x) =x,fn(x;u) = xu,g= 0,`n(x;u) =u2. (b) Ecrire la pr ogrammationdynamique p ourles fonctions v aleursVn. (c)

En d eduirequ eVn(x) =x2=(Nn).

(d)

Calculer W(x).

3.

Comparer les deux m ethodes.

Exercice 32.On s'interesse au probleme de croissance optimale decrit par sup (kt)1 X t=0 tln(ktkt+1) sous les contraintes :k0=k(ouk >0 est donne),kt+12[0;kt] pour toutt2N. Le taux d'actualisation2]0;1[ et la puissance2]0;1[ sont donnes. Pourk >0, on noteW(k) la valeur de ce probleme. L'interpretation economique est que (kt) represente le capital a l'instantt, la dierencektkt+1etant la consommation (en gros la dierence entre la productionktet l'investissementkt+1a l'instantt). 1. P ourk >0, soitv(k) la fonction valeur du probleme v(k) := sup (kt)1 X t=0 tln(kt) sous les memes contraintes que pourW. Montrer quev(k) =ln(k)1et que queWv. 2. Mon trerque West solution de l'equation de de point xe :f=TfavecTl'operateur deni par

Tf(x) := sup

y2[0;x]fln(xy) +f(y)g: pour toutx >0. 3. P ourquoine p euton pas armer ici directemen tque West l'unique solution de l'equation de Bellman? 4. Mon trerque Tv=v+caveccune constante negative a determiner. 5. Calculer les it ereesTnvpourn2N, montrer que cette suite converge vers une limitev1 que l'on explicitera. Montrer enn queTv1=v1. 8

6.Mon trerque Wv1.

7.

Mon trerque Wv1(plus dicile) et conclure.

8. Mon trerque le probl emeinitial admet une solution u niqueque l'on calculera. On notera (kt) cette politique optimale. 9. Etudier la dynamique optimale ( kt) (monotonie, convergence).

Exercice 33.Pourx0 etN1 un entier, on denit

V

N(x) := sup(

N1Y i=0x i:xi0;N1X i=0x i=x)

1.CalculerV1

2.Trouver une relation de recurrence entreVNetVN1

3.Montrer que

V

N(x) =xNN

N

4.En deduire l'inegalite entre la moyenne geometrique et arithmetique

(jx1jjxNj)1N jx1j++jxNjN

Et etudier le cas d'egalite.

Exercice 34.Resoudre le probleme

min xt2 X t=0(x2t+tu2t) +x23 avecxtveriant la dynamiquext+1=xtutetx0= 1

Exercice 35.Trouver les extrema de

3 X t=0(teut+xt)2x4 avecxtveriant la dynamiquext+1=xt+utetx0=xet sous la contrainte 0u1

Exercice 36.Resoudre le probleme

min u4 X t=12ut3(xtut) avecxtveriant la dynamiquext+1= 0:8ut+0:5(xtut) sous la contrainte 0uet 0(xu) 9

Exercice 37.Resoudre le probleme

min u3 X t=012 (x2t+u2t) +12 x24 avecxtveriant la dynamiquext+1=xtutavecx0= 1

Exercice 38.Resoudre le probleme

max(x1+ 4x2+ 2x3) avecx1+x2+x3= 1 etxi0

2.2 Calcul des variations

Exercice 39.Ecrire les equations d'Euler associees au probleme suivant et en calculer les solutions : J

1(x) =

1 0quotesdbs_dbs6.pdfusesText_11

[PDF] cours optimisation pdf

[PDF] cours optique géométrique mpsi

[PDF] cours optique géométrique smpc s2 pdf

[PDF] cours optique ondulatoire prépa

[PDF] cours organisation des entreprises pdf

[PDF] cours outils mathématiques

[PDF] cours outlook 2010 pdf

[PDF] cours paces ue3 pdf

[PDF] cours paie pdf

[PDF] cours pc 4eme pdf

[PDF] cours pdf économie de la construction

[PDF] cours permanente cap coiffure

[PDF] cours permanente coiffure

[PDF] cours pharmacologie 3eme annee medecine

[PDF] cours philosophie terminal e