1 Les conditions de Kuhn-Tucker PDF

Optimisation non-linéaire

Exercice I.4 Calculer le gradient et la matrice Hessienne des fonctions suivantes : f(xy) = x3 + 3xey

RO04/TI07 - Optimisation non-linéaire

Exercices. Documents section ? suivant ?. 7. ??. Formulation générale des problèmes d'optimisation non linéaire. La forme générale d'un problème

Optimisation non linéaire : correction des TD

17 jan. 2008 Dans cet exercice nous chercherons à optimiser la fonction sans contrainte puis nous vérifierons a posteriori que l'optimum se trouve dans le ...

TD 1 Optimisation non linéaire : Généralités

Optimisation non linéaire : Généralités. Exercice 1 :Étude des fonctions quadratiques. Soient Q une matrice de Rn×n b un vecteur de Rn et f : Rn ? R la

LICENCE 3 MATHEMATIQUES – INFORMATIQUE

systèmes non linéaires optimisation). Pour chaque semaine

RO04/TI07 - Optimisation non-linéaire

Exercices. Documents chapitre ? section suivante ?. 5. I.1 Motivations. I.1.1. Formulation générale des problèmes d'optimisation non linéaire .

1 Les conditions de Kuhn-Tucker

Corrigés d'optimisation convexe et quadratique Exercices corrigés . ... cas de la programmation linéaire ces conditions sont réalisée car une fonction.

Optimisation Non Linéaire Travaux Pratiques I Optimisation sans

Optimisation Non Linéaire. Travaux Pratiques I. Mehmet Ersoy. Optimisation sans contraintes : algorithmes. Le but de ce TP est de tester différentes

Exercices sur le cours “Optimisation et programmation dynamique” 1

