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

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

L'objectif de l'exercice est de montrer qu'on peut mettre tout probl`eme d'opti- misation avec crit`ere et contraintes affines sous la forme standard de la 

[PDF] MS41 Optimisation I - Gloria FACCANONI

29 juil 2014 · Les exercices permettent d'orienter les raisonnements vers d'autres de l'aide ( voir le début de la correction, en parler à un autre étudiant, interroger les tuteurs) de la surface avec le plan horizontal d'équation z = B0

[PDF] Optimisation

3 4 4 Petit guide du choix et de l'utilisation d'une méthode d'optimisation 59 D'autres exemples sont dans la séance d'exercices On note l'application d' une forme linéaire b à un vecteur v quelconque avec un " " : b v, au lieu de

[PDF] EXERCICES DU COURS DOPTIMISATION - ENS Rennes

Exercice 6: Même exercice avec la projection d'un point de R3 sur un plan Exercices du chapitre 3 Exercice 1: Soit f la fonction numérique `a variable réelle  

[PDF] 345 Exercices (optimisation avec contraintes)

16 sept 2016 · Exercice 126 (Aire maximale d'un rectangle à périmètre donné) Corrigé en page 268 1 On cherche à maximiser l'aire d'un rectangle de 

[PDF] Table des matières 1 Calcul différentiel

QUELQUES EXERCICES CORRIGÉS D'OPTIMISATION Yannick Correction 1 Le problème s'écrit inf X∈R3 J(X) avec X = a b c et J(X) = N

[PDF] Éléments de Cours, exercices et problèmes corrigés - Institut de

OPTIMISATION Éléments de Cours, exercices et problèmes corrigés D AZÉ J - B HIRIART-URRUTY 2 1 Le problème de l'optimisation avec contrainte

[PDF] Exercices corrigés de la leçon optimisation sans contrainte Partie 3

d) f(x,y) = xy − x2 e) f(x,y) = x3 + y2 − 3x − 12y + 10 Exercice 4 Un industriel produit simultanément 2 biens A et B dont il a le monopole de la production et de  

[PDF] TECHNIQUES DOPTIMISATION J-C Hennet Correction

Exercice 1 ⎛ Tableau simplexe initial apr`es introduction des variables d'écart : Nouvelle solution de base: x2 = 10, x5 = 34 et z = 40, avec x1 = x3 = x4 = 0

[PDF] Méthodes dOptimisation - LMPA

3 2 Exercice synthétique corrigé : construction d'un pont 33 7 2 Recherche d'un flot maximal dans un réseau avec capacités

[PDF] exercices avec corrigés de comptabilité nationale sur le tee et le tes

[PDF] exercices axe corporel

[PDF] exercices bac spé maths es

[PDF] exercices beton arme avec leurs solutions pdf

[PDF] exercices biologie générale

[PDF] exercices calculs commerciaux bac pro commerce

[PDF] exercices calculs d aires cap

[PDF] exercices chimie kc

[PDF] exercices chimie organique 1ere année pharmacie pdf

[PDF] exercices cinématique terminale s

[PDF] exercices classes grammaticales 6ème

[PDF] exercices concept de base de la comptabilité générale

[PDF] exercices concept de base de la comptabilité générale pdf

[PDF] exercices conjugaison 6ème imparfait passé simple

[PDF] exercices conjugaison 6eme imprimer

Exercices sur le cours

\Optimisation et programmation dynamique"

2018-2019

Master mention Math´ematiques appliqu´ees 1`ere ann´ee

Universit´e Paris Dauphine

1 Optimisation

1.1 Le theor`eme de Kuhn et Tucker

Exercice 1.On consid`ere le probl`eme

max g(x)0f(x) Montrer que, sixest un maximum du probl`eme et la contrainte est qualifi´ee enx, alors il existe

0 tel que

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

Exercice 2.On consid`ere le probl`eme de la boite

min x i0 x

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

1.

