COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin PDF

Convexité en optimisation convexité forte

On dit que f est strictement convexe si l'inégalité ci-dessus est stricte pour x = y t ?]0

Optimisation Convexité

Propriété de stabilité: combinaison positive de fonctions convexes Par contre on peut avoir une fonction strictement convexe avec cependant.

COURS OPTIMISATION Cours en Master M1 SITN Ionel Sorin

fonctions convexes et ?1?2

Fonctions convexes 1 Dimension 1

Elle est strictement convexe si on peut mettre l'inégalité stricte pour ? ?]0 1[ et x = y. Une fonction f est dite (strictement) concave si ?f est

Microéconomie 1 Définitions mathématiques importantes

Figure 1: Fonction convexe. Source: Wikipedia. Fonction strictement convexe. Une fonction f X ? R est dite strictement convexe sur un intervalle C ? X si.

229. Fonctions monotones et fonctions convexes. Exemples et

17 déc. 2009 Toute fonction strictement croissante est injective. Proposition 2. L'ensemble des fonctions croissantes sur I (resp convexes sur C ) un cône ( ...

Analyse 1: convexité et fonction convexe

Joseph Salmon. Fonction strictement convexe. Définition : strictement fonction convexe f : Rd ? R est strictement convexe si elle vérifie ?x0 = x1 ?.

OptiAlgo cours

