Vous êtes ici : UVSQ RechercheDoctoratSoutenances de thèse

Conditions d’optimalité en optimisation globale : Contributions à l’optimisation combinatoire

Par Monsieur Ider TSEVEENDORJ Discipline : MATHEMATIQUES APPLIQUEES/ INFORMATIQUE

La présente thèse est consacrée aux conditions d'optimalité globale pour des problèmes  nonconvexes et aux algorithmes numériques d'amélioration de solutions locales. A cet effet, les trois problèmes non-convexes:  maximisation convexe, reverse convexe et  maximisation convexe par morceaux sont étudiés. Les résultats numéiques obtenus sur les problèmes d'optimisation combinatoire du sac à dos multiple (multiknapsack) et de la  clique maximale confirment l'approche continue proposée, comme très prometteuse. Par ailleurs, les problèmes de l'affectation de trafic sur réseau routier et de la tarification dans les réseaux de  télécommunications ont été modélisés respectivement comme inégalité variationnelle non-monotone et la programmation mathématique sous contrainte d'équilibre; pour ces deux applications non convexes, une approche convexe par morceaux peut également fournir des solutions stationnaires. En conclusion, l'auteur affiche sa confiance dans l'approche convexe par morceaux pour les problèmes non convexes, en tant qu'évolution logique naturelle de l'approche affine par morceaux dans l'optimisation convexe.

Abstract : The present thesis deals with global optimality conditions for nonconvex optimization problems and numerical algorithms for solving them. For this purpose, convex maximization, reverse convex and piecewise convex maximization among the classes of nonconvex problems, are considered. Computational results given  on combinatorial optimization problems like multiknapsack, the maximum clique problems make the proposed continuous optimization algorithms very promising. From applications side, traffic assignment on transportation networks and pricing  in telecommunications have been formulated as nonmonotone variational inequality and mathematical programming with equilibrium constraint respectively; interestingly, for both cases, piecewise convex approach may lead to stationary solutions. To conclude, the  author  trusts  in the piecewise convex approach  for  nonconvex problems as a natural and logical continuation of piecewise affine approximation in convex optimization.

Informations complémentaires

Panos PARDALOS, Professeur des Universités  à l'Université de Floride (USA) -Rapporteur Tao PHAM DINH, Professeur des Universités l'Institut National des Sciences Appliquées de Rouen - INSA - Rapporteur Alexander STREKALOVSKY, Professeur et Directeur « of Departement of System Analysis and Optimization (Russie) - Rapporteur Catherine ROUCAIROL, Professeur des Universités à l'Université de Versailles Saint-Quentin-en-Yvelines  - Examinateur Arnaud FREVILLE, Professeur des Universités à l'Université de Valencienne - Examinateur Dominique FORTIN, Chargé de recherche INRIA de Rocquencourt - Examinateur Thierry MAUTOR, Maître de Conférences à l'Université de Versailles Saint-Quentin-en-Yvelines - Examinateur Olivier HUDRY, Professeur ENST Paris - Examinateur An LE THI HOAI, Professeur des Universités à l'Université de Paul Verlaine Metz - Examinateur