Ce document propose un parcours de mes travaux de recherche en optimisation, en passant par l'optimisation mixte en variables entières, l'optimisation non-linéaire continue locale et le clustering dans les réseaux (graphes). Le premier chapitre traite de la programmation non linéaire mixte en variables entières et de l'optimisation globale déterministe. Il présente des contributions relatives à des investigations théoriques ainsi que des applications à des problèmes concrets. Nous discutons principalement de relaxations convexes et de reformulations automatiques de problèmes de programmation mathématique, dans le but d'améliorer l'efficacité des algorithmes de Branch-and-Bound. Dans le cadre de la programmation polynomiale, nous avons étudié des relaxations convexes pour les monômes multilinéaires et la génération de relaxations compactes de problèmes polynomiaux basés sur une technique spécifique de reformulation-linéarisation (RLT). Parmi les applications, une attention particulière est portée à des problèmes qui se posent dans la gestion du trafic aérien. Nous avons proposé de nouveaux modèles mathématiques et des approches de résolution basées d'une part sur l'optimisation mixte en variables entières et d'autre part sur le contrôle optimal. Deux thèmes de l'optimisation continue non-linéaire sont décrits au deuxième chapitre. Des méthodes de point intérieur pour la programmation quadratique et leurs noyaux d'algèbre linéaire (systèmes KKT) sont d'abord discutées. L'accent est mis sur les méthodes itératives pour les systèmes KKT et sur des questions connexes, telles que les techniques de préconditionnement et les propriétés de convergence. L'autre sujet discuté concerne, encore une fois, des problèmes de trafic aérien. Il porte sur les approches déjà mentionnées de contrôle optimal qui conduisent à des problèmes non-linéaires. Le troisième chapitre présente mes principaux résultats dans le domaine du clustering dans les réseaux. Le problème de l'identification de clusters dans les réseaux peut être formulé en utilisant la programmation mathématique et conduit généralement à un problème d'optimisation combinatoire. Mes contributions concernent les critères de classification et les méthodes de clustering correspondantes. Une attention particulière est portée aux méthodes exactes utilisées pour résoudre l'ensemble du problème d'optimisation ou, localement, les sous-problèmes survenant dans des heuristiques hiérarchiques, ou enfin dans le raffinement des solutions obtenues précédemment par d'autres méthodes.