“Optimisation et programmation dynamique” o`u s et c sont des vecteurs de Rn non nuls. ... 1.3.2 Programmation linéaire et algorithme du simplexe.

Méthodes numériques pour loptimisation non linéaire déterministe.

f(xk). Démonstration. En exercice. d. Théorème 1.1 f est convexe si et seulement si son épigraphe epi(f) =

UNIVERSIT

E PARIS OUEST NANTERRE LA DEFENSE

U.F.R. SEGMI Annee universitaire 2013 { 2014

Master d'economie Cours de M. Desgraupes

Methodes Numeriques

Document 5 : Corriges d'optimisation convexe et quadratique1 Les conditions de Kuhn-Tucker 1 Rappels de cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Exercices corriges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Les coniques 14

Rappels de cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 Exercices corriges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

3 La methode de Beale 31

Exercices corriges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

4 La methode de Dantzig 46

Rappels de cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Exercices corriges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5 La methode de Wolfe 57

Rappels de cours . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

Exercices corriges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581 Les conditions de Kuhn-Tucker

Rappels de cours

Si on considere un programme d'optimisation convexe note : 8>< :Maxf(x) g(x)b x0 oux= (x1;:::;xn) est un element deRnetgest une fonction deRndansRm: g:x!0 B B@g 1(x) g m(x)1 C CA On suppose que les fonctionsfetgsont contin^ument dierentiables. Le lagrangien associe a ce programme est la fonction :

L(x;) =f(x):(g(x)b) =f(x)1:(g1(x)b1)m:(gm(x)bm):

1 Les coecientss'appellent les coecients de Kuhn-Tucker. Il y en a autant que de contraintes. Le coecientjest associe a la contraintegj(x)bj. Les conditions de Kuhn-Tucker sont des conditions necessaires qui sont rea- lisees a l'optimum du probleme. Elles s'ecrivent vectoriellement de la maniere suivante : r xL0x0x:rxL= 0 (1) r

L00:rL= 0 (2)

On peut les expliciter, pour chaque variablexi(i= 1;:::;n) et pour chaque coecientj(j= 1;:::;m), de la maniere suivante : x i0@L@x i0xi@L@x i= 0 j0@L@ j0j@L@ j= 0 On peut remarquer, en derivant directementLpar rapport aj, que la condition @L@ j0 est simplement la contraintegj(x)bj. Les conditionsx:rxL= 0 et:rL= 0 sont appeleesrelations d'exclusion. En toute generalite, les conditions de Kuhn-Tucker sont des conditionsne- cessaires, autrement dit, si on est en un point optimum, elles sont toujours realisees. Mais elles ne sont pas forcementsusantes: autrement dit, ce n'est pas parce qu'elles sont realisees en un point (x;) que ce point est obligatoi- rement un optimum. Neanmoins, il existe des situations ou on peut armer qu'elles sont eectivement susantes : c'est le cas en particulier lorsque la fonc- tionfestconcaveet les fonctionsgjsontconvexes. C'est pourquoi on s'interesse a l'optimisation convexe. En resume, dans le cas oufest concave et lesgsont convexes, les conditions de Kuhn-Tucker sont des conditions necessaires et susantes d'optimalite. Dans cette situation, un point est optimalsi et seulement siles conditions sont toutes realisees. Si jamais une seule des conditions n'etait pas realisee, le point ne pourrait pas ^etre une solution optimale du probleme. Noter que dans le cas d'une minimisation, la condition susante ci-dessus est inversee : la fonctionfestconvexeet les fonctionsgjsontconcaves. Dans le cas de la programmation lineaire, ces conditions sont realisee car une fonction lineaire est a la fois convexe et concave.

Ecriture avec des variables d'ecart

Si on introduit des variables d'ecartx0dans les contraintes, l'ecriture des conditions de Kuhn-Tucker est modiee. Les contraintes s'ecrivent : g(x) +x0=b et le lagrangien est deni de la maniere suivante :

L(x;x0;) =f(x):g(x) +x0b:

C'est une fonction desx, desx0et des.

2 Dans ce cas, les conditions de Kuhn-Tucker s'ecrivent comme ceci : x0rxL0x:rxL= 0 (3) x

00rx0L0x0:rx0L= 0 (4)

0rL= 0 (5)

On peut les expliciter, pour chaque variablexi(i= 1;:::;n), pour chaque variablex0jet pour chaque coecientj(j= 1;:::;m), de la maniere suivante : x i0@L@x i0xi@L@x i= 0 x

0j0@L@x

0j0x0j@L@x

0j= 0 j0@L@ j= 0 Exercices corrigesCorrige ex. 1 - Conditions de Kuhn-Tucker

Programme 1

8 >>>>>>>:Max(x313x2) x

1x2+ 20

2x1+x220

1+ 2x2100

7x1+ 2x2280

x 1;x20 Les deux premieres contraintes doivent ^etre reecrites sous la forme : x1+x22

2x1x2 2

Le lagrangien s'ecrit de la maniere suivante :

L(x;) =x313x21(x1+x22)2(2x1x2+ 2)

3(x1+ 2x210)4(7x1+ 2x228)

Les conditions de Kuhn-Tucker sont donc les suivantes. Il y a tout d'abord les conditions de signe sur les variables : x

10; x20; 10; 20; 30; 40

Il faut ensuite calculer les derivees partielles par rapport a ces variables et poser les conditions de signe correspondantes. Dans le cas des derivees par 3 rapport aux coecients, on retrouve les contraintes :

3x21+1+ 223740

31+223240

1x2+ 20

2x1+x220

1+ 2x2100

7x1+ 2x2280

Il y a enn les relations d'exclusion :

1(3x21+1+ 22374) = 0

2(31+22324) = 0

1(x1x2+ 2) = 0

2(2x1+x22) = 0

3(x1+ 2x210) = 0

4(7x1+ 2x228) = 0

Ce sont ces dernieres conditions qui servent a mener la discussion car elles presentent une alternative. L'un des deux termes du produit doit ^etre nul. On discute donc en testant les deux possibilites. On cherche a maximiser la fonction objectiff=x313x2. Intuitivement, on voit qu'il faut choisirx1le plus grand possible etx2le plus petit possible. On va donc chercherx2= 0 (les variables doivent ^etre positives). On est conduit, en remplacant dans les conditions ax1= 4, puis1=2=

3= 0 et1= 48=7. C'est l'optimum du probleme et on peut verier qu'il

remplit toutes les conditions de Kuhn-Tucker.

Programme 2

8 >>:Max(4x13x2) x

1+ 2x27

2x1+ 5x28

x 1;x20 La deuxieme contrainte doit ^etre reecrite sous la forme :

2x15x2 8

Le lagrangien s'ecrit de la maniere suivante :

L(x;) = 4x13x21(x1+ 2x27)2(2x15x2+ 8)

Les conditions de Kuhn-Tucker sont donc les suivantes. Il y a tout d'abord les conditions de signe sur les variables : x

10; x20; 10; 20

4 Il faut ensuite calculer les derivees partielles par rapport a ces variables et poser les conditions de signe correspondantes. Dans le cas des derivees par rapport aux coecients, on retrouve les contraintes :

41+ 220

321+ 520

1+ 2x27

2x1+ 5x28

Il y a enn les relations d'exclusion :

1(41+ 22) = 0

2(321+ 52) = 0

1(x1+ 2x27) = 0

2(2x1+ 5x28) = 0

La discussion des relations d'exclusion conduit a la solution suivante : x

1= 7; x2= 0; 1= 4; 2= 0:Corrige ex. 2 - Methode de Lagrange-3-2-10123

-2 -1 0 1 2 x yl ll ll x1 x2M a b1) Pour determiner le rectangle, il sut de trouver les coordonnees de son coin superieur droitM. Si (x1;x2) sont les coordonnees deM, la surface du 5 rectangle estS= 2x12x2= 4x1x2. Le probleme s'ecrit donc :

8>>>><

>>>:Max(4x1x2) x 21a

2+x22b

2= 1 x 1;x20 On peut le traiter directement par la methode de Lagrange. Le lagrangien est :

L(x1;x2;) = 4x1x2x21a

2+x22b

21
On annule les derivees partielles deLpar rapport aux variablesx1,x2et:

8>>>>>>><

>>>>>>:@L@x

1= 4x22x1a

2= 0 @L@x

2= 4x12x2b

2= 0 @L@x

1=x21a

2+x22b

21
= 0 En eliminantentre les deux premieres equations, on obtient la relation a

2x22=b2x21. En la reportant dans l'equation de la contrainte, on trouve na-

lementx21=a22 et doncx22=b22 . Comme on cherche une solution positive, la reponse est : 8>>< >:x 1=ap2 x 2=bp2

La surface maximale du rectangle est donc 2ab.

2) C'est une generalisation de la question precedente. Le probleme s'ecrit :

8>>>><

>>>:Max(8x1x2x3) x 21a

2+x22b

2+x23c

2= 1 x

1;x2;x30

La resolution est identique et conduit a la solution suivante :

8>>>>><

>>>>:x 1=ap3 x 2=bp3quotesdbs_dbs18.pdfusesText_24

[PDF] 1 Les conditions de Kuhn-Tucker

UNIVERSIT

E PARIS OUEST NANTERRE LA DEFENSE

U.F.R. SEGMI Annee universitaire 2013 { 2014

Master d'economie Cours de M. Desgraupes

Methodes Numeriques

2 Les coniques 14

3 La methode de Beale 31

4 La methode de Dantzig 46

5 La methode de Wolfe 57

Rappels de cours

L(x;) =f(x):(g(x)b) =f(x)1:(g1(x)b1)m:(gm(x)bm):

L00:rL= 0 (2)

Ecriture avec des variables d'ecart

L(x;x0;) =f(x):g(x) +x0b:

C'est une fonction desx, desx0et des.

00rx0L0x0:rx0L= 0 (4)

0rL= 0 (5)

0j0@L@x

0j0x0j@L@x

Programme 1

1x2+ 20

2x1+x220

1+ 2x2100

7x1+ 2x2280

2x1x2 2

Le lagrangien s'ecrit de la maniere suivante :

L(x;) =x313x21(x1+x22)2(2x1x2+ 2)

3(x1+ 2x210)4(7x1+ 2x228)

10; x20; 10; 20; 30; 40

3x21+1+ 223740

31+223240

1x2+ 20

2x1+x220

1+ 2x2100

7x1+ 2x2280

Il y a enn les relations d'exclusion :

1(3x21+1+ 22374) = 0

2(31+22324) = 0

1(x1x2+ 2) = 0

2(2x1+x22) = 0

3(x1+ 2x210) = 0

4(7x1+ 2x228) = 0

3= 0 et1= 48=7. C'est l'optimum du probleme et on peut verier qu'il

Programme 2

1+ 2x27

2x1+ 5x28

2x15x2 8

Le lagrangien s'ecrit de la maniere suivante :

L(x;) = 4x13x21(x1+ 2x27)2(2x15x2+ 8)

10; x20; 10; 20

41+ 220

321+ 520

1+ 2x27

2x1+ 5x28

Il y a enn les relations d'exclusion :

1(41+ 22) = 0

2(321+ 52) = 0

1(x1+ 2x27) = 0

2(2x1+ 5x28) = 0

1= 7; x2= 0; 1= 4; 2= 0:Corrige ex. 2 - Methode de Lagrange-3-2-10123

8>>>><

2+x22b

L(x1;x2;) = 4x1x2x21a

2+x22b

8>>>>>>><

1= 4x22x1a

2= 4x12x2b

1=x21a

2+x22b

2x22=b2x21. En la reportant dans l'equation de la contrainte, on trouve na-

La surface maximale du rectangle est donc 2ab.

2) C'est une generalisation de la question precedente. Le probleme s'ecrit :

8>>>><

2+x22b

2+x23c

1;x2;x30

8>>>>><