Guaranteed Deterministic Global Optimization using Constraint Programming through Algebraic, Functional and Piecewise Differential Constraints

Ce mémoire présente une approche basée sur des méthodes garanties pour résoudre des problèmes d’optimisation de systèmes dynamiques multi-physiques. Ces systèmes trouvent des applications directes dans des domaines variés tels que la conception en ingéniérie, la modélisation de réactions chimiques, la simulation de systèmes biologiques ou la prédiction de la performance sportive.La résolution de ces problèmes d’optimisation s’effectue en deux phases. La première consiste à mettre le problème en équations sous forme d’un modèle mathématique constitué d’un ensemble de variables, d’un ensemble de contraintes algébriques et fonctionelles ainsi que de fonctions de coût. Celles-ci sont utilisées lors de la seconde phase qui consiste à d’extraire du modèle les solutions optimales selon plusieurs critères (volume, poids, etc).Les contraintes algébriques permettent de manipuler des grandeurs statiques (quantité, taille, densité, etc). Elles sont non linéaires, non convexes et parfois discontinues.Les contraintes fonctionnelles permettent de manipuler des grandeurs dynamiques. Ces contraintes peuvent être relativement simples comme la monotonie ou la périodicité, mais aussi bien plus complexe par la prise en compte de contraintes différentielles simples ou définies par morceaux. Les équations différentielles sont utilisées pour modéliser des comportements physico-chimiques (magnétiques, thermiques, etc) et d’autres caractéristiques qui varient lors de l’évolution du système.Il existe plusieurs niveaux d’approximation pour chacune de ces deux phases. Ces approximations donnent des résultats pertinents, mais elles ne permettent pas de garantir l’optimalité ni la réalisabilité des solutions.Après avoir présenté un ensemble de méthodes garanties permettant de résoudre de manière garantie des équations différentielles ordinaires, nous formalisons un modèle particulier de systèmes hybrides sous la forme d’équations différentielles ordinaires par morceaux. A l’aide de plusieurs preuves et théorèmes nous étendons la première méthode de résolution pour résoudre de manière garantie ces équations différentielles par morceaux. Dans un second temps, nous intégrons ces deux méthodes au sein d’un module de programmation par contracteurs, que nous avons implémenté. Ce module basé sur des méthodes garantie permet de résoudre des problèmes de satisfaction de contraintes algébriques et fonctionnelles. Ce module est finalement utilisé dans un algorithme d’optimisation globale déterministe modulaire permettant de résoudre les problèmes considérés.In this thesis a set of tools based on guaranteed methods are presented in order to solve multi-physics dynamic problems. These systems can be applied in various domains such that engineering design process, model of chemical reactions, simulation of biological systems or even to predict athletic performances.The resolution of these optimization problems is made of two stages. The first one consists in defining a mathematical model by setting up the equations for the problem. The model is made of a set of variables, a set of algebraic and functional constraints and cost functions. The latter are used in the second stage in order to extract the optimal solutions from the model depending on several criteria (volume, weight, etc).Algebraic constraints are used to describe the static properties of the system (quantity, size, density, etc). They are non-linear, non-convex and sometimes discontinuous. Functional constraints are used to manipulate dynamic quantities. These constraints can be quite simple such as monotony or periodicity or they can be more complex such as simple or piecewise differential constraints. Differential equations are used to describe physico-chemical properties (magnetic, thermal, etc) and other features evolving with the component use. Several levels of approximation exist for each of these two stages. These approximations give some relevant results but they do not guarantee the feasibility nor the optimality of the solutions.After presenting a set of guaranteed methods in order to perform the guaranteed integration of ordinary differential equations, a peculiar type of hybrid system that can be modeled with piecewise ordinary differential equation is considered. A new method that computes guaranteed integration of these piecewise ordinary differential equations is developed through an extension of the initial algorithm based on several proofs and theorems. In a second step these algorithms are gathered within a contractor programming module that have been implemented. It is used to solve algebraic and functional constraint satisfaction problems with guaranteed methods. Finally, the considered optimization problems are solved with a modular deterministic global optimization algorithm that uses the previous modules