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.

Cette thèse consiste à étudier l'organisation du système de contrôle des voies métaboliques des bactéries afin de dégager des propriétés systémiques révélant son fonctionnement. Dans un premier temps, nous montrons que le contrôle des voies métaboliques est hautement structuré et peut se décomposer en modules fortement découplés en régime stationnaire. Ces modules possèdent des propriétés mathématiques remarquables ayant des conséquences importantes en biologie. Cette décomposition, basée intrinsèquement sur la vision système de l'Automatique, offre un cadre théorique formel général d'analyse du contrôle des voies métaboliques qui s'est révélé effectif pour analyser des données expérimentales. dans un deuxième temps, nous nous intéressons aux raisons possibles de l'émergence de cette structure de contrôle similaire. Nous identifions un ensemble de contraintes structurelles agissant au niveau de la répartition d'une ressource commune, les protéines, entre les processus cellulaires. Respecter ces contraintes pour un taux de croissance donné conduit à formaliser et résoudre un problème d'optimisation convexe non différentiable, que nous appelons Resource balance Analysis. Ce problème d'optimisation se résout numériquement à l'échelle de la bactérie grâce à un problème de Programmation Linéaire équivalent. plusieurs propriétés sont déduites de l'analyse théorique du critère obtenu. Tout d'abord, le taux de croissance est structurellement limité par la répartition d'une quantité finie de protéines entre les voies métaboliques et les ribosomes. Ensuite, l'émergence des modules dans les voies métaboliques provient d'une politique générale d'économie en protéines chez la bactérie pour gagner du taux de croissance. Certaines stratégies de transport bien connues comme la répression catabolique ou la substitution de transporteurs haute/basse affinités sont prédites par notre méthode et peuvent alors être interprétées comme le moyen de maximiser la croissance tout en minimisant l'investissement en protéines. / This thesis consist in studying the organization of the control system of metabolic pathways of bacteria to identify systemic properties revealing its operation. At first, we show that control of metabolic pathways is highly structured and can be decomposed into modules strongly decoupled in steady-state. These modules are defined by their singular mathematical properties having important implications in biology. This decomposition, based inherently on the system outlook of automatic control, offers a formal theoretical analysis of general control of metabolic pathways, which has been effective in analysing experimental data. In a second step, we consider the possible reasons for the emergence of this modular control structure. We identify a set of structural constraints acting at the distribution of a common resourc, the proteins between cellular processes. Satisfying these constraints for a given growth rate leads to formalize and to solve a non-differentiable convex optimization problem, that we call Resource Balance Analysis. This optimization problem is solved numerically at the scale of the bacteria through an equivalent linear programming problem. Several properties are derived from theoretical analysis of the obtained criterion. Firts, the growth rate is structurally limited by the distribution of a finite amount of proteines between the metabolic pathways and the ribosomes. Second, the emergence of modules in metabolic pathways arises from a policy of economy in proteins in the bacterium to increase the growth rate. Some well known transport strategies such as catabolite repression of the substitution between low/highaffinity transporters are predicted by our methods and could consequently be interpretd as ways to maximize growth while minimizing investment in proteins.