L'augmentation des besoins en bande passante dans les réseaux de télécommunications pousse les opérateurs à déployer de nouvelles infrastructures. Pour le réseau d'accès fixe, la fibre optique est la technologie envisagée. Du fait des enjeux financiers et de la complexité qui vont de pair avec ce déploiement, il est crucial d'optimiser son coût tout en respectant à la fois les attentes en qualité de service et les règles d'ingénierie du déploiement. Cette thèse fait suite à des travaux antérieurs, à l'issue desquels le problème avait été modélisé sous la forme d'un programme linéaire en nombres entiers. Un travail conséquent quant à l'amélioration de la résolution de ce problème avait été fourni, et de nombreuses pistes de recherches avaient été envisagées pour faire suite à ces travaux. Parmi ces pistes, il y avait le traitement de l'incertitude sur la demande qui occupe une grande partie de cette étude. En effet, les futurs clients ne s'étant pas encore déclarés, il n'est plus possible de dimensionner le réseau par rapport à des données connues et fixées. Dans ce cas, le problème devient un problème d'optimisation combinatoire dans l'incertain. Le choix a été fait de le traiter sous l'angle de l'optimisation robuste. Cette approche permet de se prémunir contre l'incertitude en garantissant la faisabilité des solutions dans tous les cas ainsi qu'une optimisation du " pire cas ". Le formalisme qui en découle rend souvent les problèmes étudiés complexes à résoudre. En effet, ils font intervenir des formulations à plusieurs niveaux où les décisions sont prises en séquence, avant ou après la réalisation du scénario incertain. Des algorithmes adaptés ont été développés pour permettre l'application de la robustesse au déploiement des réseaux de fibres optiques. Ces algorithmes, exacts ou approchés, ont permis, via leurs résultats, d'obtenir une connaissance stratégique réelle pour les déploiements à venir. A la suite de ces investigations sur le problème du déploiement optique, certains résultats ont pu être étendus et généralisés à d'autres problèmes d'optimisation robuste, comme par exemple des bornes de probabilité sur la pertinence des ensembles d'incertitudes ou une estimation probabiliste des coûts futurs dans les problèmes d'optimisation robuste en deux étapes. En marge de ces travaux sur l'incertitude qui occupent la plus grande partie de cette étude, d'autres travaux ont été réalisés sur ce problème. En effet, dans le but d'améliorer la prise en compte des coûts futurs du réseau (maintenance, gestion, etc.) qui sont, sur le long terme, les plus importants, une approche a été développée qui permet de prendre en compte les " bonnes pratiques " de déploiement directement dans l'optimisation. L'intégration de ces considérations, regroupées sous le terme d'OA&M (pour Organisation, Administration et Maintenance), a été validée par le développement de macro-modèles de coûts, à même d'estimer les gains futurs à attendre de ces nouvelles contraintes. Enfin, nos efforts ont porté sur la résolution d'une version particulière du problème, dans des graphes qui sont des arbres, avec la prise en compte des contraintes de câblage dans l'optimisation. Pour ce problème qui avait déjà été étudié, un nouvel algorithme de programmation dynamique a été proposé. Il s'appuie fortement sur les propriétés du problème et les utilise pour n'explorer qu'un nombre très limité de solutions tout en restant exact. Les performances de l'algorithme ont montré une nette amélioration du temps de calcul par rapport à des approches de type programmation linéaire en nombres entiers. L'ensemble de ces travaux a permis de découvrir d'autres pistes de recherche, notamment sur des versions alternatives du traitement de l'incertitude, ainsi que sur une prise en compte plus fine du câblage dans l'optimisation.

Cette thèse est divisée en deux parties. Dans la première partie, nous étudions des problèmes de contrôle optimal déterministes avec contraintes et nous nous intéressons à des questions d'analyse de sensibilité. Le point de vue que nous adoptons est celui de l'optimisation abstraite; les conditions d'optimalité nécessaires et suffisantes du second ordre jouent alors un rôle crucial et sont également étudiées en tant que telles. Dans cette thèse, nous nous intéressons à des solutions fortes. De façon générale, nous employons ce terme générique pour désigner des contrôles localement optimaux pour la norme L1. En renforçant la notion d'optimalité locale utilisée, nous nous attendons à obtenir des résultats plus forts. Deux outils sont utilisés de façon essentielle : une technique de relaxation, qui consiste à utiliser plusieurs contrôles simultanément, ainsi qu'un principe de décomposition, qui est un développement de Taylor au second ordre particulier du lagrangien. Les chapitres 2 et 3 portent sur les conditions d'optimalité nécessaires et suffisantes du second ordre pour des solutions fortes de problèmes avec contraintes pures, mixtes et sur l'état final. Dans le chapitre 4, nous réalisons une analyse de sensibilité pour des problèmes relaxés avec des contraintes sur l'état final. Dans le chapitre 5, nous réalisons une analyse de sensibilité pour un problème de production d'énergie nucléaire. Dans la deuxième partie, nous étudions des problèmes de contrôle optimal stochastique sous contrainte en probabilité. Nous étudions une approche par programmation dynamique, dans laquelle le niveau de probabilité est vu comme une variable d'état supplémentaire. Dans ce cadre, nous montrons que la sensibilité de la fonction valeur par rapport au niveau de probabilité est constante le long des trajectoires optimales. Cette analyse nous permet de développer des méthodes numériques pour des problèmes en temps continu. Ces résultats sont présentés dans le chapitre 6, dans lequel nous étudions également une application à la gestion actif-passif.

