Thèse de doctorat : Mathématiques : Nice : 2004. / Thèse préparée à l'Inria Sophia Antipolis, projet Ariana. Bibliogr. p. 261-269.

Depuis son introduction, la programmation mathématique à deux niveaux suscite un intérêt toujours croissant. En effet, vu ses applications dans une multitude de problèmes concrets (problèmes de gestion, planification économique, chimie, sciences environnementales,...), beaucoup de recherches ont été effectuées afin de contribuer à la résolution de cette classe de problèmes. Cette thèse est consacrée à l'étude de quelques classes de problèmes d'optimisation à deux niveaux, à savoir, les problèmes à deux niveaux forts, les problèmes à deux niveaux forts-faibles et les problèmes à deux niveaux semi-vectoriels. Le premier chapitre est consacré aux rappels de quelques définitions et résultats de topologie et d'analyse convexe que nous avons utilisé dans la suite. Dans le deuxième chapitre, nous avons rappelé quelques résultats théoriques et algorithmiques établis dans la littérature pour la résolution de quelques classes de problèmes d'optimisation à deux niveaux. Le troisième chapitre est consacré à l'étude d'un problème à deux niveaux fort-faible (SWBL). Vu la difficulté que présente cette classe de problèmes dans l'étude de l'existence de solutions, et afin de donner de nouvelles perspectives à leur résolution, nous avons procédé à une régularisation du problème. Sous des conditions suffisantes et via cette régularisation, nous avons montré que le problème (SWBL) admet au moins une solution. Dans le quatrième chapitre, nous avons donné une approche de dualité à un problème d'optimisation à deux niveaux fort (S). Cette approche est basée sur l'utilisation d'une régularisation et la dualité de Fenchel-Lagrange. En utilisant cette approche, nous avons donné des conditions nécessaires d'optimalité pour le problème (S). Enfin, des conditions suffisantes d'optimalité sont obtenues pour (S) sans utiliser l'approche. Une application concrète est donnée sur l'allocation de ressources. Dans le cinquième chapitre, nous avons étudié un problème à deux niveaux semi-vectoriel (SVBL). Pour ce problème, nous avons donné une approche de dualité en utilisant une régularisation, une scalarisation et la dualité de Fenchel-Lagrange. Puis, via cette approche et sous des hypothèses appropriées, nous avons donné des conditions nécessaires d'optimalité pour une classe de solutions du problème (SVBL). Finalement, des conditions suffisantes d'optimalité sont établies sont établies sans utiliser l'approche de dualité. / Since its introduction, the class of tao-level programming problems has attracted increasing interest. Indeed, because of its applications in a multitude of concrete problems (management problems, economic planning, chemistry, environmental sciences,...), several researchers have been interested in the study of such class of problems. This thesis deals with the study of some classes of two-level optimization problems, namely, strong two-level problems, strong-weak two-level problems and semi-vectorial two-level problems. In the first chapter, we have recalled some definitions and results related to topology and convex analysis that we have used in our study. In the second chapter, we have discussed some theoretical and algorithmic results established in the literature for solving some classes of two-level optimization problems. The third chapter deals with strong-weak Stackelberg problems. As it is well-known, such a class of problems presents difficulties in its study concerning the existence of solutions. So that, for a strong-weak two-level optimization problem, we have first given a regularization. Then, via this regularization and under appropriate assumptions we have shown the existence of solutions to such a problem. This result generalizes the one given in the literature for weak Stackelberg problems. In the fourth chapter, we have given a duality approach for a strong two-level programming problem (S). The duality approach is based on the use of a regularization and the Fenchel-Lagrange duality. Then, via this approach, we have given necessary optimality conditions for (S). Finally, sufficient optimality conditions are given for the initial problem (S). An application to a two-level resource allocation problem is given. In the fifth chapter, we have considered a semivectorial two-level programming problem (SVBL) where the upper and lower levels are vectorial and scalar respectively. For such a problem, we have given a duality approach based on the use of a regularization, a scalarization and the Fenchel-Lagrange duality. Then, via this approach we have established necessary optimality conditions for (SVBL). Finally, we have given sufficient optimality conditions without using the duality approach.

