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

[PDF] pdf 173k

On peut déterminer si une fonction est convexe ou concave grâce au comportement de la forme quadratique associée à sa matrice hessienne (la matrice des 

[PDF] Fonctions homogènes, concaves et convexes - LaBRI

Fonctions homog`enes, concaves et convexes Hervé Hocquard matrice hessienne de f a toutes ses valeurs propres négatives ou nulles La fonction f est  

[PDF] COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

2 2 2 Exemples des fonctions convexes, strictement convexes et fortement (la matrice Hessienne de f est le Jacobien du gradient de f ou le gradient de la

[PDF] Cours doptimisation ENSAI Rennes

15 mar 2019 · Lorsque f est de classe C2, la convexité se traduit par une propriété de la matrice hessienne Théor`eme 4 4 2 Si K est convexe et si f est de 

[PDF] Convexité en optimisation, convexité forte

fonction convexe définie sur Ω ⊂ V est différentiable presque partout (au sens de la différentielle seconde s'identifie à la matrice hessienne lorsque f est deux

[PDF] OptiAlgo cours

(a) Comme pour tout x ∈ Rn, la matrice hessienne ∇2f(x) est définie positive, f est strictement convexe d'après le Théorème 2 15 sur les fonctions convexes deux 

[PDF] Analyse du problème

Une fonction f : R n −→ R est dite convexe si, pour tout x, y ∈ R n Fonction strictement convexe La matrice hessienne est toujours symétrique Analyse du  

[PDF] Régime Aménagé - UFR 02 Mathématique 2 Cours d - SAMM

Une fonction f de classe C2 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] Optimisation statique Lagrangien et conditions de Kuhn et Tucker

La matrice hessienne bordée de f est une matrice symétrique carrée d'ordre n + Soit f une fonction de plusieurs variables définie sur un ensemble convexe S

[PDF] Chapitre Concavité et convexité des fonctions de plusieurs variables

Ainsi, l'étude de la concavité et de convexité de ces fonctions repose pleinement sur la détermination de la matrice Hessienne Par ailleurs, ce chapitre se veut 

[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