Une approche formelle pour l'optimisation de systèmes à événements discrets
Résumé
This thesis is centered on optimization of discrete event dynamical systems over finite domains. Two basic optimization methods have been considered: the Minimum Principle and Dynamic Programming. The result of the approach based on the Minimum Principle has been established in the form of a Theorem in which the necessary optimality condition is defined in terms of a variational inequality separable with respect to stages. This inequality is an explicit function of control variables at the current time, of state variables and possibly exogenous parameters involved in the evolution model. A resolution technique for such a parametric variational inequality has been developed under a " min-max " type process, respectively for the current control and the other controls. A method of symbolic computation is proposed in the manuscript to optimize a polynomial form defined over a finite discrete set. The corresponding algorithm is denoted by the acronym SCDO (Symbolic Computation for Discrete Optimization). The outcome of the application of this algorithm to solving the above mentioned " Min-Max " problem is the expression of the symbolic control sequence in a symbolic form explicit in the system state (and the exogenous parameters). The approach based on Dynamic Programming directly exploits the parametric character and the decomposition framework of this method. Integration of the SCDO algorithm in both stages of the process (optimization and trajectory reconstruction) here again generates an expression of the optimal control sequence explicit in the state.
Cette thèse est centrée sur l'optimisation de systèmes dynamiques a événements discrets sur un domaine fini. Deux approches fondamentales de l'optimisation sont considérées : le principe du minimum et la programmation dynamique. Dans chaque cas une méthode de calcul formel est développée pour l'optimisation d'une forme polynomiale sur un domaine de définition fini. Le résultat de l'approche basée sur le principe du minimum est établi sons la forme d'un théorème dans lequel la condition (nécessaire) d'optimalité est définie en terme d'une inégalité variationnelle sons une forme séparable par rapport aux étapes (instants). Celle-ci est explicitement fonction de la variable de commande à linstant courant, (commande courante), de la forme paramétrée de celle-ci et de l'état du système auquel peuvent s'ajouter des paramètres exogènes impliqués dans le modèle d'évolution. La résolution de cette inégalité variationnelle paramétrique est développée selon une procédure de type Min-Max avec une minimisation par rapport aux commandes courantes et une maximisation par rapport aux autres commandes. L'algorithme correspondant est désigné par le symbole SCDO (Symbolic Computation for Discrete Optimisation). L'approche basée sur la programmation dynamique exploite le caractère paramétrique de cette méthode de décomposition. L'intégration de l'algorithme SCDO dans les deux phases de ce processus d'optimisation permet ici encore d'exprimer la séquence de commandes optimales sous une forme explicite de l'état du système et des autres paramètres exogènes. Dans ce mémoire, nous considérons également le principe de relaxation pour transformer le problème discret en un problème continu de résolution classique. Ainsi, pour une famille particulière de processus discrets linéaires par rapport à l'état et de fonction de coût concave, nous obtenons une condition de type principe du minimum, équivalente pour l'optimum relaxé et l'optimum de problème original. Dans le cas de fonctions de coût linéaires, la condition obtenue est celle du principe du minimum classique.
Domaines
Automatique / Robotique
Loading...