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

EXERCICE III (optimisation sans contrainte). On considère la fonction f définie sur Corrigé de l'exercice. 1. Le problème s'écrit inf. X?R3. J(X) avec.

OPTIMISATION CONTRAINTE

Quels sont les extremums de cette fonctions ? Corrigé de l'exercice 1.1. On doit résoudre un problème d'extremum pour une fonction de deux variables soumise à

Table des matières 1 Calcul différentiel

QUELQUES EXERCICES CORRIGÉS D'OPTIMISATION 2 Analyse des problèmes d'optimisation sans contrainte ... Soit A ? Mnm(R)

Optimisation Sans Contraintes

avec ou sans contraintes cependant on limite souvent l'optimisation à une Hiriart-Urruty

1 Les conditions de Kuhn-Tucker

Corrigés d'optimisation convexe et quadratique Exercices corrigés . ... Si on introduit des variables d'écart x dans les contraintes l'écriture des.

Optimisation sous contraintes

Un problème de recherche de minimum avec contraintes est donc celui pour une fonction définie sur la partie E = {x;g(x)=0} de Rn dépourvue de calcul

Corrigé type de la série des exercices 1 Optimisation sans contraintes

Corrigé type de la série des exercices 1. Optimisation sans contraintes -LMD- S5. Solution de l'exercice 1. Soit f : R2 ?? R la fonction définie f(x y) =.

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

Etudier les paragraphe 3.4 et 3.5 (optimisation avec contrainte). Exercice proposé (avec corrigé) : 139 (Uzawa). Le corrigé du deuxième devoir sera

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

26 mars 2015 Exercice 1. ... Montrer que la contrainte est qualifiée en tout point. ... avec la condition d'exclusion ?g(x y

ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE

doivent être préparés : écouter le corrigé d'un exercice en ont un) avec toutes leurs hypothèses et vérifiez que ces hypothèses sont satisfaites avant ...

OPTIMISATION SOUS CONTRAINTES - HEC Montréal

3 Optimisation sous contrainte à variables multiples La fonction à optimiser peut souvent dépendre de plusieurs facteurs Par exemple les profits réalisés peuvent dépendre du coût des ressources du nombre d'employés du prix de vente

34 Optimisation sous contraintes

La contrainte (1) est représentée par le disque de centre ( r r) et de rayon 2 La contrainte (2) délimite le demi-espae sous la droite d’équation 1+ t 2? t= r La ontrainte (3) désigne les points à droite de l’axe 1= r Les courbes de niveau f(x)=constante sont des cercles de centre ( u t)

345 Exercices (optimisation avec contraintes) - univ-amufr

3 4 5 Exercices (optimisation avec contraintes) Exercice 125 (Sur l'existence et l'unicité) Corrigé en page 268 Etudierl'existenceetl'unicitédessolutionsduproblème (3 48)avecles donnéessuivantes: E = IR ;f : IR ! IR est dén ie par f (x ) = x 2 et pour les quatre différents ensembles K suivants : (i) K = fjx j 1g ; (ii) K = fjx j = 1 g

34 Optimisation sous contraintes - univ-amufr