Cette thèse traite de la modélisation et de l'approximation numérique des écoulements liquide-gaz compressibles. La difficulté centrale est la modélisation et l'approximation de l'interface liquide-gaz. Le modèle bifluide est constitué d'un système de lois de conservation fermé par une loi d'état du mélange. La loi d'état conditionne les bonnes propriétés (hyperbolicité, existence d'une entropie de Lax) du système. Les schémas classiques de type Godunov conduisent à des imprécisions les rendant inutilisables en pratique. L'existence de solutions discontinues rend difficile la construction de schémas d'ordre élevé et nécessite des maillages très fins pour une précision acceptable. Il est indispensable de proposer des algorithmes performants pour les calculateurs parallèles les plus récents. Nous aborderons chacune de ces problématiques: construction d'une "bonne" loi de pression, construction de schémas numériques adaptés, programmation sur calculateur massivement multicoeur. / This thesis deals with the modeling and numerical approximation of compressible gas-liquid flows. The main difficulty lies in modeling and approximation of the liquid-gas interface. The two-fluid model is a system of conservation laws closed with a mixture pressure law. The law has to be chosen carefully, it conditions good properties of the system as hyperbolicity or existence of a Lax entropy. Classic conservative Godunov-type schemes lead to inaccuracies that make them unusable inpractice. The existence of discontinuous solutions makes it difficult to build high order schemes and requires very fine meshes to an acceptable accuracy. It is therefore essential to provide efficient algorithms for the High Performance Computing. In this thesis, we will partially treat each of these issues : construction of a "good" pressure law, building adapted numerical schemes, programming on GPU or GPU cluster.

Le but de cette thèse est d’étudier les structures obtenues à partir des groupes de réflexion finis. Ce travail consiste en quatre articles publiés, un article soumis et un article en préparation dont les résultats partiels constituent un chapitre de cette thèse. Dans le premier article, nous présentons une réduction des orbites des groupes de Coxeter finis vers leurs sous-groupes. Nous utilisons des matrices de projection, c’est-à-dire, des applications qui transforment les racines simples d’un groupe de réflexion en les racines simples du sous-groupe associé. Les résultats présentés dans ce papier se concentrent sur les groupes finis de réflexion non crystallographiques. De plus, nous utilisons les polytopes engendrés par le groupe non crystallographique H3 pour illustrer les lois de ramification (branching rules), c’est-à-dire une réduction des orbites des groupes finis de Coxeter. Dans le deuxième article, nous étudions les polytopes avec 60 sommets engendrés par le groupe non crystallographique H3. Nous utilisons la méthode de décoration des diagrammes de Coxeter–Dynkin pour décrire leurs structures en détails et décomposer les sommets en somme des orbits de symétries de dimension inférieure. Le troisième article compare deux notations utilisées pour décrire le polyèdre engendré par le groupe de réflexion. Il s’agit du symbole de Schläfli et de la notation des points dominants. Nous y présentons les avantages de chaque méthode, expliquons les deux approches et nous les illustrons par des exemples. Dans le quatrième article, nous nous concentrons sur le graphène, c’est-à-dire un pavement d’hexagones sur le plan, qui possède de remarquables propriétés quand les sommets sont modélisés par des atomes de carbone. Dans ce travail, nous présentons différentes méthodes pour obtenir du graphène à partir de réseaux (lattices) et des orbites de dimension 3 des groupes finis de réflexion. De plus, une technique de coloriage des hexagones au moyen d’un nombre fini de couleurs est donnée avec une méthode systématique pour raffiner le graphène. Dans le cinquième article, nous utilisons des v fonctions spéciales et les transformations de Fourier pour traiter les données échantillonnées sur un réseau de carrés du groupe de Lie SU(2)×SU(2), relié au groupe de symétrie A1×A1. / The goal of this thesis is to study structures obtained from finite reflection groups. The work is contained in four published papers, one submitted article and a research paper currently in preparation, with partial results presented as a chapter of this thesis. In the first article, we present a reduction of the orbits of finite Coxeter groups to their subgroups. We use projection matrices, that is, mappings that transform the simple roots of a reflection group to the simple roots of the appropriate subgroup. The results presented in this paper focus on non-crystallographic finite reflection groups. Moreover, we use polytopes generated by the non-crystallographic group H3 to illustrate the obtained branching rules, i.e., reductions of orbits of the finite Coxeter groups. In the second article, we study polytopes with 60 vertices, generated by the non-crystallographic group H3. We use a method of decoration of the Coxeter–Dynkin diagram to describe their structure in detail, and decompose their vertices into sums of orbits of lower-dimensional symmetries. The third article compares two notations used to describe polyhedra generated by reflection groups, namely the Schläfli symbol, and the dominant point notation. Here, we present the advantages of each method, we explain the two approaches, and we illustrate them through examples. In the fourth article, we focus on graphene, i.e., a hexagonal tiling of the plane that possesses remarkable properties when the vertices are modelled with carbon atoms. In this work, we present different methods to obtain graphene from lattices and three-dimensional orbits of finite reflection groups. Moreover, a technique to colour the hexagons by a finite number of colours is provided, along with a systematic method to refine the graphene. In the fifth article, we use special functions and Fourier transforms to process data sampled on a square lattice of the Lie group SU(2) × SU(2), related to the A1 × A1 symmetry group.

L’entropie d’une distribution sur un ensemble de variables aléatoires discrètes est toujours bornée par l’entropie de la distribution factorisée correspondante. Cette propriété est due à la sous-modularité de l’entropie. Par ailleurs, les fonctions sous-modulaires sont une généralisation des fonctions de rang des matroïdes ; ainsi, les fonctions linéaires sur les polytopes associés peuvent être minimisées exactement par un algorithme glouton. Dans ce manuscrit, nous exploitons ces liens entre les structures des modèles graphiques et les fonctions sous-modulaires. Nous utilisons des algorithmes gloutons pour optimiser des fonctions linéaires sur des polytopes liés aux matroïdes graphiques et hypergraphiques pour apprendre la structure de modèles graphiques, tandis que nous utilisons des algorithmes d’inférence sur les graphes pour optimiser des fonctions sous-modulaires. La première contribution de cette thèse consiste à approcher par maximum de vraisemblance une distribution de probabilité par une distribution factorisable et de complexité algorithmique contrôlée. Comme cette complexité est exponentielle dans la largeur arborescente du graphe, notre but est d’apprendre un graphe décomposable avec une largeur arborescente bornée, ce qui est connu pour être NP-difficile. Nous posons ce problème comme un problème d’optimisation combinatoire et nous proposons une relaxation convexe basée sur les matroïdes graphiques et hypergraphiques. Ceci donne lieu à une solution approchée avec une bonne performance pratique. Pour la seconde contribution principale, nous utilisons le fait que l’entropie d’une distribution est toujours bornée par l’entropie de sa distribution factorisée associée, comme conséquence principale de la sous-modularité, permettant une généralisation à toutes les fonctions sous-modulaires de bornes basées sur les concepts de modèles graphiques. Un algorithme est développé pour maximiser les fonctions sous-modulaires, un autre problème NP-difficile, en maximisant ces bornes en utilisant des algorithmes d’inférence vibrationnels sur les graphes. En troisième contribution, nous proposons et analysons des algorithmes visant à minimiser des fonctions sous-modulaires pouvant s’écrire comme somme de fonctions plus simples. Nos algorithmes n’utilisent que des oracles de ces fonctions simple basés sur minimisation sous-modulaires et de variation totale de telle fonctions. / The entropy of a probability distribution on a set of discrete random variables is always bounded by the entropy of its factorisable counterpart. This is due to the submodularity of entropy on the set of discrete random variables. Submodular functions are also generalisation of matroid rank function; therefore, linear functions may be optimised on the associated polytopes exactly using a greedy algorithm. In this manuscript, we exploit these links between the structures of graphical models and submodular functions: we use greedy algorithms to optimise linear functions on the polytopes related to graphic and hypergraphic matroids for learning the structures of graphical models, while we use inference algorithms on graphs to optimise submodular functions.The first main contribution of the thesis aims at approximating a probabilistic distribution with a factorisable tractable distribution under the maximum likelihood framework. Since the tractability of exact inference is exponential in the treewidth of the decomposable graph, our goal is to learn bounded treewidth decomposable graphs, which is known to be NP-hard. We pose this as a combinatorial optimisation problem and provide convex relaxations based on graphic and hypergraphic matroids. This leads to an approximate solution with good empirical performance. In the second main contribution, we use the fact that the entropy of a probability distribution is always bounded by the entropy of its factorisable counterpart mainly as a consequence of submodularity. This property of entropy is generalised to all submodular functions and bounds based on graphical models are proposed. We refer to them as graph-based bounds. An algorithm is developped to maximise submodular functions, which is NPhard, by maximising the graph-based bound using variational inference algorithms on graphs. As third contribution, we propose and analyse algorithms aiming at minimizing submodular functions that can be written as sum of simple functions. Our algorithms only make use of submodular function minimisation and total variation oracles of simple functions.

Cette thèse a pour objet la résolution exacte d’un problème d’optimisation des flux de puissance (OPF) dans un réseau électrique. Dans l’OPF, on doit planifier la production et la répartition des flux de puissances électriques permettant de couvrir, à un coût minimal, la consommation en différents points du réseau. Trois variantes du problème de l’OPF sont étudiées dans ce manuscrit. Nous nous concentrerons principalement sur la résolution exacte des deux problèmes (OPF − L) et (OPF − Q), puis nous montrerons comment notre approche peut naturellement s’´étendre à la troisième variante (OPF − UC). Cette thèse propose de résoudre ces derniers à l’aide d’une méthode de reformulation que l’on appelle RC-OPF. La contribution principale de cette thèse réside dans l’étude, le développement et l’utilisation de notre méthode de résolution exacte RC-OPF sur les trois variantes d’OPF. RC-OPF utilise également des techniques de contractions de bornes, et nous montrons comment ces techniques classiques peuvent être renforcées en utilisant des résultats issus de notre reformulation optimale. / Alternative Current Optimal Power Flow (ACOPF) is naturally formulated as a non-convex problem. In that context, solving (ACOPF) to global optimality remains a challenge when classic convex relaxations are not exact. We use semidefinite programming to build a quadratic convex relaxation of (ACOPF). We show that this quadratic convex relaxation has the same optimal value as the classical semidefinite relaxation of (ACOPF) which is known to be tight. In that context, we build a spatial branch-and-bound algorithm to solve (ACOPF) to global optimality that is based on a quadratic convex programming bound.

La performance des dispositifs moléculaires, tels que les cellules solaires ou des diodes électroluminescentes, peut être optimisée en contrôlant l’organisation des composantes des couches actives. Les fullerènes et leurs dérivés sont souvant utilisés dans des dispositifs photovoltaïques pour leurs propriétés électro-acceptrices et conductrices. Il est donc important de concevoir des structures moléculaires pouvant interagir avec les unités fullerène et ainsi de diriger leur organisation. Le caractère électro-accepteur et la forme convexe des fullerènes favorisent le choix d’un partenaire de surface complémentaire : électro-donneuse et concave. Le phosphangulène, une triarylphosphine hexacyclique qui répond à ces critères et est aisément fonctionnalisable, a été choisi comme structure de base pour la synthèse des cibles. La présente thèse décrit la synthèse et la structure des dérivés du phosphangulène et des cocristaux obtenus avec les fullerènes au travers de quatre articles soumis au courant de ce doctorat. Le premier article décrit la synthèse des dérivés chalcogénures du phosphangulène. Ces dérivés-ci présentent de nombreux polymorphes, résultant en de bons candidats pour la cocristallisation. Le second article se concentre sur les cocristaux de ces dérivés chalcogénures avec le C60 et le C70. Dans le troisième article, nous décrivons les complexes obtenus par la coordination du phosphangulène sur des métaux de transition. Enfin, dans le quatrième article, nous parlons des sels du µ-nitrido-bis(phosphangulène), un cation organique où deux unités phosphangulène sont pontées par un atome d’azote, ainsi que des cocristaux résultant de la combinaison de ce ligand pontant et du C60. / The performance of molecular devices such as solar cells or light-emitting diodes can be optimized by controlling how the active-layer components are organized. Fullerenes and their derivatives are often used in photovoltaic devices for their electron-accepting and conductive properties. It is therefore important to design molecular structures that can interact with fullerene units and thus direct their organization. The electron-accepting character and convex shape of fullerenes favor the choice of a partner with a complementary surface that is electron-donating and concave. Phosphangulene, a hexacyclic triarylphosphine that meets these criteria and is easily functionalizable, was chosen as the basic structure for synthesizing targets. This thesis describes the synthesis and structure of phosphangulene derivatives and their cocrystals obtained with fullerenes through four articles submitted during this doctorate. The first article describes the synthesis of chalcogenide derivatives of phosphangulene. These derivatives have many polymorphs, resulting in good candidates for cocrystallization. The second article focuses on cocrystals of these chalcogenide derivatives with C60 and C70. In the third article, we describe the complexes obtained by the coordination of phosphangulene with transition metals. Finally, in the fourth article, we talk about the salts of μ-nitrido-bis (phosphangulene), an organic cation where two phosphangulene units are bridged by a nitrogen atom, as well as the crystals resulting from the combination of this bridging ligand and C60.

On étudie l'équation de Hamilton-Jacobi évolutive du premier ordre, couplée avec une donnée initiale lipschitzienne. Le but est de comparer les solutions de viscosité et les solutions variationnelles pour cette équation, deux notions de solutions faibles qui coïncident en dynamique hamiltonienne convexe. Pour travailler dans un cadre pertinent pour les deux types de solutions, on doit d’abord construire une solution variationnelle sans hypothèse de compacité sur la variété ou le hamiltonien étudiés. On retrace dans ce cas la construction historique des solutions variationnelles, en détaillant les propriétés de la famille génératrice obtenue par la méthode des géodésiques brisées. Il en découle des estimées permettant d’obtenir la solution de viscosité à partir de la solution variationnelle par un procédé d’itération. Après avoir vérifié que la solution variationnelle construite coïncide effectivement avec la solution de viscosité pour un Hamiltonien convexe, on caractérise les Hamiltoniens intégrables pour lesquels cette propriété persiste, en étudiant attentivement des exemples élémentaires en dimension 1 et 2. / We study the first order Hamilton-Jacobi equation associated with a Lipschitz initial condition. The purpose of this thesis is to compare two notions of weak solutions for this equation, namely the viscosity solution and the variational solution, that are known to coincide in convex Hamiltonian dynamics. In order to work in a relevant framework for both notions, we first need to build a variational solution without compactness assumption on the manifold or the Hamiltonian. To do so, we follow the historical construction, detailing properties of the generating family obtained via the broken geodesics method. Local estimates allow to prove that the viscosity solution can be obtained from the variational solution via an iterative process. We then check that this construction gives effectively the viscosity solution for a convex Hamiltonian, and characterize the integrable Hamiltonians for which this property persists by carefully studying elementary examples in dimension 1 and 2.

No description available.

Le problème de l'adaptation d'impédance en ingénierie des hyper fréquences et en électronique en général consiste à minimiser la réflexion de la puissance qui doit être transmise, par un générateur, à une charge donnée dans une bande de fréquence. Les exigences d'adaptation et de filtrage dans les systèmes de communication classiques sont généralement satisfaites en utilisant un circuit d'adaptation suivi d'un filtre. Nous proposons ici de concevoir des filtres d'adaptation qui intègrent à la fois les exigences d'adaptation et de filtrage dans un seul appareil et augmentent ainsi l'efficacité globale et la compacité du système. Dans ce travail, le problème d'adaptation est formulé en introduisant un problème d'optimisation convexe dans le cadre établi par la théorie de d'adaptation de Fano et Youla. De ce contexte, au moyen de techniques modernes de programmation semi-définies non linéaires, un problème convexe, et donc avec une optimalité garantie, est obtenu. Enfin, pour démontrer les avantages fournis par la théorie développée au-delà de la synthèse de filtres avec des charges complexes variables en fréquence, nous examinons deux applications pratiques récurrentes dans la conception de ce type de dispositifs. Ces applications correspondent, d'une part, à l'adaptation d'un réseau d'antennes dans le but de maximiser l'efficacité du rayonnement, et, d'autre part, à la synthèse de multiplexeurs où chacun des filtres de canal est adapté au reste du dispositif, notamment les filtres correspondant aux autres canaux. / The problem of impedance matching in electronics and particularly in RF engineering consists on minimising the reflection of the power that is to be transmitted, by a generator, to a given load within a frequency band. The matching and filtering requirements in classical communication systems are usually satisfied by using a matching circuit followed by a filter. We propose here to design matching filters that integrate both, matching and filtering requirements, in a single device and thereby increase the overall efficiency and compactness of the system. In this work, the matching problem is formulated by introducing convex optimisation on the framework established by the matching theory of Fano and Youla. As a result, by means of modern non-linear semi-definite programming techniques, a convex problem, and therefore with guaranteed optimality, is achieved. Finally, to demonstrate the advantages provided by the developed theory beyond the synthesis of filters with frequency varying loads, we consider two practical applications which are recurrent in the design of communication devices. These applications are, on the one hand, the matching of an array of antennas with the objective of maximizing the radiation efficiency, and on the other hand the synthesis of multiplexers where each of the channel filters is matched to the rest of the device, including the filters corresponding to the other channels.