La lecture à portée de main
Découvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDécouvre YouScribe en t'inscrivant gratuitement
Je m'inscrisDescription
Sujets
Informations
Publié par | Thesee |
Nombre de lectures | 26 |
Langue | Français |
Poids de l'ouvrage | 1 Mo |
Extrait
!!"#$%&!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!&'!()*!+*!,-./0*'01.'!+)
234"356"!2&2&!!789:;;<<&&5%5%;;"="=!!2&2&!!"39739%"39739%&&
2>,1(?>!@A?!"#$%&'(')'!*+'(,%+"!-,".'/01%(2)/!3/!4,)",)&/
21BC1@,1'*!.)!B@>C1A,10>!D!Sûreté de logiciel et calcul à haute performance
-68&/%'8/!/'!&,)'/%)/!9+6!
E3526:!:;:;:
:/!;!380/7<6/!=>?>
3@01F1BA01.'!G,./A,*!/AB>*
B)?!,-6'A,HB*!+-;'0*?(A,,*B
5*,AIA01.'!6JJ1'*!*0!71F10A01.'!+*!,A!K>F.1?*
=C.,*!+.C0.?A,*
@+'187+'(2)/&A!$%5,67+'(2)/A!48"80,77)%(0+'(,%&!3/!4,)",)&/!B@$44C
9'10>!+*!?*CL*?CL*!
$%&'(')'!3/!D/01/601/!/%!$%5,67+'(2)/!3/!4,)",)&/!B$D$4C
21?*C0*)?!+*!0LMB*
N?>+>?1C!K&%%;:& @+E'6/!3/!F,%586/%0/!GHD! $*-!I!J*KJJ$G4
5A@@.?0*)?B!
5A,@L!OAP*?!Q&65N3""! -6,5/&&/)6!3#L%(M/6&('8 L%(M/6&('.!,5!:,)(&(+%+!+' !:+5+./''/
7*.!7;O&5";! -6,5/&&/)6!3#L%(M/6&('8! N0,"/!-,".'/01%(2)/ de Palaiseau
&IAF1'A0*)?B
7A)?*'0 !G56:<;77;&5% -6,5/&&/)6!3#L%(M/6&('8! L%(M/6&('8!3/!*+%'/&
R1*??*!#6:%&:! -6,5/&&/)6!3#L%(M/6&('8! GJF!@,%'68+"
21+1*?!#&:5;3:!! H(6/0'/)6!3/!D/01/601/ :OOKIF*DK
KA?C*,!K3:G&69 @+E'6/!3/!F,%586/%0/!GHD L%(M/6&('8!-+)"!K+<+'(/6Remerciements
Que de chemin parcouru, que de gens passionnants rencontrés, que de lieux
magnifiques visités et d’expériences enrichissantes partagées depuis le début de ce
travail. Cette thèse est certes personnelle, mais elle n’aurait jamais été possible sans
l’aide et le soutien de toutes les personnes qui m’ont entouré.
Tout d’abord, je tiens à remercier Frédéric Messine pour son encadrement, sa
gentillesse et son amitié. Merci pour les centaines de litres de café bu tout en discu-
tant de recherche durant des centaines d’heures. C’est grâce à cette rencontre que
j’ai su que je voulais faire de la recherche. Il a su me faire profiter de toute son
expérience et de son savoir avec générosité et m’a appris les rudiments de ce pas-
sionnant métier de chercheur. J’ai eu grand plaisir à travailler à ses côtés et j’espère
poursuivre ma carrière dans le même genre d’ambiance.
Merci à Pierre Hansen d’avoir accepté de présider mon jury de thèse et surtout
pourm’avoirfaitconfiancedèsledébutdemonMaster.Sonexpérience,sonérudition
et sa sagesse m’ont permis de progresser grandement. Et chacune de nos rencontres
a été pour moi extrêmement enrichissante.
Merci àLeo Libertid’avoir accepté d’être rapporteur de mathèse et pourles dis-
cussions, toujours fructueuses, que nous avons eues. Son dynamisme et sa confiance
m’ont toujours poussé à échanger et à communiquer davantage sur mes idées aux
quatre coins du monde.
Je tiens également à remercier Ralph Baker Kearfott pour avoir accepté d’être
rapporteur de ma thèse, et d’avoir fait le déplacement pour la soutenance. Et je suis
certain que de cette première rencontre débutera une collaboration fructueuse.
Merci encore à Laurent Granvilliers, Didier Henrion et Marcel Mongeau d’avoir
accepté de faire partie de mon jury de thèse. Merci également pour vos conseils et
vos remarques qui m’ont permis d’améliorer et de clarifier mon travail. Et j’ai hâte
de pouvoir continuer à travailler avec vous.
Merci à tous les membres de l’équipe APO qui m’ont accueilli au sein de l’IRIT.
Merci à mes deux coreligionnaires Olivier et Sandrine pour leur soutien et les cen-
taines d’heures passées ensemble dans ce bureau avec une fenêtre donnant sur une
fenêtre donnant elle-même sur un mur, à la recherche d’une lueur de soleil et d’un
peu d’air frais. Merci à toute l’équipe GREM3du LAPLACE pour l’accueil toujours
chaleureux qui m’a été fait et les applications toujours étonnantes et surprenantes
sur lesquelles ils m’ont proposé de travailler.
– i –Jetienségalement àremercier tousmesamis, Olivier,Laetitia,lesamisduV&B,
les anciens de TVn7, les amis du groupe nano, les copains de Reims, et tous ceux
avec qui j’ai passé des moments inoubliables.
Merci à mes parents, mon frère et mes grands-parents pour la confiance sans
faille qu’ils me témoignent, pour les encouragements à aller toujours plus loin et
pour cette curiosité et cette soif d’apprendre qu’ils ont su m’inculquer.
Enfin, il est impossible pour moi de passer sous silence l’influence positive qu’a
eue pour moi Laurène, avec qui je partage chaque instant depuis trois ans. Son
amour a été pour moi une source inépuisable d’énergie, de force et de stabilité. Son
point de vue a toujours été essentiel et m’a permis de rendre mon travail plus lisible
et mieux construit. Elle n’imagine pas à quel point son aide a été précieuse pour
moi. J’espère simplement pouvoir un jour lui rendre autant qu’elle m’a donné et
continue de me donner.
– ii –Résumé
Depuis une vingtaine d’années, la résolution de problèmes d’optimisation glo-
bale non convexes avec contraintes a connu un formidable essor. Les algorithmes
de branch and bound basée sur l’analyse d’intervalles ont su trouver leur place, car
ils ont l’avantage de prouver l’optimalité de la solution de façon déterministe, avec
un niveau de certitude pouvant aller jusqu’à la précision machine. Cependant, la
complexité exponentielle en temps et en mémoire de ces algorithmes induit une li-
mite intrinsèque, c’est pourquoi il est toujours nécessaire d’améliorer les techniques
actuelles.
• Dans cette thèse, nous avons développé de nouvelles arithmétiques basées sur
l’arithmétique d’intervalles et l’arithmétique affine, afinde calculer des minorants et
des majorants de meilleure qualité de fonctions explicites sur un intervalle.
• Nous avons ensuite développé une nouvelle méthode automatique de construc-
tion de relaxations linéaires. Cette construction est basée sur l’arithmétique affine
et procède par surcharge des opérateurs. Les programmes linéaires ainsi générés
ont exactement le même nombre de variables et de contraintes d’inégalité que les
problèmes originaux, les contraintes d’égalité étant remplacées par deux inégalités.
Cette nouvelle procédure permet de calculer des minorants fiables et des certificats
d’infaisabilité pour chaque sous-domaine à chaque itération de notre algorithme de
branch and bound par intervalles. De nombreux tests numériques issus du site CO-
CONUT viennent confirmer l’efficacité de cette approche.
• Un autre aspect de cette thèse a été l’étude d’une extension de ce type d’al-
gorithmes en introduisant une limite sur mémoire disponible. L’idée principale de
cette approche est de proposer un processus inverse de l’optimisation par le biais
d’un principe métaheuristique : plutôt que d’améliorer des solutions locales à l’aide
de métaheuristiques telles que les algorithmes Taboo ou VNS, nous partons d’une
méthode exacte et nous la modifions en une heuristique. De cette façon, la qualité
de la solution trouvée peut être évaluée. Une étude de la complexité de ce principe
métaheuristique a également été effectuée.
•Enfin,pourfinirl’étude,nousavonsappliquénotrealgorithmeàlarésolutionde
problème engéométrieplane, ainsiqu’àlarésolutiond’unproblème dedimensionne-
mentdemoteurélectrique. Lesrésultatsobtenusontpermisdeconfirmerl’intérêt de
ce type d’algorithme, en résolvant des problèmes ouverts sur les polygones convexes
et proposant des structures innovantes en génie électrique.
– iii –MotsClés:RechercheOpérationnelle,OptimisationGlobale,BranchandBound,
Analyse d’Intervalles, Arithmétique Affine, Calcul Robuste, Relaxation Linéaire.
– iv –Abstract
Since about thirty years, interval Branch and Bound algorithms are increasingly
used to solve constrained global optimization problems in a deterministic way. Such
al