Prop oserune in terpr´etationdu probl `eme.

2. On supp oseque le probl `emeadmet une solution. Ecrire le sconditions n ´ecessairesd"opti- malit´e et calculer cette solution. 3. (dicile) Mon trerque le probl `emeadmet bien une solution

Exercice 3.On consid`ere probl`eme

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

Exercice 4.On consid`ere le probl`eme

max 0xi42 x

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

Calculer la solution de ce probl`eme.

Exercice 5.On consid`ere le probl`eme

max 0x

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

1

1.Mon trerque le p oint(0 ;1) est le seul point v´erifiant les conditions n´ecessaires.

2. Mon trerque le p oint(1 ;0) est le minimum du probl`eme. Exercice 6.SoitAune matrice sym´etrique de formatnn. 1.

Mon trerque

m= minkxk=1xTAx est la plus petite valeur propre deA. 2. Soien tfvigi=1;:::;kune famille de vecteurs propres deA, deux `a deux orthogonaux. Montrer que la quantit´e min kxk= 1; v

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

TAx est une valeur propre deA. Exercice 7.SoitPl"hyperplan deRNd"´equationcTx=d(o`uc2Rn,d2R). Calculer la projection orthogonale d"un pointydeRnsurP, c"est-`a-dire le minimum du probl`eme min cTx=d12 kxyk2

Exercice 8.Quelles conditions doivent v´erifier les r´eelsp,q,rpour que la fonction lin´eaire

(x1;x2;x3;x4)!x1+px2+qx3+rx4atteigne son maximum sous les contraintes 0x1x2 x