Une fonction f est (strictement) concave si ?f est (strictement) convexe. Remarque. On peut également restreindre ? à ]01[ pour la définition de la

UTILISATION DE LA NOTION DE CONVEXITÉ EN ANALYSE.

Toute norme Î.Î de E est convexe non strictement convexe dès que E ”= {0}. On déduit de la première équivalence qu'une fonction convexe sur I est ...

[PDF] Convexité en optimisation convexité forte

On dit que f est strictement convexe si l'inégalité ci-dessus est stricte pour x = y t ?]01[ Rappelons que toute fonction convexe possède une régularité

[PDF] Fonctions convexes 1 Dimension 1

Une fonction f est dite (strictement) concave si ?f est (strictement) convexe – Le nombre ?x + (1 ? ?)y ? ? [0 1] est une combinaison convexe de x et y

[PDF] Eléments danalyse et doptimisation convexe

19 fév 2020 · Proposition 2 8 Une fonction fortement convexe est strictement convexe elle ad- met donc un minimiseur unique Note : par contre une fonction

[PDF] FONCTIONS CONVEXES

On montre facilement qu'une fonction fortement convexe est strictement convexe On a aussi la caractérisation suivante : Proposition 3 1 Soit C un convexe

[PDF] Chp 9 Convexité

Dans tout ce chap?tre C désigne une partie convexe de IRn et f une fonction numérique partout définie sur C 9 1 Fonctions affines convexes strictement

[PDF] Cours en Master M1 SITN

Si au moins l'une des fonctions f1··· fp est strictement convexe alors f est stric- tement convexe 3 Si au moins l'une des fonctions f1··· fp est

[PDF] Optimisation convexe - Institut de Mathématiques de Bordeaux

Si f est strictement convexe sur I elle admet au plus un minimiseur • La fonction x ?? ex est strictement convexe sur R et n'admet pas de minimum ni de

[PDF] Fonctions convexes

-I est dite strictement convexe sur C si V¥ G]0 1[Vx y G C x ?=y I(¥x + ( 1 - ¥)y) < ¥I(x) + ( 1 - ¥)I(y) -I est dite fortement convexe sur C s¿il existe

[PDF] Fonctions convexes - Irif

Une fonction f : R ? R est dite convexe sur [a b] si la corde prise Si f et g sont deux fonctions convexes alors f + g est une fonction convexe

[PDF] CONVEXITÉ - Christophe Bertault

Enfin une fonction dérivable f ? (I) est strictement convexe si et seulement si sa dérivée f ? est strictement croissante si et seulement si pour tout a ?

Comment montrer qu'une fonction est strictement convexe ?
Elle est strictement convexe si on peut mettre l'inégalité stricte pour ? ?]0, 1[ et x = y. Une fonction f est dite (strictement) concave si ?f est (strictement) convexe. – Le nombre ?x + (1 ? ?)y, ? ? [0, 1] est une combinaison convexe de x et y, c'est-à-dire un barycentre à coefficients positifs (voir Exercice 1).
Comment déterminer qu'une fonction est convexe ?
Une fonction convexe poss? une dérivée première croissante ce qui lui donne l'allure de courber vers le haut. Au contraire, une fonction concave poss? une dérivée première décroissante ce qui lui donne l'allure de courber vers le bas.
Comment montrer qu'une fonction est strictement concave ?
Propriété : Soit une fonction f définie et dérivable sur un intervalle I. La fonction f est convexe sur I si sa dérivée f ' est croissante sur I, soit f ''(x) ? 0 pour tout x de I. La fonction f est concave sur I si sa dérivée f ' est décroissante sur I, soit f ''(x) ? 0 pour tout x de I.
Théorème 2.1 Un fonction f est convexe si et seulement si, pour tout (x, y) ? (dom(f))2 et ? ? 0 tels que y + ?(y ? x) ? dom(f), f satisfait : f(y + ?(y ? x)) ? f(y) + ?(f(y) ? f(x))._{19 fév. 2020}

COURS OPTIMISATION

Cours en Master M1 SITN

Ionel Sorin CIUPERCA

Table des matières

1 Introduction 4

2 Quelques rappels de calcul différentiel, analyse convexe et extremum 5

2.1 Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.2 Quelques rappels sur le calcul différentiel . . . . . . . . . . . . . . . 6

2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.4 Quelque rappels sur le matrices carrées réelles . . . . . . . . . . . . 11

2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.1 Fonctions convexes, strictement convexes, fortement convexes . . . . 11

2.2.2 Exemples des fonctions convexes, strictement convexes et fortement

convexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

2.2.3 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Conditions nécéssaires et suffisantes de minimum . . . . . . . . . . . . . . 17

2.4 Existence et unicité d"un point de minimum . . . . . . . . . . . . . . . . . 21

3 Optimisation sans contraintes 23

3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 24

3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 27

3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.1 Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 29

3.2.2 Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 30

3.3 La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 33

3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.2 Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 38

4 Optimisation avec contraintes 39

4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 40

4.2 Optimisation sous contraintes d"inégalités . . . . . . . . . . . . . . . . . . . 41

4.2.1 Conditions d"optimalité de premier ordre : multiplicateurs de Karush-

Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.2.2 Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 49

4.2.3 Applications de la théorie du point selle à l"optimisation . . . . . . 51

4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 53

4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.2 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.3 Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 59

4.3.4 Méthode d"Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Chapitre 1

Introduction

En généraloptimisersignifie le fait de chercher une configuration optimale d"un sys-

tème, c"est à dire, chercher la meilleure configuration parmi tous les configurations possibles

du système et ceci, par rapport à un critère donné. Pour décrire (et éventuellement résoudre) un problème d"optimisation nous utilisons la modélisation mathématique. La démarche de modélisation comporte 3 étapes : Etape 1.Choisir lesvariables de décision, qui sont les composantes du système sur lesquelles on peut agir. On supposera dans ce cours qu"il y a un nombre finit notén2IN

de variables de décision, chacune de ces variables étant un nombre réel. Alors les variables

de décision seront représentés par un vecteurx= (x1;x2;xn)T2IRn(vecteur colonne). Etape 2.Décrirel"étatdu système, étant donnée une configuration des variables de décision. Ceci revient mathématiquement à se donner une fonctionJ:IRn!IRqui s"appellefonction objectifoufonction coûtet que nous voulons rendre la plus petite possible ou la plus grande possible. Etape 3.Décrire lescontraintesque les variables de décision satisfont. Ceci revient à définir un ensemble de contraintesUIRnet imposer d"avoirx2U. Pour résumer on peut dire que pour décrire un problème d"optimisation on se donne

1. Une fonctionJ:IRn7!IR(fonction coût)

2. Un ensembleUIRn(ensemble des contraintes)

On cherche à minimiserJsurU, c"est à dire, on cherchex2Utel que

J(x) = minx2UJ(x)

ou équivalent

J(x)J(x);8x2U:

Motivation et exemples pratiques :en classe

Chapitre 2

Quelques rappels de calcul différentiel,

analyse convexe et extremum

2.1 Rappel calcul différentiel

2.1.1 Quelques Notations

1. Pour toutn2IN;IRndésigne l"espaceeuclidienIRIRIR( "produitnfois").

En général un vecteurx2IRnsera notéx= (x1;x2;xn)T(vecteur colonne).

2. On notee1;e2;enles éléments de labase canoniquedeIRn, oùeiest le vecteur

deIRndonné par : (ei)j=ij=0sij6=i

1sij=i;8i;j= 1;2n(2.1)

(ij=symboles deKronecker).

3. Pour tousx;y2IRnon note par< x;y >2IRleproduit scalairedexety, qui

est donné par < x;y >=nX i=1x iyi: Deux vecteursx;y2IRnsontorthogonaux(on noterax?y) si< x;y >= 0.

4. Pour toutx2IRnon note parkxk 0lanorme euclidiennedex, donnée par

kxk=p< x;x >=v uutn X i=1x 2i: Rappellons lespropriétés d"une norme(donc aussi de la norme euclidienne) : i)kxk=jjkxk 82IR;8x2IRn ii)kx+yk kxk+kyk 8x;y2IRn iii)k0k= 0etkxk>0six2IRn f0g. 5

5. Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexet

rayonr, donnée par

B(x;r) =fy2IRn;kyxk< rg:

6. Si x(k) k2INest une suite dansIRnetxest un élément deIRnon dit quex(k) convergeversx(notéex(k)!x) sikx(k)xk !0. Rappellons que nous avons :x(k)!xsi et seulement six(k) i!xienIRoùx(k) i(respectivementxi) est lai-ème composante dex(k)(respectivementx).

7. SoitUIRn.

- On définitl"intérieurdeUcomme l"ensemble des élémentsx2Upour lesquels il exister >0tel queB(x;r)U. - On dit queUestouvertsi8x2U9r >0tel queB(x;r)U. - On dit queUestfermési pour tout suitefx(k)g Utel quex(k)!x2IRnon ax2U.

8. Sia;b2IRnon note[a;b]le sous-ensemble deIRndonné par

[a;b] =fa+t(ba)(1t)a+tb; t2[0;1]g: L"ensemble[a;b]est aussi appelléle segmentreliantaàb.

Remarques :

[a;b] = [b;a](Exo!) Sia;b2IRaveca < bon retrouve la notation[a;b]pour l"intervalle des nombres x2IRtels queaxb.

9. Rappellons aussi l"inégalité de Cauchy-Schwarz :

j< x; y >j kxk kyk 8x;y2IRn:

2.1.2 Quelques rappels sur le calcul différentiel

On considère dans cette partiemetndeux nombres deN(très souvent dans ce cours on auram= 1).

1. SoitUun sous-ensemble deIRnetf:U7!IRm.

On dit quefestcontinueenx2Usif(x(k))!f(x)pour toute suitex(k)U telle quex(k)!x. On dit quefest continue surUsifest continue en tout pointx2U. Remarque :Sif= (f1;f2;fm)avecf1;f2;fm:U!IRalorsfest continu enx2Usi et seulement sif1;f2;fmsont continues enx.

Pour tous les poins suivants on va supposer que

est un ouvert de IRnetfest une fonctionf: !IRm. 6

2. Pour toutx2

eth2IRnon note (quand9) @f@h (x) = limt7!01t [f(x+th)f(x)] (c"est ladérivée directionnelledefenxdans la directionh).

Remarques :

i)@f@0(x) = 0: ii)Sif= (f1;f2;fn)T2IRnavecf1;f2;fm: !IRalors @f@h (x) =@f1@h (x);@f2@h (x);@fm@h (x) T

