[PDF] Optimisation statique Lagrangien et conditions de Kuhn et Tucker

COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

[PDF] COURS OPTIMISATION Cours en Master M SITN Ionel Sorin math univ lyon ~ciuperca optim M cours optim M sitn pdf

Fonctions convexes

[PDF] Fonctions convexescours mido dauphine calculDiffOpti cours Lchapter pdf

Fonctions homogènes, concaves et convexes - LaBRI

[PDF] Fonctions homogènes, concaves et convexes LaBRI labri perso hocquard Files homogene pdf

Rappel mathématique

[PDF] Rappel mathématiqueneumann hec ca sites cours docs notes Rapmathe pdf

OptiAlgo cours

[PDF] OptiAlgo cours math info univ paris ~bgalerne m poly opti algo pdf

Optimisation statique Lagrangien et conditions de Kuhn et Tucker

[PDF] Optimisation statique Lagrangien et conditions de Kuhn et Tucker parisschoolofeconomics grenet julien TD Annexe pdf

Fonctions convexes et conjuguées

[PDF] Fonctions convexes et conjuguées dmi usherb ca ~dussault ROPH chap pdf

Convexité d une fonction en un point position - ENSTA ParisTech

[PDF] Convexité d 'une fonction en un point position ENSTA ParisTechperso ensta paristech ~chambey RecapConvexiteLocal pdf

Introduction `a l optimisation - Institut de Mathématiques de Toulouse

[PDF] Introduction `a l 'optimisation Institut de Mathématiques de Toulouse math univ toulouse ~lagnoux CoursOpt pdf

UFR 02 Mathématique 2 Cours d Optimisation Libre Dans R 1

Une fonction f de classe C sur I R est dite convexe (resp concave) si pour tout X D 'après le théorème de Schwartz, la matrice hessienne est symétrique

[PDF] convocation bac 2017 cote d'ivoire

[PDF] convocation bac 2017 en ci

[PDF] convocation bac 2017 ivoirien

[PDF] convocation bepc

[PDF] convocation bepc 2017

[PDF] convocation bepc 2017 ci

[PDF] convocation categorie 3 police

[PDF] convocation ccf cap

[PDF] convocation ccf eps

[PDF] convocation ccf word

[PDF] convocation cnc 2017

[PDF] convocation cns luxembourg

[PDF] convocation dscg 2017

[PDF] convocation examen prof

[PDF] convocation jury examen

TD d"Économie - Julien GrenetÉcole Normale SupérieureAnnée 2007-2008 Vade mecum : Optimisation statique.Lagrangien et conditions de Kuhn et Tucker Ce vade mecum expose la méthode de résolution des programmesd"optimisation sta- tique (par opposition aux programmes d"optimisation dynamique qui ne seront pas abor- dés ici) dans le cas d"une fonction objectif multivariée. Les sections

1et2donnent un

certain nombre de définitions préliminaines. Les sections suivantes exposent les méthodes de résolution des quatre grandes catégories de programmes d"optimisation : optimisation sans contraintes (section

3), optimisation sous contraintes prenant la forme d"équations

(section

4), optimisation sous contraintes prenant la forme d"inéquations (section5) et

optimisation sous contraintes prenant la forme d"inéquations incluant des contraintes de non-négativité (section 6).

1 Préambule

1.1 Définitions préliminaires

Soitf:U→Rune fonction denvariables (x1,x2,...,xn) à valeurs réelles dont l"en- semble de définitionUconstitue un sous-ensemble deR n. On supposera toujours quef est continue et deux fois différentiable.

On notef

?ila dérivée partielle defpar rapport àxi(f?i=∂f(x1,x2,...,xn) ∂xi); on notef??ij la dérivée croisée defpar rapport àxietxj(f??ij=∂2f(x1,x2,...,xn) ∂xi∂xj) Déterminant d"une matrice :Le déterminant d"une matrice est défini par induction : •Une matrice (1,1) est juste un scalairea. Le déterminant de cette matrice est égal àa.

