[PDF] Partiel du 26 Mars 2015—Corrigé “Optimisation et programmation

View - Download Partiel du 26 Mars 2015—Corrigé “Optimisation et programmation

Previous PDF

Next PDF

Partiel du 26 Mars 2015|Corrige

\Optimisation et programmation dynamique" Master mention Mathematiques appliquees 1ere annee

Universite Paris Dauphine

Dans tout le partiel, on note

K(x) la projection orthogonale d'un pointxdeRnsur un convexe ferme non videKdeRn. Siy= (yi)i=1;:::;metz= (zi)i=1;:::;msont deux vecteurs de R m, on ecrityz, si et seulement si,yizipour touti= 1;:::;m.

Exercice 1.On cherche a resoudre le probleme

(P) min(x;y;z)2Kx2+y2+z2ouK=f(x;y;z)2R3jx+y+z= 1 etx2+y21g: 1. Mon trerque le probl emeadmet une unique solution. 2. Mon trerque la con trainteest quali eeen tout p oint. 3. Ecrire les conditions n ecessairesd'optimalit edu probl emeet en d eduirela solution du probleme (P). 4. Retrouv erla solution du probl eme( P) par la methode de dualite.

Solution :

1. On r emarqueque la c ontrainteKest fermee et le critere est coercif (c'est la norme eucli- dienne). Donc, par theoreme de cours, le probleme admet au moins une solution. Ensuite on note que le critere est strictement convexe (puisquef(x;y;z) :=x2+y2+z2verie Hess f(x;y;z) = 2I3qui est une matrice denie positive) et la contrainte est convexe (car la fonctionsh: (x;y;z)!x+y+z1est ane et la fonctiong: (x;y;z)!x2+y21 est convexe). Donc le probleme admet une et une seule solution. 2. L ac ontrainteest c onvexe,mais e llea u nint erieurvide. Il faut r eveniraux c onditionsde qualication usuelles. Posonsg(x;y;z) =x2+y21eth(x;y;z) =x+y+z1. On note que ce sont des fonctions de classeC1(en faitC1). Si(x;y;z)2Kverieg(x;y;z)<0, il sut de montrer que la famillefrh(x;y;z) = (1;1;1)gest libre, ce qui est evident puisqu'elle est constituee d'un seul vecteur non nul. Si(x;y;z)2Kverieg(x;y;z) = 0, alors il faut verier que la famillefrh(x;y;z) = (1;1;1)gest libre et qu'il existe un vecteurv2R3tel que hv;rh(x;y;z)i= 0 ethv;rg(x;y;z)i<0: La premiere condition est evidente. Pour la seconde, on peut prendre par exemplev= (x;y;x+y), qui verie bien hv;rh(x;y;z)i=xy+ (x+y) = 0 ethv;rg(x;y;z)i=2x22y2=2<0 puisqueg(x;y;z) =x2+y21 = 0. 3. Comme le crit ereet les fonctions d enissantles c ontraintessont de classe C1et comme la contrainte est qualiee en tout point, les conditions necessaires d'optimalite s'ecrivent : si(x;y;z)2Kest la solution du probleme, alors il existe0et2Rtels que rf(x;y;z) +rg(x;y;z) +rh(x;y;z) = 0 avec la condition d'exclusiong(x;y;z) = 0. Considerons deux cas : sig(x;y;z)<0, alors = 0et le systeme se reduit a8>>< >:2x+= 0

2y+= 0

2z+= 0

x+y+z= 1 qui ne possede qu'une solution solution :x=y=z= 1=3. Notons queg(1=3;1=3;1=3) =

2=9<1. Donc le point(1=3;1=3;1=3)verie les conditions necessaires d'optimalite.

Comme la contrainte est qualiee et que le probleme est convexe, on en deduit que(1=3;1=3;1=3) est un minimum du probleme. Comme ce minium est unique, c'est la seule solution. On pourrait etudier le cas oug(x;y;z) = 0(m^eme si c'est inutile). Le systeme devient :

8>>>><

>>>:2x+ 2x+= 0

2y+ 2y+= 0

2z+= 0

x+y+z= 1 x

2+y2= 1

Comme0, on trouve en utilisant les deux premieres egalites quex=y, ce qui implique par la saturation de la contrainte d'inegalite, quex=y=p2=2ou=1. Donc z= 1p2. Alors=2z=2 +2p2et=1=(2x) =3 + 2p2. Comme

2p2<3, on a <0, ce qui est impossible. Donc la contrainte d'inegalite n'est pas saturee

a l'optimum. 4.

On p ose

L(x;y;z;;) =f(x;y;z)+g(x;y;z)+h(x;y;z) = (1+)(x2+y2)+(x+y)+z2+z: On cherche a minimiserLpar rapport a(x;y;z)pour0. On trouve comme systeme d'optimalite (qui est aussi une condition susante puisqueLest convexe en(x;y;z)) : 8< :2(1 +)x+= 0

2(1 +)y+= 0

2z+= 0

