Accueil > Manifestations > Thèses et HDR > Thèses > Benjamin Martin

Benjamin Martin

Directeur de thèse

Laurent Granvilliers
Alexandre Goldsztjen
Christophe Jermann

Résumé

L’Optimisation de critères nonlinéaires contradictoires, sous contraintes nonlinéaires, apparaît dans de nombreux problèmes, par exemple en ingénierie ou dans des problèmes de localisation. La résolution d’un problème avec m objectifs nécessite de calculer son ensemble de solutions dites Pareto optimales, formant des variétés continues de dimensions m-1 potentiellement morcelées en plusieurs parties disjointes. Dans cette thèse, nous nous intéressons aux algorithmes rigoureux, i.e. donnant des garanties de résultats, basés sur l’analyse par intervalle pour la résolution de problèmes biobjectifs. Nous proposons une méthode de continuation certifiée qui trace localement les variétés continues de solutions optimales. Cette méthode améliore d’autres techniques similaires de la littérature en proposant une meilleure adaptation à la forme de la variété tracée, ainsi que la prise en compte des contraintes d’inégalités du problème sources de singularités. De plus, nous proposons un algorithme de Branch & Bound (B&B) qui calcule globalement un encadrement vérifié des solutions optimales. Cette méthode intègre des techniques de propagation de contraintes, exploitant notamment les bornes sur les objectifs, afin
d’accélérer la résolution. Elle généralise également d’autres approches similaires de la littérature. Enfin, nous discutons la perspective de coupler ces deux méthodes. Une telle approche est prometteuse dans la mesure où le B&B converge globalement mais lentement. Ceci est dû aux efforts nécessaire pour couvrir totalement les variétés de solutions, tandis que la continuation est une méthode efficace, mais locale, pour effectuer ce travail.

Mots-clés : Optimisation nonlinéaire biobjectif, Analyse par intervalle, Satisfaction de contraintes numériques, Méthodes de continuation, Branch & Bound

Composition du jury :

  • R. Baker Kearfott, University of Louisianna at Lafayette, Rapporteur
  • Luc Jaulin, ENSTA Bretagne, Rapporteur
  • Michel Rueher, Université de Nice Sophia-Antipolis, Examinateur
  • Laurent Granvilliers, Université de Nantes, Directeur de thèse
  • Alexandre Goldsztejn, CNRS, Co-encadrant
  • Christophe Jermann, Université de Nantes, Co-encadrant

Abstract :

Many problems, such as in engineering design or in location problems, require the optimization of several conflicting nonlinear objectives subject to nonlinear constraints. Solving a multiobjective problem involving m objectives implies computing its set of Pareto-optimal solutions, that are in general m-1 dimensional manifolds possibly made of
several disjoint connected components. In this thesis, we are interested in interval-based rigorous algorithms, i.e. with guaranteed results, to solve biobjective problems. We propose a certified continuation method that tracks locally a connected manifold of optimal solutions. This method supplements other techniques from the literature as it adapts finely to the shape of manifolds and deals with singularities resulting from inequality constraints in biobjective problems. We also propose an interval Branch & Bound (B&B) algorithm that globally computes a verified enclosure of the optimal solutions. This method integrates constraint propagation techniques, noticeably exploiting bounds on the objectives, in
order to enhance the solving process. It also generalizes other similar approaches from the literature. Eventually, we discuss the perspective of coupling the two techniques. Such an hybrid approach is promising as the B&B converges globally, but slowly. It indeed spends many efforts for covering the manifold of solutions, whereas the continuation is an
efficient, but local, technique for building such covering.

Keywords : Biobjective nonlinear optimization, Interval analysis,
Numerical constraint satisfaction, Continuation methods, Branch & Bound

Dernière modification : mercredi 22 octobre 2014