Optimisation Globale basée sur l'Analyse d'Intervalles : relaxation Affine et Limitation de la Mémoire, Global Optimization based on Interval Analysis : affine Relaxation and Limited Memory

Jordan Ninin

Description

Sous la direction de Frédéric Messine
Thèse soutenue le 08 décembre 2010: INPT
Depuis une vingtaine d’années, la résolution de problèmes d’optimisation globale 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 limite 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, afin de 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 construction 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 COCONUT 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’algorithmes 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, pour finir l’étude, nous avons appliqué notre algorithme à la résolution de problème en géométrie plane, ainsi qu’à la résolution d’un problème de dimensionnement de moteur électrique. Les résultats obtenus ont permis de confirmer l’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.
-Recherche Opérationnelle
-Optimisation Globale
-Branch and Bound
-Analyse d’Intervalles
-Arithmétique Affine
-Calcul Robuste
-Relaxation Linéaire
Since about thirty years, interval Branch and Bound algorithms are increasingly used to solve constrained global optimization problems in a deterministic way. Such algorithms are reliable, i.e., they provide an optimal solution and its value with guaranteed bounds on the error, or a proof that the problem under study is infeasible. Other approaches to global optimization, while useful and often less time-consuming than interval methods, do not provide such a guarantee. However, the exponential complexity in time and memory of interval Branch and Bound algorithms implies a limitation, so it is always necessary to improve these methods. In this thesis, we have developed new arithmetics based on interval arithmetic and affine arithmetic, to compute better lower and upper bounds of a factorable function over an interval. An automatic method for constructing linear relaxations of constrained global optimization problems is proposed. Such a construction is based on affine and interval arithmetics and uses operator overloading. These linear programs have exactly the same numbers of variables and of inequality constraints as the given problems. Each equality constraint is replaced by two inequalities. This new procedure for computing reliable bounds and certificates of infeasibility is inserted into a classical interval Branch and Bound algorithm. Extensive computation experiments, made on a sample of test problems from the COCONUT database, prove its effectiveness. Another aspect is the study of an extension of such a global optimization code by limiting the available memory. The main idea of this new kind of metaheuristique is to propose a reverse process of optimization via heuristics : rather than improving local solutions by using metaheuristics such as Taboo or VNS, we begin with an exact method and we modify it into a heuristic one. In such a way, the quality of the solution could be evaluated. Moreover, a study of the complexity of this metaheurisque has been done. Finally, we applied our algorithm to solve open problem in geometry, and to solve a design problem of an electric motor. The results have confirmed the usefulness of this kind of algorithms, solving open problems on convex polygons and offering innovative structures in electrical engineering.
-Operations Research
-Global Optimization
-Branch and Bound
-Nterval Analysis
-Affine Arithmetic
-Reliable Computation
-Linear Relaxation
Source: http://www.theses.fr/2010INPT0090/document

Sujets

• Recherche opérationnelle
• Séparation et évaluation

Informations

• Publié par: Thesee
• Nombre de lectures: 34
• 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