Cette thèse est consacrée à la résolution de problèmes d'analyse non linéaire multivoque dans lesquels plusieurs variables interagissent. Le problème générique est modélisé par une inclusion vis-à-vis d'une somme d'opérateurs monotones sur un espace hilbertien produit. Notre objectif est de concevoir des nouveaux algorithmes pour résoudre ce problème sous divers jeux d'hypothèses sur les opérateurs impliqués et d'étudier le comportement asymptotique des méthodes élaborées. Une propriété commune aux algorithmes est le fait qu'ils procèdent par éclatement en ceci que les opérateurs monotones et, le cas échéant, les opérateurs linéaires constitutifs du modèle agissent indépendamment au sein de chaque itération. Nous abordons en particulier le cas où les opérateurs monotones sont des sous-différentiels de fonctions convexes, ce qui débouche sur de nouveaux algorithmes de minimisation. Les méthodes proposées unifient et dépassent largement l'état de l'art. Elles sont appliquées aux inclusions monotones composites en dualité, aux problèmes d'équilibre, au traitement du signal et de l'image, à la théorie des jeux, à la théorie du trafic, aux équations d'évolution, aux problèmes de meilleure approximation et à la décomposition de domaine dans les équations aux dérivées partielles.

Le but de cette thèse est de développer de nouvelles techniques d'éclatement d'opérateurs multivoques pour résoudre des problèmes d'inclusion monotone structurés dans des espaces hilbertiens. La dualité au sens des inclusions monotones tient une place essentielle dans ce travail et nous permet d'obtenir des décompositions qui ne seraient pas disponibles via une approche purement primale. Nous développons plusieurs algorithmes à métrique fixe ou variable dans un cadre unifié, et montrons en particulier que de nombreuses méthodes existantes sont des cas particuliers de la méthode explicite--implicite formulée dans des espaces produits adéquats. Les méthodes proposées sont appliquées aux problèmes d'inéquations variationnelles, aux problèmes de minimisation, aux problèmes inverses, aux problèmes de traitement du signal, aux problèmes d'admissibilité et aux problèmes de meilleure approximation. Dans un second temps, nous introduisons une notion de suite quasi-fejérienne à métrique variable et analysons ses propriétés asymptotiques. Ces résultats nous permettent d'obtenir des extensions de méthodes d'éclatement aux problèmes où la métrique varie à chaque itération.

Cette thèse est consacrée à la résolution de trois types de problèmes fondamentaux qui apparaissent en analyse fonctionnelle hilbertienne non-linéaire et dans ses applications : les problèmes d'équilibre pour les bifonctions monotones, les problèmes de point fixe pour les contractions, et les problèmes d'inclusion pour les opérateurs monotones. Notre objectif est d'élaborer de nouvelles méthodes d'approximation et de construction de solutions pour ces problèmes et d'étudier leur comportement asymptotique. Dans un premier temps, nous proposons de nouvelles perturbations visqueuses et visco-pénalisées de ces problèmes, et étudions le comportement asymptotique des courbes d'approximation associées quand la perturbation devient évanescente. Nous étudions ensuite les propriétés de divers systèmes dynamiques discrets et continus associés à ces courbes. Cette étude débouche en particulier sur de nouveaux algorithmes, dont la convergence est établie. Des applications numériques à des problèmes de restauration en traitement de l'image sont fournies pour illustrer la mise en œuvre et les performances de certains des algorithmes proposés.