3. Pour toutx2

et touti2 f1;2;;ngon note (quand9) @f@x i(x) =@f@e i(x) = limt7!01t [f(x+tei)f(x)] (c"est ladérivée partielledefenxpar rapport à la variablexi.)

En particulier, sin= 1on notef0(x) =@f@x

1(x) = limt!01t

[f(x+t)f(x)] = lim y!x1yx[f(y)f(x)]

4. Pour toutx2

on note (quand9)Jf(x) =lamatrice Jacobiennedefenxqui est un élément deMm;n(IR)définie par (Jf(x))ij=@fi@x j(x)2IR8i= 1;m;8j= 1;n: Legradientdefenxest défini comme la transposée de la matrice Jacoblenne de fenx: rf(x) = (Jf(x))T2 Mn;m(IR): Remarque importante :Dans le cas particulierm= 1(doncf: !IR) alors en considérant tout élément deMn;1comme un vector colonne deIRn, on va dire que rf(x)est le vecteur colonne rf(x) =@f@x 1@f@x

2;@f@x

n T 2IRn:

Rappellons la formule :

@f@h (x) =8x2

8h2IRn:

5. Sif:

!IR(icim= 1) on dit qu"un pointx2 est unpoint critiquepour la fonctionfsirf(x) = 0. 7

6. Pour toutx2

eti;j2 f1;2;ngon note (quand9) 2f@x i@xj(x) =@@x i @f@x j (x)2IRm dérivée partielle à l"ordre 2.

Notation :pouri=jon écrira@2f@

2xi(x)à la place de@2f@x

i@xi(x).

7. Dans le casm= 1on note pour toutx2

(quand9)r2f(x) =la matrice carrée 2 M n(IR)donnée par r2f(x) ij=@2f@x i@xj(x);8i;j= 1;2;n: (r2f(x)s"appelle aussila matrice Hessiennedefenx).

8. On dit quefest de classeCpsur

(on noteraf2Cp( )) pourp= 1oup= 2 si les dérivées partielles desfjusqu"à l"ordrepexistent et sont continues sur . Par extension on dit quefest de classeC0sur sifest continue sur

9. On a le Théorème de Schwarz : sif2C2(

)alors 2f@x i@xj(x) =@2f@x j@xi(x)8x2 ;8i;j= 1;n (c"est à dire, la matricer2f(x)est symmétrique).

10. (Lien entrer;Jfetr2) : Sif:

!IRest de classeC2alors r

2f(x) =Jrf(x) =rJf(x)8x2

(la matrice Hessienne defest le Jacobien du gradient defou le gradient de la

Jacobienne def).

11. (Composition) Soient

IRn; UIRmavec

;Uouvertsf: !IRm; g:U! IR pavecp2INetf( )U. Considérons la fonction composéegf: !IRp. i)Sifetgsont continues alorsgfest continue. ii)Sifetgsont de classeC1alorsgfest de classeC1et on a l"égalité matricielle J gf(x) =Jg(f(x))Jf(x)8x2

Conséquences :

i)Sim=p= 1alors r(gf)(x) =g0(f(x))rf(x): i)Sin=p= 1alors (gf)0(x) = : 8quotesdbs_dbs33.pdfusesText_39

