[PDF] [PDF] th`ese de doctorat es sciences - UMMTO

View - Download [PDF] th`ese de doctorat es sciences - UMMTO

Previous PDF

Next PDF

R´epublique Alg´erienne D´emocratique et Populaire Minist`ere de l'Enseignement Sup´erieur et de la Recherche Scientifique

Universit´e Mouloud Maameri de Tizi-Ouzou

Facult´e des Sciences

D´epartement de Math´ematiques

TH ESE DE DOC TO RAT ES

SCIENCES

SP

´ECIALISTE : Math´ematiques

Option : Recherche Op´erationnelle et Optimisation

Pr´esent´ee par :

Mr CHEBBAH MOHAMMED

Sujet dddddddddR

ESOLUTIONS ET

IMPLEMENTATIONS DE PROBLEMES

EN

OPTIMISATION GLOBALE.e

eeeeeeee

Soutenue le : 07/07/2020.

Devant la commission d'examen compos´ee de :

HAMADOUCHE DJAMAL ProfesseurU.M.M.T.O Pr´esident

OUANES MOHANDProfesseurU.M.M.T.ORapporteur

MOULAI MUSTAPHA ProfesseurU.S.T.H.BExaminateur

BOUROUBI SADEK ProfesseurU.S.T.H.BExaminateur

AIDER MEZIANEProfesseurU.S.T.H.BExaminateur.

>Remerciements> Avant tout, je remercie Dieu de m'avoir donne le courage et la foie pour mener a bien ce travail, malgre tous les obstacles.

Mes vifs et sinceres remerciements vont a M

rOUANES Mohand (professeur a UMMTO) qui, en acceptant de diriger ce travail, m'a permis de proter de ses conseils, son aide et ses encouragements, je lui temoigne ma respectueuse gratitude. Mes sinceres remerciements s'adressent egalement aux membres du jury pour avoir accepte d'examiner ce travail. En l'occurrence le professeur Hamadouche Djamal de l'UMMTO, les professeurs Moulai Mustapha, Bouroubi Sadek et Aider Meziane de l'USTHB.Je tiens egalement a remercier tous ceux qui ont contribue de pres ou de loin a la realisation et la reussite de ce travail.

Merci beaucoup.

>Dedicaces> C'est avec un enorme plaisir que je dedie ce travail : Aux deux personnes les plus nobles et les plus cheres au monde : Mon defunt Pere et ma Mere qui ont sacrie les plus belles annees de leurs vies pour me voir un jour reussir, et qui m'ont soutenu jusqu'a la n.

A mes freres et soeurs qui n'ont jamais

cesse de m'encourager.

A mes chers granfs parents.

A toute ma famille.

A ma femme et mes enfants Rayan, Khadidja et Marya. A mon directeur de these qui m'a vraiment ete d'un grand soutien.

A mes tres chers amis et camarades.

A tous ceux qui m'ont soutenu de pres ou de loin.

MOHAMMED.

Table des mati`eres

Table des mati`eres

i

Table des figures

iv

Introduction g´en´erale

1

1 Convexit´e et Analyses Convexes

4

1.1 Introduction

4

1.2 Propri´et´es sur la convexit´e

5

1.2.1 Ensembles convexes

5

1.2.2 Propri´et´es des ensembles convexes

6

1.2.3 Polytopes et poly`edres convexes

6

1.3 Enveloppe convexe

7

1.4 Enveloppe affine

7

1.5 Enveloppe conique

7

1.6 Les fonctions convexes

8

1.6.1 Crit`eres de Sylvester

11

1.6.2 Exemple

12

2 Optimisation et Th´eories

14

2.1 Classification des programmes math´ematiques

15

2.1.1 Les programmes lin´eaires (la programmation lin´eaire) [

16 17 16

2.1.2 M´ethodes de r´esolution en programmation lin´eaire [

100
81
16 34
17 16

2.1.3 Exemple Illustratif de la programmation lin´eaire non diff´erentiable

19

2.1.4 Exemple Illustratif (Impl´ementation) de la programmation lin´eaire

19

2.1.5 La programmation quadratique

24

2.1.6 Les programmes non lin´eaires (la programmation non lin´eaire) [

11 32

2.1.7 La programmation convexe [

17 34
22
81
12 9 83
41

2.1.8 La dualit´e en programmation convexe [

17 34
22
81
45

2.1.9 La dualit´e en programmation math´ematique non convexe [

17 34
81
48
i

3 Optimisation Globale et Contribution `a l'Optimisation Globale50

