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

(x1,x2,x3,x4) → x1 +px2 +qx3 +rx4 atteigne son maximum sous les contraintes 0 ≤ x1 ≤ x2 ≤ x3 ≤ x4 au point (0,0, 1 3 , 2 3 )? Exercice 9 Les probl`emes

Fondamentales, CSMI QUELQUES EXERCICES CORRIGÉS D'OPTIMISATION 3 Analyse des problèmes d'optimisation sous contrainte 9 4 Algorithmes

[PDF] 345 Exercices (optimisation avec contraintes)

16 sept 2016 · OPTIMISATION SOUS CONTRAINTES Exercice 125 (Sur l'existence et l'unicité ) Corrigé Suggestions en page 244, corrigé en page 269

[PDF] Séance 4 : Exercices corrigés OPTIMISATION SOUS CONTRAINTES

Mathématiques 2 1 Séance 4 : Exercices corrigés OPTIMISATION SOUS CONTRAINTES Objectifs Exemples d'application du théorème de Lagrange

[PDF] OPTIMISATION CONTRAINTE

Corrigé de l'exercice 1 1 On doit résoudre un problème d'extremum pour une fonction de deux variables soumise à une contrainte donnée sous forme d'égalité

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

(x1,x2,x3,x4) → x1 +px2 +qx3 +rx4 atteigne son maximum sous les contraintes 0 ≤ x1 ≤ x2 ≤ x3 ≤ x4 au point (0,0, 1 3 , 2 3 )? Exercice 9 Les probl`emes

[PDF] INSA TD 5: Corrigé Exercice 7 : Nous allons résoudre ∂2f ∂x∂y (x

TD 5: Corrigé Exercice 16 : Rappels de cours : Théorème des extrema liés et Lagrangien - Optimisation sous contrainte But : Optimiser f : R2 → R sous la

[PDF] Optimisation sous contraintes - Le laboratoire de Mathématiques

Optimisation sous contrainte Laurent Guillopé Laboratoire de mathématiques Jean Leray Département de mathématiques, UFR Sciences et techniques

[PDF] MS41 Optimisation I - Gloria FACCANONI

29 juil 2014 · On a inclus dans ce texte nombreux exercices corrigés Ceux-ci, de de sorte que, sous la contrainte de budget, la fonction d'utilité peut être

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

2 1 Le problème de l'optimisation avec contrainte Partie II Exercices et problèmes corrigés 7 N° 84 Variations sur les projections sur deux sous- espaces

[PDF] Exercice 1 : Optimisation sous contrainte - Jean-Romain Heu

GM2-Miq2-Pl2, Mathématiques mars 2015 Corrigé du contrôle 1 Exercice 1 : Optimisation sous contrainte Soient f et g deux fonctions définies de R2 vers R de

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)

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

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.

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.

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´eairequotesdbs_dbs18.pdfusesText_24

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

Exercices sur le cours

2018-2019

Universit´e Paris Dauphine

1 Optimisation

1.1 Le theor`eme de Kuhn et Tucker

Exercice 1.On consid`ere le probl`eme

0 tel que

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

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

Prop oserune in terpr´etationdu probl `eme.

Exercice 3.On consid`ere probl`eme

Exercice 4.On consid`ere le probl`eme

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

Calculer la solution de ce probl`eme.

Exercice 5.On consid`ere le probl`eme

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

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

Mon trerque

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

3x4au point (0;0;13

2+y2+ 2z2min

Exercice 12.SoientMla matrice

1 1 21

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

Montrer que le probl`eme

Ind. L"inverse deMestM1=14

1.2 Dualite

Exercice 15.Calculer le probl`eme dual de

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

2Rl+12

TCA1CT(bTA1CT+dT)

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

E=fu2RnjnX

2i=a2i1g

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

Montrer que le maximum ded() v´erifie

2ix2i(a2i+)2= 1:

Exercice 20.On consid`ere le probl`eme

Ax=b12

Calculer le probl `emedual ( D).

1.3 Methodes numeriques

1.3.1 Methodes de penalisation

Mon trerque le probl `emesous con trainte

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

Conclure que ( x) tend vers xlorsque!0.

Mon trerque Jposs`ede un unique minimumxdansRd.

Conclure que ( x) tend vers xlorsque!0.

Pour tout >0, on pose

Mon trerque Jposs`ede un unique minimumxdansRd.

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

1.3.2 Programmation lineaire et algorithme du simplexe

SoitCune matrice de formatmn,a2Rnetd2Rm.

On consid `erele probl `eme

On consid `erele probl `eme

Exercice 25.Soit

D´eterminer les sommets deK.

1=x2=x.