[PDF] optimisation quadratique sous contrainte linéaire

[PDF] optimisation convexe pdf

[PDF] fonction convexe plusieurs variables

[PDF] modélisation et simulation d'un moteur ? courant continu matlab

[PDF] modélisation mcc

[PDF] simulation mcc simulink

[PDF] asservissement et regulation de vitesse d'un moteur a courant continu

[PDF] modélisation d'un moteur ? courant continu

[PDF] equation differentielle moteur courant continu

[PDF] schéma bloc moteur ? courant continu

[PDF] commande pid d'un moteur ? courant continu pdf

[PDF] modélisation machine asynchrone simulink

[PDF] onduleur triphasé matlab

[PDF] cours de modélisation financière sous excel

[PDF] modélisation financière pdf

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

Comment montrer qu'une fonction est strictement convexe ?

Comment déterminer qu'une fonction est convexe ?

Comment montrer qu'une fonction est strictement concave ?

COURS OPTIMISATION

Cours en Master M1 SITN

Ionel Sorin CIUPERCA

Table des matières

1 Introduction 4

2 Quelques rappels de calcul différentiel, analyse convexe et extremum 5

2.1 Rappel calcul différentiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.1 Quelques Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

2.1.2 Quelques rappels sur le calcul différentiel . . . . . . . . . . . . . . . 6