3.0.10 Introduction : L'optimisation globale [

78
86
50

3.0.11 Domaines d'application de l'optimisation globale [

34
16 50

3.0.12 Les techniques d'optimisation dansR[

34
16 17 51

3.1 Probl`emes pratiques en optimisation globale

56

3.2 Exemple

60

3.3 M´ethodes de r´esolution en optimisation globale [

68
101
95
57
63
71

3.5 Background

72

3.5.1 Programmation factorable, am´elioration (relaxation)

72

3.5.2 La fonction borne inf´erieure dans la m´ethodeαBB [

11 74

3.5.3 La fonction quadratique borne inf´erieure [

51
74

3.6 La nouvelle fonction borne inf´erieure

75

3.6.1 Test convexit´e/concavit´e

76

3.6.2 Pruning method

76

3.7 L'algorithme de Branch and Bound et sa convergence

78

3.7.1 Convergence

80

3.8 R´esultats des calculs num´eriques

81

3.9 Conclusion

85

3.10 Perspectives

86
98

3.11.1 Motivations quant `a l'utilisation de l'optimisation globale unidimensionnelle

99

3.11.2 La borne inf´erieure dans la m´ethodeαBB [

11 100

3.11.3 La borne inf´erieure quadratique [

51
100

3.12 Nouvelle fonction borne inf´erieure

101

3.12.1 Test convexit´e/concavit´e

103

3.13 Algorithme et sa convergence

104

3.13.1 Algorithme

104

3.13.2 Convergence

105

3.14 R´esultats num´eriques

105

3.15 Conclusion

106

4 Optimisation de syst`emes dynamiques en contrˆole optimal.

115

4.1 Introduction

115

4.2 Le cas discret

116

4.2.1 Position du probl`eme

116

4.2.2 Notion de commandabilit´e

118

4.2.3 Accroissement de la fonctionnelle, crit`ere d'optimalit´e et de suboptimalit´e.

119

4.2.4 Crit`ere de suboptimalit´e

120

4.2.5 M´ethode de r´esolution

120
ii iii

4.2.6 Exemple. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .120

4.3 Le cas continu [

8 98
48
72
23
87
76
123

4.3.1 Position du probl`eme

123

4.3.2 D´efinitions

123

4.3.3 Support et support-contrˆole

124

4.3.4 Accroissement de la fonctionnelle et crit`eres d'optimalit´e et suboptimalit´e.

125

4.3.5 Th´eor`eme (crit`ere d'optimalit´e)

125

4.3.6 Th´eor`eme (crit`ere de sub-optimalit´e)

125

4.3.7 M´ethode de r´esolution

126

4.3.8 Changement du contrˆole

126

4.3.9 Changement du support

127

4.3.10 Proc´edure finale

129

4.3.11 Conclusions et perspectives

130

4.3.12 Exemple

130

4.3.13 Exemple

130

4.3.14 Exemple

131

4.4 Conclusion

135

Conclusion g´en´erale

136
A G´en´eralit´es sur les fonctions `a plusieurs variables 138

A.1 Introduction

138
A.2 G´en´eralit´es sur les fonctions `a plusieurs variables et topologie. [ 16 34
38
39
70
138
A.2.1

´El´ements de la topologie

138

A.2.2 Les espaces norm´es

139

A.2.3 Les espaces m´etriques

140
A.2.4

´El´ements de topologies surRn

140

A.2.5 Les fonctions surRnet th´eories

141

A.2.6 Limites et continuit´e

141
A.2.7 D´eriv´ees partielles et directionnelles 141

A.2.8 Diff´erentiabilit´e des fonctions

142

A.2.9 Matrice jacobienne

142

A.2.10 Formule de Taylor

143

A.2.11 Points critiques et extremas

144

Bibliographie

146

Table des figures

1.1 Ensembles convexes et ensembles non convexes.

5

1.2 Repr´esentation fonctionfconvexe.

9

1.3 Repr´esentation ´epigraphefconvexe.

9

3.1 Trajectoires et commandes optimales avec la m´ethode indirecte.

61

3.2 Trajectoires et commandes optimales avec la m´ethode directe.

62

3.3 Trajectoires optimales.

62
iv

Introduction generale

L'optimisation globale est de nos jours un sujet d'actualit´e par excellence, elle est une branche

des math´ematiques appliqu´ees et de l'analyse num´erique qui exhibe les minimas ou maximas

globaux d'une fonction ou d'un ensemble de fonctions sur un ensemble donn´e avec multiplicit´e.

Cette discipline partie int´egrante de la recherche op´erationnelle.

La recherche op´erationnelle (R.O) [

100
81
17 ] peut ˆetre d´efinie comme l'ensemble des m´ethodes et

techniques rationnelles orient´ees vers la recherche du meilleur choix dans la fa¸con d'op´erer en vue

d'aboutir au r´esultat vis´e ou au meilleur r´esultat possible. Elle fait partie des ≪aides `a la d´ecision . Dans la mesure o`u elle propose des mod`eles conceptuels en vue d'analyser et de maˆıtriser des situations complexes pour permettre aux d´ecideurs de comprendre, d'´evaluer les enjeux et d'arbitrer ou de faire les choix les plus efficaces. Ce domaine fait largement appel au raisonnement

math´ematique (logique, probabilit´es, analyse des donn´ees,...etc.) et `a la mod´elisation des processus.

Il est fortement li´e `a l'ing´enierie des syst`emes, ainsi qu'au management du syst`eme d'information

entre autres.

L'optimisation [

100
81
17 16 34
] est une branche des math´ematiques (branche de la recherche

op´erationnelle) cherchant `a mod´eliser, `a analyser et `a r´esoudre analytiquement ou num´eriquement

les probl`emes qui consistent `a minimiser ou maximiser par exemple une fonction sur un ensemble 98
72
87
23
8 62
]. L'optimisation joue un rˆole important en recherche op´erationnelle (domaine

`a la fronti`ere entre l'informatique, les math´ematiques et l'´economie). L'optimisation est dans les

math´ematiques appliqu´ees (fondamentales pour l'industrie et l'ing´enierie), en analyse et en analyse

num´erique, en statistique pour l'estimation du maximum de vraisemblance d'une distribution, pour

la recherche de strat´egies dans le cadre de la th´eorie des jeux, ou encore en th´eorie du contrˆole et

de la commande. Beaucoup de syst`emes susceptibles d'ˆetre d´ecrits par un mod`ele math´ematique

sont optimis´es. La qualit´e des r´esultats et des pr´edictions d´epend de la pertinence du mod`ele, de

l'efficacit´e de l'algorithme et des moyens pour le traitement num´erique. L'optimisation globale a connu de nos jours, une avanc´ee fulgurante en ce sens que beaucoup de papiers ont vu le jour dans ce contexte. Il n' y a pas si longtemps que ce domaine (l'optimisation

globale) ´etait `a peine connu, d'ailleurs on peinait `a trouver la meilleure solution dans le cadre

de l'optimisation (programmation math´ematique) en g´en´eral. Donc pour chercher des solutions,

les m´ethodes ´etaient le lagrangien augment´e, la m´ethode SQP, m´ethodes type Newton avec ses

variantes, gradient r´eduit,...etc. Alors que la recherche de la multiplicit´e des solutions optimales

paraissaient utopiques en g´en´eral, cela occasionnant en outre des apports consid´erables en res-

sources (temps d'ex´ecution, quantit´e de m´emoires utilis´ees). 1 2 L'optimisation globale dans ce sens a ramen´e un nouveau souffle, de nouvelles orientations et

surtout de nouvelles m´ethodes et a permis en mˆeme temps de r´esoudre les probl`emes li´es `a l'opti-

misation cit´ee plus haut. Les travaux de l'´equipe de PHAM DINH Tao et LE THI Hoai An (Metz France) [ 101
], celle de Floudas (USA) [ 51
], celle de Fr´ed´eric Messine et Jordan Ninin (Toulouse France) [ 78
86
quotesdbs_dbs29.pdfusesText_35

[PDF] Exercices de gestion des ressources humaines-2 - Numilog

[PDF] Mecanique quantique Cours et exercices corriges - Numilog

[PDF] Correction de l 'examen de probabilités et statistiques - Julian Tugaut

[PDF] Examen final corrigé (janvier 2013)

[PDF] Série d 'exercices Finance Internationale - ResearchGate

[PDF] Cours de gestion financière (M1) Exercices corrigés Le cas

[PDF] Exercice n°1

[PDF] Réseaux de Petri

[PDF] Examen professionnel Informatique, système d 'information

[PDF] Graphes exercices et correction

[PDF] Correction examen théorie des jeux 2009-2010 - Ceremade

[PDF] Exercice n° HU 0601 - Corrigé

[PDF] 10

[PDF] 14

[PDF] Examen d analyse personnel technique (ANT) - carrieres gouv