Les méthodes de décomposition sont une application du concept de diviser pour régner en optimisation. L'idée est de décomposer un problème d'optimisation donné en une séquence de sous-problèmes plus faciles à résoudre. Bien que ces méthodes soient les meilleures pour un grand nombre de problèmes de recherche opérationnelle, leur application à des problèmes réels de grande taille présente encore de nombreux défis. Cette thèse propose des améliorations méthodologiques et algorithmiques de méthodes de décomposition. Notre approche est basée sur l'analyse convexe et l'optimisation non-différentiable. Dans la décomposition par les contraintes (ou relaxation lagrangienne) du problème de planification de production électrique, même les sous-problèmes sont trop difficiles pour être résolus exactement. Mais des solutions approchées résultent en des prix instables et chahutés. Nous présentons un moyen simple d'améliorer la structure des prix en pénalisant leurs oscillations, en utilisant en particulier une régularisation par variation totale. La consistance de notre approche est illustrée sur des problèmes d'EDF. Nous considérons ensuite la décomposition par les variables (ou de Benders) qui peut avoir une convergence excessivement lente. Avec un point de vue d'optimisation non-différentiable, nous nous concentrons sur l'instabilité de l'algorithme de plans sécants sous-jacent à la méthode. Nous proposons une stabilisation quadratique de l'algorithme de Benders, inspirée par les méthodes de faisceaux en optimisation convexe. L'accélération résultant de cette stabilisation est illustrée sur des problèmes de conception de réseau et de localisation de plates-formes de correspondance (hubs). Nous nous intéressons aussi plus généralement aux problèmes d'optimisation convexe non-différentiable dont l'objectif est coûteux à évaluer. C'est en particulier une situation courante dans les procédures de décomposition. Nous montrons qu'il existe souvent des informations supplémentaires sur le problème, faciles à obtenir mais avec une précision inconnue, qui ne sont pas utilisées dans les algorithmes. Nous proposons un moyen d'incorporer ces informations incontrôlées dans des méthodes classiques d'optimisation convexe non-différentiable. Cette approche est appliquée avec succès à desproblèmes d'optimisation stochastique. Finalement, nous introduisons une stratégie de décomposition pour un problème de réaffectation de machines. Cette décomposition mène à une nouvelle variante de problèmes de conditionnement vectoriel (vectorbin packing) où les boîtes sont de taille variable. Nous proposons des heuristiques efficaces pour ce problème, qui améliorent les résultats de l'état de l'art du conditionnement vectoriel. Une adaptation de ces heuristiques permet de construire des solutions réalisables au problème de réaffectation de machines de Google. / Decomposition methods are an application of the divide and conquer principle to large-scale optimization. Their idea is to decompose a given optimization problem into a sequence of easier subproblems. Although successful for many applications, these methods still present challenges. In this thesis, we propose methodological and algorithmic improvements of decomposition methods and illustrate them on several operations research problems. Our approach heavily relies on convex analysis and nonsmooth optimization. In constraint decomposition (or Lagrangian relaxation) applied to short-term electricity generation management, even the subproblems are too difficult to solve exactly. When solved approximately though, the obtained prices show an unstable noisy behaviour. We present a simple way to improve the structure of the prices by penalizing their noisy behaviour, in particular using a total variation regularization. We illustrate the consistency of our regularization on real-life problems from EDF. We then consider variable decomposition (or Benders decomposition), that can have a very slow convergence. With a nonsmooth optimization point of view on this method, we address the instability of Benders cutting-planes algorithm. We present an algorithmic stabilization inspired by bundle methods for convex optimization. The acceleration provided by this stabilization is illustrated on network design andhub location problems. We also study more general convex nonsmooth problems whose objective function is expensive to evaluate. This situation typically arises in decomposition methods. We show that it often exists extra information about the problem, cheap but with unknown accuracy, that is not used by the algorithms. We propose a way to incorporate this coarseinformation into classical nonsmooth optimization algorithms and apply it successfully to two-stage stochastic problems.Finally, we introduce a decomposition strategy for the machine reassignment problem. This decomposition leads to a new variant of vector bin packing problems, where the bins have variable sizes. We propose fast and efficient heuristics for this problem that improve on state of the art results of vector bin packing problems. An adaptation of these heuristics is also able to generate feasible solutions for Google instances of the machine reassignment problem.