soitx=y==((2(1 +))etz==2. D'ou d(;) = min(x;y;z)2R3L(x;y;z;;) =22(1 +)24 On cherche maintenant le maximum dedsurR+R. Commedest concave (cf. le cours) et que la contraintef0gest convexe et qualiee puisqu'ane, les conditions necessaires sont susantes : il sut de trouver un point veriant les conditions necessaires d'optima- lite, soitrd(;) + (;0) = 0ou0. Orrd(;)(;0) = 0equivaut au systeme (22(1+)21= 0 (1+)2 1 = 0 On note que= 0et=2=3est solution (avec= 7=9). On peut s'arr^eter la, puisque cela fournit une (et donc la) solution du probleme :(x;y;z) = (1=3;1=3;1=3). Si on veut etudier ce qui se passe si la contrainte d'inegalite n'est pas saturee, alors on peut dire que= 0,=p2(1+)(ou=1) et donc=p2(3p2=2+1)<0pour = 1et=1. Donc cette solution est impossible et ce cas est exclus. Exercice 2.1.Soien tn;m2N,Cune matrice reelle de taillemnetd2Rm. On suppose que l'ensembleK:=fx2Rn; Cxdgest non vide. Soitx;y2Rn. Montrer quey= K(x), si et seulement si, il existe2Rmavec0, yx+CT= 0 etT(Cyd) = 0 (ouCTest la transposee de la matriceC). (Indication : Ecrire les conditions necessaires du probleme d'optimisation satisfait par (x)). 2. (Erreur d' enonce)

Solution :

1. L apr ojectionsur Kest la solution du probleme d'optimisation min y2K12 kyxk2 Comme il s'agit d'un probleme convexe, avec une contrainte qualiee puisqu'ane, les conditions necessaires sont susantes. Or

L(y;) =12

kyxk2+mX i=1 i((Cx)idi) =12 kyxk2+TCx: On en deduit queyest solution du probleme, i.e.,y= K(x), si et seulement si, il existe

2Rmavec0etryL(y;) = 0etT(Cyd) = 0. OrryL(y;) = (yx) +CT,

ce qui prouve l'assertion. Exercice 3.SoientC1etC2deux convexes fermes deRnd'intersection non vide. On suppose qu'on sait eectuer numeriquement la projection

C1et C2sur les ensemblesC1etC2. On

cherche a trouver un point deC1\C2. Pour2]0;2[ un parametre xe et x2Rnune position initiale donnee, on denit l'algorithme x 0= x x n+1=2=xn+(C1(xn)xn) (n2N) x n+1=xn+1=2+C2(xn+1=2)xn+1=2(n2N) 1. Mon trerque, si Cest un convexe ferme non vide,x2Cety2Rn, alors : ky+(C(y)y)xk2 kyxk2(2)kC(y)yk2: 2.

En d eduireque, p ourtout x2C1\C2, on a :

kxn+1xk2 kxnxk2(2)

C2(xn+1=2)xn+1=2

2+kC1(xn)xnk2

3. Mon treralors que, p ourtout x2C1\C2, la suite (kxnxk2) converge et verier que la suite (xn) est bornee. 4. Mon trerque toute v aleurd'adh erencede la suite ( xn) appartient aC1\C2.

Solution :

1.

On a :

ky+(C(y)y)xk2=kyxk2+ 2hyx;C(y)yi+2kC(y)yk2 Or hyx;C(y)yi=hyC(y);C(y)yi+hC(y)x;C(y)yi ou hC(y)x;C(y)yi 0 par caracterisation de la projection. Donc hyx;C(y)yi hyC(y);C(y)yi=kyC(y)k2; ce qui montre que ky+(C(y)y)xk2 kyxk2(2)kC(y)xnk2 ce qui est le resultat voulu. 2. On applique le r esultatd'ab ordle r esultatpr ecedententr exn+1etxn+1=2: on trouve kxn+1xk2 kxn+1=2xk2(22)kC2(xn+1=2)xn+1=2k2: Puis on applique le resultat de la question precedente entrexn+1=2etxnpour obtenir l'inegalite desiree : kxn+1xk2 kxnxk2(2)

C2(xn+1=2)xn+1=2

2+kC1(xn)xnk2

3. Comme 2]0;2[, on a22>0. Donc la suite(kxnxk2)est decroissante, minoree : elle admet une limite. En particulier, cette suite est bornee. Comme kxnk kxnxk+kxk la suite(xn)est egalement bornee. 4. Soit xune valeur d'adherence de la suite(xn)et(xnk)une sous-suite qui converge versx.

Notons d'abord que, d'apres la question 2, on a

C2(xn+1=2)xn+1=2

2+kC1(xn)xnk2(22)1kxnxk2 kxn+1xk2

ou la suite a droite tend vers0puisque la suite(kxnxk2)converge. On en deduit que les suites(kC1(xn)xnk)et(

C2(xn+1=2)xn+1=2

)tendent vers0. Appliquees a la sous-suite(xnk), la premiere convergence implique queC1(x) = x. En particulier,x2C1 et la suite(xnk+1=2)converge egalement versx. Alors la second convergence entra^ne de m^eme queC2(x) = x, ce qui signie quex2C2. Cela prouve nalement quex2C1\C2.quotesdbs_dbs29.pdfusesText_35

[PDF] 1S-Cours 11 Champs forces

[PDF] Exercices corrigés du cours de VIBRATIONS et ACOUSTIQUE

[PDF] L 'ADJECTIF QUALIFICATIF

[PDF] Guide

[PDF] Guide

[PDF] agrandissement et réduction_4eme_exos

[PDF] éval aire cm1 - Eklablog

[PDF] 4ème Chapitre12 : Aires et volumes Correction de la feuille 02

[PDF] CLASSE : 5ème CONTROLE sur le chapitre : AIRES LATERALES

[PDF] Exercices d 'algorithmique en seconde Activités transversales

[PDF] Aide-Mémoire en alphabétisation, niveau 1

[PDF] Aide-Mémoire en alphabétisation, niveau 1

[PDF] 5ème soutien N°22 les angles - Collège Anne de Bretagne - Rennes

[PDF] Angle inscrit et angle au centre

[PDF] 3ème CONTROLE sur le chapitre : ANGLES ET POLYGONES