3x4au point (0;0;13

;23 Exercice 9.Les probl`emes 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 10.Calculer, en fonction du param`etreu2R, la solution du probl`eme min 8< :0xyz x+y+z1(xy+uxz+u2yz)

Exercice 11.D´eterminer les points v´erifiant les conditions n´ecessaires d"optimalit´e et trouver

la solution du probl`eme si celle-ci existe : max 8< :y0; yx x+y+ 30x 2+y

Exercice 12.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

2

Montrer que le probl`eme

maxX2SXTMX admet une unique solution. La calculer.

Ind. L"inverse deMestM1=14

0 @311 1 31 11 31 A Exercice 13.On cherche `a r´esoudre le probl`eme (P) min(x;y)2K(x2)2+y2o`uK=f(x;y)2R2j2xy21 etx0g: 1. Mon trerque le probl `emeadmet au moins une solution. 2. Mon trerque la con trainteest qualifi ´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.2 Dualite

Exercice 14.R´esoudre par dualit´e le probl`eme min x2+y21 y+z012 (x2)2+y2+z2

Exercice 15.Calculer le probl`eme dual de

min log(x)y0 y1x+12 y2 Exercice 16.R´esoudre par dualit´e le probl`eme min 1? xTAx1cTx o`uAest une matrice sym´etrique d´efinie positive de formatnn, etcun vecteur deRn.

Exercice 17.On s"int´eresse au probl`eme

(P) minCxd12 xTAx+bTx o`uAest une matricennd´efinie positive,best un vecteur deRn,Cest une matrice de format lnetdest un vecteur deRl. L"expressionCxdsignifie que toute composante deCx

est inf´erieure ou ´egale `a la composante correspondante ded. Montrer que le probl`eme dual du

probl`eme (P) est le probl`eme suivant max

2Rl+12

TCA1CT(bTA1CT+dT)

3 Exercice 18.On consid`ereai(i= 1;:::;n) des r´eels strictement positifs, etxtel quePn i=1x2i=a2i>

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

E=fu2RnjnX

i=1x

2i=a2i1g

Calculer le probl`eme duald() du probl`eme

min u2Ekuxk2

Montrer que le maximum ded() v´erifie

n X i=1a

2ix2i(a2i+)2= 1:

Exercice 19.R´esoudre par dualit´e le probl`eme min hs;xi012 kxk2 hc;xi o`usetcsont des vecteurs deRnnon nuls.

Exercice 20.On consid`ere le probl`eme

min

Ax=b12

kxk2 o`uAest une matricemnetbun vecteur deRm. 1. Quelle est la signification g ´eom´etriquede 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.

1.3 Methodes numeriques

1.3.1 Methodes de penalisation

Exercice 21(M´ethode de p´enalisation int´erieure).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) o`uK:=fx2Rd:g(x)0g poss`ede une unique solution x. L"objectif du probl`eme est d"approcher xpar une m´ethode de p´enalisation. Pour tout >0, on pose J (x) :=f(x)g(x)8x2Int(K) =fx2Rd:g(x)<0g: 4

2.Mon trerque Jposs`ede un unique minimumxdansInt(K).

3. Soit x2Int(K). V´erifiez queJ(x)J(x)f(x). En d´eduire que, si ~xest une valeur d"adh´erence de (x) lorsque!0, alorsf(x)f(~x). 4.

Conclure que ( x) tend vers xlorsque!0.

5. On s upposeque fetgsont de classeC1surRd. Ecrire la condition d"optimalit´e pourx et red´emontrer l"existence d"un multiplicateur0 pour x. 6. Sugg ´ererune m ´ethoden um´eriqued"appro ximationde x. Exercice 22(M´ethode de p´enalisation ext´erieure).Soientf:Rd!Retg:Rd!Rdeux fonctions continues surRd, strictement convexes avecfcoercive. On note xl"unique solution du probl`eme sous contrainte min x2Kf(x) o`uK:=fx2Rd:g(x)0g

L"objectif du probl`eme est d"approcher xpar une m´ethode de p´enalisation ext´erieure. Pour tout

>0, on pose J (x) :=f(x) +1 (maxf0;g(x)g)28x2Rd: 1.

Mon trerque Jposs`ede un unique minimumxdansRd.

2. Mon trerque la famille ( x) est born´ee pour2(0;1). 3. Soit x2K. V´erifiez queJ(x)J(x)f(x). En d´eduire que, si ~xest une valeur d"adh´erence de (x) lorsque!0, alorsf(x)f(~x). 4.

Conclure que ( x) tend vers xlorsque!0.

5. On supp oseque fetgsont de classeC1surRd. V´erifier queJest de classeC1et sugg´erer une m´ethode num´erique d"approximation de x. 6. On supp oseq uefetgsont de classeC1surRdet que la contrainteKest qualifi´ee. On dit que la p´enalisation est exacte si il existe0>0 tel quex= xpour tout2]0;0[. V´erifier que la p´enalisation est exacte, si et seulement si, le multiplicateur dans la condition n´ecessaire d"optimalit´e pour xest nul. 7.

Comparer les r ´esultatsa vecla m ´ethodede p ´enalisationin t´erieurede l"exercice pr ´ec´edent.

Exercice 23(M´ethode de p´enalisation exacte).Soientf:Rd!Retg:Rd!Rdeux fonctions de classeC1surRd, strictement convexes avecfcoercive. On note xl"unique solution du probl`eme sous contrainte min x2Kf(x) o`uK:=fx2Rd:g(x)0g On suppose que la contrainteKest qualifi´ee et on notele multiplicateur dans la condition n´ecessaire d"optimalit´e pour x.

Pour tout >0, on pose

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

Mon trerque Jposs`ede 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. 5

1.3.2 Programmation lineaire et algorithme du simplexe

Exercice 24.L"objectif de l"exercice est de montrer qu"on peut mettre tout probl`eme d"opti- misation avec crit`ere et contraintes anes sous la forme standard de la programmation lin´eaire.

SoitCune matrice de formatmn,a2Rnetd2Rm.

1.

On consid `erele probl `eme

(P1) infx2Kha;xio`uK:=fx2Rn+; Cxdg: On d´efinit alors ~a= (a;0)2Rn+m,~C:= (C Im) de formatm(n+m). Montrer que le probl`eme (P1) est \´equivalent" au probl`eme (P2) inf(x;y)2Kh~a;(x;y)io`uK:=f(x;y)2Rn+m+;~C(x;y) =dg au sens o`u la valeur de l"infimum est la mˆeme et o`u l"on peut construire les solutions de l"un `a partir des solutions de l"autre. 2.

On consid `erele probl `eme

(P3) infx2Kha;xio`uK:=fx2Rn; Cx=dg: On pose ~a= (a;a) et~C= (C;C). Montrer que le probl`eme (P3) est \´equivalent" au probl`eme (P4) inf(x;y)2Kh~a;(x;y)io`uK:=f(x;y)2R2n+;~C(x;y) =dg

Exercice 25.Soit

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

D´eterminer les sommets deK.

Exercice 26.On rappelle qu"un point extr´emal d"un ensemble convexe ferm´eKRnest un pointxdeKtel que, s"il existex1;x22Ket2]0;1[ tels quex=x1+ (1x2), alors x

1=x2=x.

Montrer qu"un ensemble convexe compactKposs`ede toujours un point extr´emal. Est-ce encore le cas siKn"est pas compact? (Indication : on pourra consid´erer le pointxdeKde norme euclidienne maximale.) Exercice 27.On rappelle que, si Γ est une matrice de formatMN, l"ensemblefΓx; x2RN+g est un ferm´e deRM. On consid`ere le probl`eme de programmation lin´eaire (P) infx2Kha;xio`uK:=fx2Rn+; Cx=dg: Montrer que soit l"infimum est1, soit le probl`eme admet un minimum. (Indication : on pourra consid´erer l"ensemblef(Cx;ha;xi); x2Rn+g.) 6

2 Programmation dynamique

2.1 Contr^ole optimal en temps discret

Exercice 28.Pourx0 etN2N, on consid`ere le probl`eme

W(x) := inffN1X

i=0u

2i;o`uui0;N1X

i=0u i=xg On se propose de comparerW(x) par deux m´ethodes : 1. Calculer W(x) en utilisant les conditions n´ecessaires de Kuhn et Tucker. 2. Ecrire le probl `emecomme u nprobl `emede c ontrˆole` ahorizon Net utiliser le principe de programmation dynamique. Pour cela, (a) R ´e´ecrirele 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 29.On s"int´eresse au probl`eme de croissance optimale d´ecrit par sup (kt)1 X t=0 tln(ktkt+1) sous les contraintes :k0=k(o`uk >0 est donn´e),kt+12[0;kt] pour toutt2N. Le taux d"actualisation2]0;1[ et la puissance2]0;1[ sont donn´es. Pourk >0, on noteW(k) la valeur de ce probl`eme. L"interpr´etation ´economique est que

(kt) repr´esente le capital `a l"instantt, la di´erencektkt+1´etant la consommation (en gros la

di´erence entre la productionktet l"investissementkt+1`a l"instantt). 1. P ourk >0, soitv(k) la fonction valeur du probl`eme v(k) := sup (kt)1 X t=0 tln(kt) sous les mˆemes contraintes que pourW. Montrer quev(k) =ln(k)1et que queWv. 2. Mon trerque West solution de l"´equation de de point fixe :f=TfavecTl"op´erateur d´efini 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 n´egative `a d´eterminer. 5. Calculer les it ´er´eesTnvpourn2N, montrer que cette suite converge vers une limitev1 que l"on explicitera. Montrer enfin queTv1=v1. 7

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 30.Pourx0 etN1 un entier, on d´efinit

V

N(x) := sup(

NY i=0x i:xi0;NX i=0x i=x)

1.CalculerV1

2.Trouver une relation de r´ecurrence entreVNetVN1

3.Montrer que

V

N(x) =xNN

N

4.En d´eduire l"in´egalit´e entre la moyenne g´eom´etrique et arithm´etique

quotesdbs_dbs21.pdfusesText_27