Le problème de tarification combinatoire (CPP) ou le jeu de tarification de Stackelberg est une classe de problèmes d’optimisation bi-niveaux comprenant deux décideurs dans un ordre séquentiel. Le premier décideur, le leader, maximise ses revenus en contrôlant les prix d’un ensemble de ressources. Le deuxième décideur, le suiveur, réagit aux prix et sélectionne un sous-ensemble de ressources selon un problème d’optimisation combinatoire. Selon le problème du suiveur, le CPP peut être très difficile à résoudre. Cette thèse présente trois articles couvrant plusieurs méthodes de solution exacte pour le CPP. Le premier article aborde la modélisation et le prétraitement pour une spécialisation du CPP : le problème de tarification du réseau (NPP), dans lequel le problème du suiveur est un problème du plus court chemin. Les formulations du NPP sont organisées dans un cadre général qui établit les liens entre elles. Le deuxième article se concentre sur la version à plusieurs marchandises du NPP. À partir des résultats de l’analyse convexe, nous dérivons une nouvelle formulation du NPP et prouvons que le NPP évolue de manière polynomiale par rapport au nombre de marchandises, étant donné que le nombre d’arcs à péage est fixe. Le troisième article nous ramène au CPP général, dans lequel les problèmes du suiveur sont NP-difficiles. En utilisant deux modèles de programmation dynamique différents, les problèmes du suiveur sont convertis en programmes linéaires, auxquels la dualité forte peut être appliquée. En raison de la nature NP-difficile de ces problèmes, des schémas de génération dynamique de contraintes sont proposés. Les méthodes de solution décrites dans chaque article sont étayées par des résultats expérimentaux, montrant leur efficacité en pratique. Cette thèse approfondit notre compréhension de la structure du CPP et introduit des méthodologies innovantes pour y faire face, contribuant ainsi à de nouvelles perspectives pour aborder les problèmes de tarification et bi-niveau en général. / The combinatorial pricing problem (CPP) or Stackelberg pricing game is a class of bilevel optimization problems that consist of two decision makers in sequential order. The first decision maker, the leader, maximizes their revenue by controlling the prices of a set of resources. The second decision maker, the follower, reacts to the prices and selects a subset of resources according to a combinatorial optimization problem. Depending on the follower’s problem, the CPP can be very challenging to solve. This thesis presents three articles covering several exact solution methods for the CPP. The first article addresses the modeling and preprocessing for a specialization of the CPP: the network pricing problem (NPP), in which the follower’s problem is a shortest path problem. The formulations of the NPP are organized in a general framework which establishes the links between them. The second article focuses on the multi-commodity version of the NPP. From the results in convex analysis, we derive a novel formulation of the NPP and with it, we prove that the NPP scales polynomially with respect to the number of commodities, given that the number of tolled arcs is fixed. The third article leads us back to the general CPP, in which the follower’s problems are NP-hard. By utilizing two different dynamic programming models, the follower’s problems are converted into linear programs, to which strong duality can be applied. Due to the NP-hard nature of these problems, dynamic constraint generation schemes are proposed. The solution methods described in each article are backed up with experimental results, showing that they are effective in practice. This thesis deepens our comprehension of the CPP structure and introduces innovative methodologies for addressing it, thereby contributing new perspectives to tackle pricing and bilevel problems in general.

L'objet de cette thèse est d'étendre le cadre théorique et les méthodes numériques du transport optimal à des objets plus généraux que des mesures de probabilité. En premier lieu, nous définissons des modèles de transport optimal entre mesures positives suivant deux approches, interpolation et couplage de mesures, dont nous montrons l'équivalence. De ces modèles découle une généralisation des métriques de Wasserstein. Dans une seconde partie, nous développons des méthodes numériques pour résoudre les deux formulations et étudions en particulier une nouvelle famille d'algorithmes de "scaling", s'appliquant à une grande variété de problèmes. La troisième partie contient des illustrations ainsi que l'étude théorique et numérique, d'un flot de gradient de type Hele-Shaw dans l'espace des mesures. Pour les mesures à valeurs matricielles, nous proposons aussi un modèle de transport optimal qui permet un bon arbitrage entre fidélité géométrique et efficacité algorithmique. / This thesis generalizes optimal transport beyond the classical "balanced" setting of probability distributions. We define unbalanced optimal transport models between nonnegative measures, based either on the notion of interpolation or the notion of coupling of measures. We show relationships between these approaches. One of the outcomes of this framework is a generalization of the p-Wasserstein metrics. Secondly, we build numerical methods to solve interpolation and coupling-based models. We study, in particular, a new family of scaling algorithms that generalize Sinkhorn's algorithm. The third part deals with applications. It contains a theoretical and numerical study of a Hele-Shaw type gradient flow in the space of nonnegative measures. It also adresses the case of measures taking values in the cone of positive semi-definite matrices, for which we introduce a model that achieves a balance between geometrical accuracy and algorithmic efficiency.