•Matrice (2,2) : soitM=

?a b c d . Le déterminant deMs"écrit ?a b c d =ad-bc.

•Matrice (n,n) : soitM=

(a11a12···a1n a21a22···a2n............ a n1an2···ann))))))

Pour calculer le déterminant deM,

il suffit d"utiliser la méthode dite du " développement selon la première ligne » :

1. on associe à chaque coefficienta

1ide la première ligne de la matriceMun signe +

siiest impair et un signe - siiest pair.

2. Le déterminant deMpeut s"écrire comme la somme desndéterminants d"ordre

n-1 obtenus en éliminant de la matriceMla ligne et la colonne contenant le coefficienta

1i. Chacun de ces déterminants est multiplié par (-1)1+ia1i

1

Exemple : soitM=

(a b cd e fg h i))) . Le déterminant de la matriceMs"écrit : det(M) = ?a b cd e fg h i =a ?e f h i -b ?d fg i +c ?????d e g h =a(ei-fh)-b(di-fg) +c(dh-eg) Mineurs principaux d"une matrice :SoitMune matrice carré symétrique de dimen- sion (n,n). Un mineur principal d"ordrekest le déterminant de la sous-matrice deM d"ordrekobtenue en supprimantn-klignes et lesn-kcolonnes correspondantes dans M.

Exemple : soitM=

(a11a12a13 a21a22a23 a31a32a33)))

Les trois mineurs principaux d"ordre 1 deMsonta

11,a22eta33.

Les trois mineurs principaux d"ordre 2 deMsont :????? a22a23 a11a13 a31a33?????et a11a12 a21a32?????

Le mineur principal d"ordre 3 deMest :

?a11a12a13 a21a22a23 a31a32a33??????? Mineurs principaux diagonaux d"une matrice :SoitMune matrice carré symé- trique de dimension (n,n). Le mineur principal diagonal d"ordrek(notéD k) de la matrice Mest le déterminant de la matrice de taille (k,k) obtenue en éliminant lesn-kdernières lignes etn-kdernières colonnes de la matriceM. Une matrice carré d"ordrenadmetn mineurs principaux diagonaux. N.B. :Le mineur principal diagonal d"ordrekd"une matrice est l"un de ses mineurs principaux d"ordrek.

Exemple : soitM=

(a11a12a13 a21a22a23 a31a32a33)))

Le mineur principal diagonal d"ordre 1 deMesta

11. Le mineur principal diagonal d"ordre 2 est?????a11a12 a21a22?????; le mineur principal diagonal d"ordre 3 est ?a11a12a13 a21a22a23 a31a32a33??????? 2 Matrice hessienne :On appelle matrice hessienneH(x1,x2,...,xn) defla matrice des dérivées secondes defévaluées au point (x

1,x2,...,xn) :

H(x

1,x2,...,xn) =

(f??11f??12···f??1n f??21f??12···f??2n f ??n1f??n2···f??nn)))))) Commef??ij=f??ji?(i,j), la matrice hessienne defest une matrice symétrique d "ordren. Matrice hessienne bordée :On appelle matrice hessienne bordéeH(x1,x2,...,xn) de

fla matrice des dérivées secondes def, bordée par la matrice des dérivées premières def:

H(x1,x2,...,xn) =

(0f?1f?2···f?n f?1f??11f??12···f??1n f?2f??21f??12···f??2n f ?nf??n1f??n2···f??nn)))))))) La matrice hessienne bordée defest une matrice symétrique carrée d"ordren+ 1. Matrice jacobienne :soitG= (g1,g2,...,gm) une fonction définie deRndansRm.

A tout vecteur

?x= (x1,x2,...,xn), la fonctionGassocie le vecteur de fonctions (g

1(?x),g2(?x),...,gm(?x)). On appelle matrice jacobienne deGla matrice de dimension (m,n)