Ce problèmeest un problèmede minimisationaveccontrainte (ou sous contrainte")au sens oùl'oncherche u qui minimise f en astreignant u a être dans K Voyons quelques exemples de ces contraintes (dén ies par l 'ensemble K ) qu'onva expliciter à l'aide des p fonctionscontinues gi 2 C (E; IR) i = 1 :::p 1 Contraintes égalités

ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE

Le but de l’UE est d’optimiser une fonction de deux variables : optimisation libre ou sous contrainte Documents et bibliographie En L1 de Sciences-Économiques toutes les universités françaises traitent à peu près le même programme de mathématiques mais la répartition sur les deux années la présentation (plus ou moins théorique)

Analyse 2: Optimisation avec contrainte

Analyse 2: Optimisation avec contrainte Minimisation avec contraintes Condition du remierp rdreo Lagrangien et conditions KKT Joseph Salmon Conditions de Karush-Khunn-Tucker (KKT) Théorème : KKT Si x est un minimum local du problème (P) que f;h i;g j sont dérivables avec des gradients continus sous des conditions de quali cation sur x il

Optimisation Continue ISTIL 2ème année Corrigé de la feuille 4

la contrainte C = cste alors ?(ab?)J ? Vect ?(ab?)C 4 Résolution du système La condition d’optimalité signi?e que les vecteurs ?(ab?)J et ?(ab?)C sont colinéaires ou encore que leur produit vectoriel est nul On a ?(ab?)J= 1 2 bsin? 1 2 asin? 1 2 abcos?

ANALYSE RÉELLE OPTIMISATION LIBRE ET SOUS CONTRAINTE

exercices doivent être préparés : écouter le corrigé d’un exercice sans avoir préalablement essayédelerésoudrecelanesertàrien Vousn’enretirerezaucunpro?tpuisquevousn’en aurezpassaisileséventuellesdi?cultés –Des sujets d’annales sont proposés dans le polycopié d’exercices Vous pouvez aussi les re-

Éléments de correction pour le TD d’optimisation sous

TD d’optimisation sous contrainte(s) d’égalité Exercice 1 DanstouslescasétudiéslesfonctionsetcontraintessontclairementC1etleursdomainesdedé?nition sontdesouverts 1 Traitéencours 2 Leseulpointcritiquedelafonction(x;y;z) 7!x2+y2 estl’originequinevéri?epaslacontrainteet

OPTIMISATION CONTRAINTE

§ 1 —Optimisation contrainte à deux variables Exercice1 1 On considère la fonction f(x;y) = x2+y24xysoumise à la contrainte x2+y2 = 8 Quels sont les extremums de cette fonctions? Corrigédel’exercice1 1 On doit résoudre un problème d’extremum pour une fonction de deux variables soumise à une contrainte donnée sous forme d

3104 Optimisation avec contraintes d’egalit´ e´

3 10 4 Optimisation avec contraintes d’egalit´ e ´ Dans de nombreux proble`mes on de´sire identi?er le point x maximisant ou minimisant une fonction f non pas parmi tous les xappartenant au domaine de de´?nition de f mais seulement parmi ceux qui ve´ri?ent une ou plusieurs con traintes du type gk(x)=0 pour tout k ?{12 ?}

Searches related to exercices corrigés doptimisation avec contrainte pdf filetype:pdf

Les coe cients s’appellent les coe cients de Kuhn-Tucker Il y en a autant que de contraintes Le coe cient j est associ e a la contrainte g j(x) b j Les conditions de Kuhn-Tucker sont des conditions n ecessaires qui sont r ea-

Comment calculer la minimisation avec contrainte ?

Soit E = IRn, soit f 2 C (E; IR) , et soit K un sous ensemble de E . On s'intéresse à la recherche de u 2 K tel que : ( u 2 K f (u ) = inf K f (3.53) Ce problèmeest un problèmede minimisationaveccontrainte (ou?sous contrainte")au sens oùl'oncherche u qui minimise f en astreignant u a être dans K .

Comment calculer la courbe de contrainte?

x3+ y + z2sous les contraintes x +y+z = 0 et x +y z = 0. Corrigé de l’exercice 2.2. Posons ’(x;y;z) = x +y+z et (x;y;z) = x +y z. Première étape : les fonctions f, ’et sont C2sur un certain ouvert U ˆR3. Puisque f, ’et 1sont des polynômes, elles sont C sur U = R3. Deuxième étape : la courbe de contrainte est régulière.

Comment calculer la contrainte d'un point ?

Chercher le(s) point(s) où f atteint son maximum ou son minimum sous la contrainte g = 1 . 3. Soient A 2 Mn(IR) symétrique, B 2 Mn(IR) s.d.p. et b 2 IRn. Pour v 2 IRn, on pose f (v) = (1 =2) Av v b v et g(v) = Bv v.

Comment calculer la contrainte d’une fonction?

— Pour chacune des deux questions suivantes on donnera deux méthodes : d’abord en explicitant la contrainte, puis en utilisant le lagrangien. 1. Soient les fonctions f et g dé?nies par : f(x,y) = xy, g(x,y) = 1 x + 1 y .

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 :

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

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

Comment calculer la minimisation avec contrainte ?

Comment calculer la courbe de contrainte?

Comment calculer la contrainte d'un point ?

Comment calculer la contrainte d’une fonction?

Partiel du 26 Mars 2015|Corrige

Universite Paris Dauphine

Dans tout le partiel, on note

Exercice 1.On cherche a resoudre le probleme

Solution :

2y+= 0

2z+= 0

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

8>>>><

2y+ 2y+= 0

2z+= 0

2+y2= 1

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

On p ose

2(1 +)y+= 0

2z+= 0

Solution :

L(y;) =12

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

C1et C2sur les ensemblesC1etC2. On

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

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

2+kC1(xn)xnk2

Solution :

On a :

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

2+kC1(xn)xnk2

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

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