La prédiction de trajectoires d'avions à partir des données disponibles au sol est un problème critique pour le contrôle aérien. Une prédiction fiable et efficace est un prérequis pour l'implémentation d'outils automatiques pour la détection et la résolution de conflits entre les trajectoires. Dans ce contexte, nous proposons de nouvelles méthodes non paramétriques pour la prédiction d'intervalle contenant une proportion attendue des données avec un haut niveau de confiance. Dans un premier temps, nous traitons le problème de l'estimation d'une distribution de probabilité à partir d'un petit échantillon. En considérant l'interprétation des distributions de possibilité comme une famille de distributions de probabilité, nous décrivons un ensemble de distributions de possibilité qui résument différents types d'intervalles statistiques. Ensuite, nous proposons un cadre de travail pour vérifier si un modèle, construit à partir de données, respecte les propriétés de recouvrement requises par les intervalles de prédiction. Nous introduisons aussi deux mesures pour comparer des modèles de prédiction d'intervalle qui ont des tailles moyennes et des taux de recouvrement différents. A partir de nos travaux sur les intervalles statistiques (et leurs distributions de possibilité associés), nous présentons une nouvelle méthode pour induire des intervalles de prédictions bornés pour des méthodes de régression des moindres carrés non paramétriques sans assumer que la prédiction est non biaisée et que les erreurs sont homoscédastiques. Nos intervalles de prédiction sont construits en utilisant des intervalles de tolérances sur les erreurs dans le voisinage du point à prédire. Pour cela, nous décrivons une méthode de sélection de voisinage à taille fixe ou de voisinage à taille variable dépendant de la quantité d'informations autour du point. Nous obtenons un algorithme qui induit, dans la majorité des cas, les intervalles de prédiction fiables les plus petits possibles. Les méthodes que nous proposons sont comparées avec les méthodes les plus connues au niveau théorique et au niveau pratique. Une évaluation est effectuée sur neuf bases de données. La taille, l'efficacité, la fiabilité et la précision des intervalles prédits sont comparés. Ces expérimentations montrent que nos approches sont significativement plus précises et fiables que les autres. Enfin nous appliquons nos méthodes au problème de la prédiction de trajectoires d'avions et nous comparons les résultats avec ceux des méthodes classiques et des modèles physiques.

Ce travail résume mes résultats scientifiques obtenus depuis mon arrivée à l'IECL. Le thème général est l'utilisation de méthodes géométriques pour l'étude de systèmes mécaniques complexes (non linéaires, de dimension infinie). La première partie concerne la commande de systèmes quantiques fermés, décrits par une équation de Schrödinger bilinéaire. L'utilisation de méthodes de géométrie différentielle (de dimension finie) sur des approximations de Galerkin bien choisies ont permis d'obtenir les premiers résultats génériques de contrôlabilité approchée pour l'équation de Schrödinger bilinéaire. La deuxième partie traite de la locomotion d'un nageur isolé dans un fluide parfait en écoulement potentiel. Sous l'action de forces internes, le nageur peut modifier sa forme et agir sur le fluide qui par réaction agit sur le nageur et peut modifier sa vitesse. L'utilisation de résultats classiques de dimension finie a permis de montrer qu'un nageur générique pouvait suivre (position du centre de masse et orientation) une trajectoire arbitraire, avec une précision arbitraire, en restant arbitrairement proche d'une forme de référence donnée. La troisième partie traite de l'optimisation de la stratégie de conduite d'un véhicule, dans le but de minimiser sa consommation d'énergie.