J G(x1,x2,...xn) des dérivées partielles desmfonctions qui composentG: J

G(x1,x2,...,xn) =

(∂g 1 ∂x1(?x)∂g1 ∂x2(?x)···∂g1 ∂xn(?x) ∂g2 ∂x1(?x)∂g2 ∂x2(?x)···∂g2 ∂xn(?x) ∂gm ∂x1(?x)∂g1 ∂x2(?x)···∂gm ∂xn(?x)

1.2 Matrices (semi) définies négatives, matrice (semi) définies positives

Matrice définie positive :SoitMune matrice carrée symétrique. SoitAun vecteur colonne quelconque. On noteA ?sa transposée.Mest dite définie positive si et seulement si : A ?MA >0?A?= 0 N.B. :Les éléments diagonauxaiid"une matrice définie positive sont tous>0. Matrice semi-définie positive :SoitMune matrice carrée symétrique. SoitAun vec- teur colonne quelconque. On noteA ?sa transposée. Une matriceMest dite semi-définie positive si et seulement si : A ?MA?0?A 3 N.B. :Les éléments diagonauxaiid"une matrice semi-définie positive sont tous≥0. Matrice définie négative :SoitMune matrice carrée symétrique. SoitAun vecteur colonne quelconque. On noteA ?sa transposée.Mest dite définie négative si et seulement si : A ?MA <0?A?= 0 N.B. :Les éléments diagonauxaiid"une matrice définie négative sont tous<0. Matrice semi-définie négative :SoitMune matrice carrée symétrique. SoitAun vec- teur colonne quelconque. On noteA ?sa transposée.Mest dite semi-définie négative si et seulement si : A ?MA?0?A Caractérisation :SoitMune matrice carrée symétrique d"ordren. •Mdéfinie positive?sesnmineurs principaux diagonauxD ksont>0. •Msemi-définie positive?tous ses mineurs diagonaux (et pas seulement diagonaux!) D ksont?0. •Mdéfinie négative?sesnmineurs principaux diagonauxD ksont alternativement<0 (kimpair) et>0 (kpair). •Msemi-définie négative?tous ses mineurs principauxD k(et pas seulement diago- naux!) sont alternativement?0 (kimpair) et?0 (kpair).

1.3 Ensembles convexes

Ensemble convexe :Un ensembleSdeRnest convexe ssi,?(x,y)?S2: (1-λ)x+λy?S,?λ?[0,1] Intuitivement, un ensemble convexe est tel que tout segmentreliant deux points de cet ensemble se trouve à l"intérieur de l"ensemble. La figure

1donne un exemple d"ensemble

convexe et un exemple d"ensemble non convexe. Ensemble strictement convexe :Un ensembleSdeRnest strictement convexe ssi, ?(x,y)?S 2: N.B. :La notion d"" ensemble concave » n"existe pas. 4

1.4 Fonctions concaves, fonctions convexes

Soitfune fonction de plusieurs variables définie sur un ensemble convexeS. Fonction concave :fest concave surSssi,?(x,y)?S2et?λ?[0,1], on a : f ?(1-λ)x+λy??(1-λ)f(x) +λf(y) feststrictementconcave surSssi : f ?(1-λ)x+λy?>(1-λ)f(x) +λf(y) Autrement dit, une fonctionfest concave ssi le segment reliant tout couple de points situés sur la surface définie parfest situéau-dessousde cette surface.

La figure

2donne un exemple de fonction strictement concave dans le casà une seule

variable.

La figure

3donne un exemple de fonction strictement concave dans le casà 2 variables.

Fonction convexe :fest convexe surSssi,?(x,y)?S2et?λ?[0,1], on a : f ?(1-λ)x+λy??(1-λ)f(x) +λf(y) feststrictementconvexe surSssi : f ?(1-λ)x+λy?<(1-λ)f(x) +λf(y) Autrement dit, une fonctionfest convexe si le segment reliant tout couple de points situés sur la surface définie parfest situéau-dessusde cette surface.

La figure

4donne un exemple de fonction strictement concave dans le casà 1 variable.

La figure

5donne un exemple de fonction strictement strictement convexe dans le cas

à 2 variables.

N.B. :Il est important de ne pas confondre la notion d"ensembleconvexe avec celle de fonctionconvexe.

Propriétés importantes :

•fconcave? -fconvexe

•Sifetgsont des fonctions concaves (resp. convexes), alors?(a,b)?R 2 +, (a.f+b.g) est une fonction concave (resp. convexe). •Sifest une fonction concave etgest une fonction croissante et concave, alors la fonction g ?f(x)?est concave. •Sifest une fonction convexe etgest une fonction croissante et convexe, alors la fonction g ?f(x)?est convexe. •Une fonction affine est à la fois concave et convexe. 5 Figure 1:Exemples d"un ensemble convexeSet d"un ensemble non convexeS?.

Ensemble convexeS

Ensemble non convexeS?

Figure 2:Fonction (strictement) concavef(x) = 10-x2. -3-2-1123 x 4 6 8 10 f ?x? Figure 3:Fonction (strictement) concavef(x,y) = 6-(x-2)2-(y-2)2. Représentation en 3 dimensions et courbes de niveaux.

Représentation en 3D

0 1 2 3 4 x 0 1 2 3 4 y -2 0 2 4 6 f?x,y? 1 2 3 4 x

Courbes de niveau

01234x

0 1 2 3 4 y5. 5. 4. 3. 2. 1. 6

Figure 4:Fonction (strictement) convexef(x) =x2.

-3-2-1123 x 2 4 6 8 f?x? Figure 5:Fonction (strictement) convexef(x,y) = (x-2)2+ (y-2)2. Représentation en 3 dimensions et courbes de niveaux.

Représentation en 3D

0 1 2 3 4 x 0 1 2 3 4 y 0 2 4 6 8 f?x,y? 1 2 3 4 x

Courbes de niveau

01234x

0 1 2 3 4 y5. 5. 4. 3. 2. 1. 7 Caractérisation pour les fonctions à une seule variable :•fconcave?f ??(x)?0?x?R. •f ??(x)<0?x?R?fstrictement concave (attention : la réciproque n"est pas néces- sairement vraie).

•fconvexe?f

??(x)?0?x?R. •f ??(x)>0?x?R?fstrictement convexe (attention : la réciproque n"est pas néces- sairement vraie). Caractérisation pour les fonctions à plusieurs variables : •fconcave?la matrice hessienne defest semi-définie négative? ?x?Rn. •la matrice hessienne defest définie négative?x?R n?fstrictement concave (atten- tion : la réciproque n"est pas nécessairement vraie). •fconcave?la matrice hessienne defest semi-définie positive?x?R n. •la matrice hessienne defest définie négative?x?R n?fstrictement convexe (atten- tion : la réciproque n"est pas nécessairement vraie). Exemple :Montrer que la fonctionf(x,y,z) =x2+ 2y2+ 3z2+ 2xy+ 2xzest strictement convexe. Solution :SoitHLa matrice hessienne def. Elle s"écrit :

H(x,y,z) =

(f??xxf??xyf??xz f??yxf??yyf??yz f??zxf??zyf??zz)))= (2 2 22 4 02 0 6))) Noter qu"ici, la matrice hessienne est indépendante de ses argumentsx,yetz(ce n"est pas toujours le cas). Les mineurs principaux diagonaux deHsontD

1= 2>0,D2=

4>0 etD

3= 8>0, doncHest définie positive, doncfest strictement convexe.

1.5 Fonctions quasi-concaves, fonctions quasi-convexes

quotesdbs_dbs50.pdfusesText_50