2.1.3 Rappel formules de Taylor . . . . . . . . . . . . . . . . . . . . . . . 10

2.1.4 Quelque rappels sur le matrices carrées réelles . . . . . . . . . . . . 11

2.2 Convexité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

2.2.1 Fonctions convexes, strictement convexes, fortement convexes . . . . 11

2.2.2 Exemples des fonctions convexes, strictement convexes et fortement

2.2.3 Fonctions coercives . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.3 Conditions nécéssaires et suffisantes de minimum . . . . . . . . . . . . . . 17

2.4 Existence et unicité d"un point de minimum . . . . . . . . . . . . . . . . . 21

3 Optimisation sans contraintes 23

3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3.1.1 Description de la méthode . . . . . . . . . . . . . . . . . . . . . . . 24

3.1.2 Cas particulier des fonctions quadratiques . . . . . . . . . . . . . . 27

3.2 Méthodes de gradient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

3.2.1 Méthodes de gradient à pas optimal . . . . . . . . . . . . . . . . . . 29

3.2.2 Autres méthodes du type gradient . . . . . . . . . . . . . . . . . . . 30

3.3 La méthode des gradients conjugués . . . . . . . . . . . . . . . . . . . . . . 33

3.3.1 Le cas quadratique . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3.3.2 Cas d"une fonctionJquelconque . . . . . . . . . . . . . . . . . . . 38

4 Optimisation avec contraintes 39

4.1 Rappel sur les multiplicateurs de Lagrange . . . . . . . . . . . . . . . . . . 40

4.2 Optimisation sous contraintes d"inégalités . . . . . . . . . . . . . . . . . . . 41

4.2.1 Conditions d"optimalité de premier ordre : multiplicateurs de Karush-

4.2.2 Théorie générale du point selle . . . . . . . . . . . . . . . . . . . . . 49

4.2.3 Applications de la théorie du point selle à l"optimisation . . . . . . 51

4.2.4 Le cas convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3 Algorithmes de minimisation avec contraintes . . . . . . . . . . . . . . . . 53

4.3.1 Méthodes de relaxation . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.2 Méthodes de projection . . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.3 Méthodes de pénalisation exterieure . . . . . . . . . . . . . . . . . . 59

4.3.4 Méthode d"Uzawa . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

Chapitre 1

Introduction

1. Une fonctionJ:IRn7!IR(fonction coût)

2. Un ensembleUIRn(ensemble des contraintes)

J(x) = minx2UJ(x)

J(x)J(x);8x2U:

Motivation et exemples pratiques :en classe

Chapitre 2

Quelques rappels de calcul différentiel,

2.1 Rappel calcul différentiel

2.1.1 Quelques Notations

1. Pour toutn2IN;IRndésigne l"espaceeuclidienIRIRIR( "produitnfois").

2. On notee1;e2;enles éléments de labase canoniquedeIRn, oùeiest le vecteur

1sij=i;8i;j= 1;2n(2.1)

3. Pour tousx;y2IRnon note par< x;y >2IRleproduit scalairedexety, qui

4. Pour toutx2IRnon note parkxk 0lanorme euclidiennedex, donnée par

5. Pour tousx2IRnetr >0on notera parB(x;r)laboule ouvertedu centrexet

B(x;r) =fy2IRn;kyxk< rg:

7. SoitUIRn.

8. Sia;b2IRnon note[a;b]le sous-ensemble deIRndonné par

Remarques :

9. Rappellons aussi l"inégalité de Cauchy-Schwarz :

2.1.2 Quelques rappels sur le calcul différentiel

1. SoitUun sous-ensemble deIRnetf:U7!IRm.

Pour tous les poins suivants on va supposer que

2. Pour toutx2

Remarques :

3. Pour toutx2

En particulier, sin= 1on notef0(x) =@f@x

1(x) = limt!01t

4. Pour toutx2

2;@f@x

Rappellons la formule :

8h2IRn:

5. Sif:

6. Pour toutx2

Notation :pouri=jon écrira@2f@