Le travail développé dans ce manuscrit porte sur la synchronisation des systèmes chaotiques. Il est articulé autour de deux axes principaux : la synthèse d'observateur et la détection de modes. Dans un premier temps, quelques rappels sur le chaos et les principales architectures de systèmes de chi ffrement chaotiques sont e ffectués. Ensuite, nous montrons comment les systèmes chaotiques à non linéarité polynomiale ou affi nes à commutation peuvent se réécrire sous forme LPV polytopique. Une revue des principaux résultats sur la synthèse d'observateurs LPV polytopiques reposant sur l'utilisation des LMI est faite. Une extension des résultats aux observateurs polytopiques à entrées inconnues, à la fois dans le cas déterministe, bruité ou incertain est proposée. Ces observateurs assurent la synchronisation du chaos et donc le déchiff rement dans les systèmes de chiff rement "modulation paramétrique", "commutation chaotique", "transmission à deux canaux" et "chiff rement par inclusion". Pour les systèmes a ffines à commutation utilisés en tant que générateur du chaos, le cas où l'état discret n'est pas accessible est considéré. Une présentation unifi ée des méthodes fondées sur les espaces de parité, proposées dans la littérature pour les systèmes linéaires et affi nes à commutation à temps discret, est réalisée. Le problème de discernabilité fait l'objet d'une étude approfondie. Une approche pour estimer les retards variables des systèmes a ffines et affi nes à commutation à temps discret, formulée en termes de détection de modes, est proposée en tant que solution à l'estimation de retard pour le chiff rement par injection de retard.

Parce que la robotique collaborative vise à libérer les robots des barrières physiques les séparant des opérateurs humains, de nouveaux défis apparaissent autour de la sécurité de ces derniers. S'il est possible de diminuer la dangerosité des robots en amont de leur conception, les logiciels qui les contrôlent doivent impérativement intégrer des mesures de sécurité, afin d'être compatibles avec des environnements humains dynamiques. Les algorithmes classiques de planification de trajectoire nécessitant de lourds calculs, il est avantageux de modifier la trajectoire en temps réel pour l'adapter à l'environnement dangereux. Dans ce projet de recherche, un algorithme de cinématique inverse, sous forme de problème d'optimisation, est utilisé afin de générer la commande du robot à partir d'une trajectoire définie hors-ligne. L'ajout de contraintes de sécurité à ce problème est particulièrement étudié : dans un premier temps, l'indice de manipulabilité, qui traduit la distance du robot à une configuration singulière, est considéré. Ainsi, il doit être maximisé tout au long de la trajectoire afin d'assurer la meilleure mobilité disponible. Dans un deuxième temps, le facteur humain a été intégré par la prise en compte du confort de celui-ci : afin de réduire le stress éprouvé par l'opérateur face à un robot aux mouvements imprévisibles, on s'assure de minimiser la distance entre l'effecteur et le regard de l'humain pour garantir une plus grande visibilité de la tâche. Dans les deux cas, nous avons présenté une formulation originale de ces critères afin de les intégrer dans le problème d'optimisation. Par ailleurs la contrainte d'évitement d'obstacles a aussi été utilisée, de même que la relaxation de la trajectoire, qui permet au robot de dévier un peu de cette dernière pendant une portion de la durée de la tâche. Enfin des tests en simulation et avec le robot réel Baxter de Rethink Robotics ont permis de valider notre approche et de vérifier les performances en conditions réelles, en utilisant une caméra RGB-D et un logiciel de détection d'humain en temps réel. / Abstract : Because collaborative robots are aimed at working in the vicinity of human workers without physical security fences, they bring new challenges about security. Even if robots can be conceived to be less harmful, their software has to integrate security features in order to be suitable for dynamic human environments. Since classical path planning algorithms require heavy calculations, it is interesting to modify the trajectory in real time to adapt it to the dangerous environment. In this research project, an inverse kinematics solver, in the form of an optimization problem, is used to generate the command of the robot to follow a trajectory defined offline. The addition of security constraints is studied: first, the manipulability index, which reflects the distance of the robot to singular configurations, is considered. Thus, it should be maximized all along the trajectory to ensure the best mobility available. Then the human is integrated by taking into account its comfort: in order to reduce the stress of working near an unpredictable moving robot, the distance between the end-effector and the human gaze is minimized to guarantee a greater visibility of the task. In both cases, we have presented a new formulation of those criteria to integrate them into the optimization problem. Moreover, the collision avoidance constraint is used, as well as the trajectory relaxation, which allows the robot to deviate from its trajectory for a certain amount of time during the task. Finally tests in simulation and with the real Baxter robot from Rethink Robotics validated our approach and the performance has been evaluated in real conditions, using a RGB-D camera and a real time human tracker software.

La thèse porte sur des problèmes de contrôle optimal où la dynamique est donnée par des équations différentielles avec mémoire. Pour ces problèmes d'optimisation, des conditions d'optimalité sont établies ; celles du second ordre constituent une part importante des résultats de la thèse. Dans le cas - sans mémoire - des équations différentielles ordinaires, les conditions d'optimalité standards sont renforcées en ne faisant intervenir que les multiplicateurs de Lagrange pour lesquels le principe de Pontryaguine est satisfait. Cette restriction à un sous-ensemble des multiplicateurs représente un défi dans l'établissement des conditions nécessaires et permet aux conditions suffisantes d'assurer l'optimalité locale dans un sens plus fort. Les conditions standards sont d'autre part étendues au cas - avec mémoire - des équations intégrales. Les contraintes pures sur l'état du problème précédent ont été conservées et nécessitent une étude spécifique à la dynamique intégrale. Une autre forme de mémoire dans l'équation d'état d'un problème de contrôle optimal provient d'un travail de modélisation avec l'optimisation thérapeutique comme application médicale en vue. La dynamique de populations de cellules cancéreuses sous l'action d'un traitement est ramenée à des équations différentielles à retards ; le comportement asymptotique en temps long du modèle structuré en âge est également étudié.

Une approche fondamentale pour la résolution de problémes de contrôle optimal est basée sur le principe de programmation dynamique. Ce principe conduit aux équations d'Hamilton-Jacobi, qui peuvent être résolues numériquement par des méthodes classiques comme la méthode des différences finies, les méthodes semi-lagrangiennes, ou les schémas antidiffusifs. À cause de la discrétisation de l'espace d'état, la dimension des problèmes de contrôle pouvant être abordés par ces méthodes classiques est souvent limitée à 3 ou 4. Ce phénomène est appellé malédiction de la dimension. Cette thèse porte sur les méthodes numériques max-plus en contôle optimal deterministe et ses analyses de convergence. Nous étudions et developpons des méthodes numériques destinées à attenuer la malédiction de la dimension, pour lesquelles nous obtenons des estimations théoriques de complexité. Les preuves reposent sur des résultats de théorie de Perron-Frobenius non linéaire. En particulier, nous étudions les propriétés de contraction des opérateurs monotones et non expansifs, pour différentes métriques de Finsler sur un cône (métrique de Thompson, métrique projective d'Hilbert). Nous donnons par ailleurs une généralisation du "coefficient d'ergodicité de Dobrushin" à des opérateurs de Markov sur un cône général. Nous appliquons ces résultats aux systèmes de consensus ainsi qu'aux équations de Riccati généralisées apparaissant en contrôle stochastique.

Le premier chapitre de ce mémoire porte sur l'étude des minimum forts pour des problèmes de contrôle optimal gouvernés par des EDP semi-linéaires elliptiques et paraboliques avec contraintes intégrales sur l'état final. Le second chapitre porte sur l'étude du problème de temps minimal pour un système de type chemostat en présence de points singuliers stationnaires. On y étudie également un problème de contrôle optimal pour un système chemostat avec deux espèces en compétition et qui comporte une courbe de non-contrôlabilité. Le troisième chapitre s'intéresse à la synthèse d'un contrôle optimal par retour d'état pour un problème de temps minimal issu d'un système fed-batch, notamment en présence d'un contrôle impulsionnel. Le quatrième chapitre étudie deux problèmes de contrôle optimal sous contraintes d'état périodiques. Enfin, le dernier chapitre traite de problèmes d'optimisation de forme géométriques sous contraintes de convexité. Cette dernière est formulée comme une contrainte semi-définie, ce qui permet ensuite d'utiliser la programmation SDP pour minimiser la fonction coût.