Ce manuscrit présente des résultats de recherche concernant une certaine classe de systèmes hybrides. Les systèmes hybrides peuvent être utilises pour la modélisation de systèmes physiques complexes et hétérogènes dont l’évolution dans le temps présente des phénomènes discrets, tels que les commutations des convertisseurs ou les impacts des systèmes mécaniques. De la même manière, la théorie hybride peut être utilisée pour concevoir des contrôleurs hybrides, en général plus performants par rapport aux contrôleurs a temps continu.Dans ce cadre, les résultats de ce manuscrit peuvent être divises en trois parties. D'abord des résultats de stabilité par rapport à un indice de performance de type Hinfini sont présentes pour une classe plutôt large de systèmes hybrides. Ensuite, nous introduisons de nouvelles architectures de contrôleurs hybrides pour les systèmes à temps continu caractérisées par le fait que leur état peut être réinitialisé en fonction de la trajectoire. Enfin, nous présentons une technique de synthèse convexe pour la conception d'un contrôleur hybride multi-objectif. La comparaison avec les résultats classique met en évidence les avantages en termes de performance par rapport aux contrôleurs a temps continu classiques, tout en préservant la propriété de robustesse et la simplicité de conception.Bien que la théorie hybride soit en plein développement, ces travaux généralisent certains résultats existants, en améliorant la simplicité d’implémentation des solutions grâce à l'utilisation de la programmation semi-definie. En plus les architectures de contrôleurs hybrides présentées ont l'avantage de simplifier la généralisation de quelques résultats classiques concernant la synthèse optimale par rapport à des indices de performance communs. / This dissertation presents some results on hybrid systems. Hybrid systems can be used to model complex physical and heterogeneous systems whose time evolution experiences discrete phenomena, such as commutations in electronic converters or impacts in mechanical systems. In the meantime the hybrid theory can be used to design hybrid controllers which exhibit better performance than the classical continuous-time controllers.In this context, the results in this dissertation can be divided en three parts. First, some stability results with respect to the Hinfinity performance index are presented for a wide class of hybrid controllers. Second, we introduce new hybrid controller architectures for continuous-time systems, where the state of the hybrid controller can be reinitialized depending on the trajectory of the system. Finally, we present a convex synthesis of a multiobjective hybrid controller. The comparisons with the classical results show the improvements that can be achieved with hybrid controllers, maintaining the property of robustness and simplicity of design.Although the hybrid theory is in full development, this work generalizes some existing results by improving the simplicity of their usage by means of semidefinite programming tools. Moreover some hybrid architectures are able to generalize some classic results regarding the optimal synthesis with respect to popular performance indexes.

Cette thèse est particulièrement destinée à traiter deux types de problèmes : clustering et l'alignement multiple de séquence. Notre objectif est de résoudre de manière satisfaisante ces problèmes globaux et de tester l'approche de la Programmation DC et DCA sur des jeux de données réelles. La thèse comporte trois parties : la première partie est consacrée aux nouvelles approches de l'optimisation non convexe. Nous y présentons une étude en profondeur de l'algorithme qui est utilisé dans cette thèse, à savoir la programmation DC et l'algorithme DC (DCA). Dans la deuxième partie, nous allons modéliser le problème clustering en trois sous-problèmes non convexes. Les deux premiers sous-problèmes se distinguent par rapport au choix de la norme utilisée, (clustering via les normes 1 et 2). Le troisième sous-problème utilise la méthode du noyau, (clustering via la méthode du noyau). La troisième partie sera consacrée à la bio-informatique. On va se focaliser sur la modélisation et la résolution de deux sous-problèmes : l'alignement multiple de séquence et l'alignement de séquence d'ARN par structure. Tous les chapitres excepté le premier se terminent par des tests numériques. / This Ph.D. thesis is particularly intended to treat two types of problems : clustering and the multiple alignment of sequence. Our objective is to solve efficiently these global problems and to test DC Programming approach and DCA on real datasets. The thesis is divided into three parts : the first part is devoted to the new approaches of nonconvex optimization-global optimization. We present it a study in depth of the algorithm which is used in this thesis, namely the programming DC and the algorithm DC ( DCA). In the second part, we will model the problem clustering in three nonconvex subproblems. The first two subproblems are distinguished compared to the choice from the norm used, (clustering via norm 1 and 2). The third subproblem uses the method of the kernel, (clustering via the method of the kernel). The third part will be devoted to bioinformatics, one goes this focused on the modeling and the resolution of two subproblems : the multiple alignment of sequence and the alignment of sequence of RNA. All the chapters except the first end in numerical tests.

En informatique, les images sont numériques et donc composées de pixels en 2D et de voxels en 3D. Dans une scène virtuelle 3D, il est impossible de manipuler directement les objets comme des ensembles de voxels en raison du trop gros volume de données. Les objets sont alors polyédrisés, c'est-à-dire remplacés par une collection de facettes. Pour ce faire, il est primordial de savoir décider si un sous-ensemble de voxels peut être transformé en une facette dans la représentation polyédrique. Ce problème est appelé reconnaissance de plans discrets. Pour le résoudre, nous mettons en place un nouvel algorithme spécialement adapté pour les ensembles de voxels denses dans une boite englobante. Notre méthode atteint une complexité quasi-linéaire dans ce cas et s'avère efficace en pratique. En parallèle, nous nous intéressons à un problème algorithmique annexe intervenant dans notre méthode de reconnaissance de plans discrets. Il s'agit de calculer les deux enveloppes convexes des points de Z2 contenus dans un domaine vertical borné et situés de part et d'autre d'une droite quelconque. Nous proposons une méthode de complexité optimale et adaptative pour calculer ces enveloppes convexes. Nous présentons le problème de manière détournée : déterminer le nombre rationnel à dénominateur borné qui approxime au mieux un nombre réel donné. Nous établissons le lien entre ce problème numérique et son interprétation géométrique dans le plan. Enfin, nous proposons indépendamment un nouvel algorithme pour calculer l'épaisseur d'un ensemble de points dans le réseau Zd. Notre méthode est optimale en 2D et gloutonne mais efficace en dimension supérieure

.

.

Cette th'ese est consacr'ee 'a l''etude et la r'esolution de certains probl'emes non lin'eaires du traitement du signal et de l'image via l'analyse convexe. Nous proposons une 'etude variationnelle unifi'ee de probl'emes inverses et de probl'emes de d'ecomposition de signaux qui ont, jusqu''a pr'esent, 'et'e 'etudi'es individuellement en raison de leur apparente disparit'e. Dans le mod'ele adopt'e, cette famille de probl'emes est r'eduite g'en'eriquement 'a la minimisation d'une somme de deux fonctions soumises 'a certaines propri'et'es de r'egularit'e. Des r'esultats d'existence, d'unicit'e et de caract'erisation du probl'eme ainsi pos'e sont obtenus. L'op'erateur proximal, introduit par Moreau en 1962 pour les besoins de la m'ecanique, joue un rˆole essentiel dans notre analyse. Nous l'utilisons notamment pour obtenir de nouveaux sch'emas non lin'eaires de d'ecomposition de signaux. Cet outil est par ailleurs au coeur de l'algorithme explicite-implicite que nous proposons pour la r'esolution du probl'eme g'en'erique. Ce cadre th'eorique est appliqu'e 'a l'analyse de signaux et 'a la restauration d'images. Les probl'emes de restauration que nous abordons sont pos'es sur des trames et notre approche permet de prendre en compte des contraintes de parcimonie ou de mod'eliser des formulations bay'esiennes avec des connaissances a priori sur les lois des coefficients de la d'ecomposition. Des r'esultats num'eriques sont fournis.

L’efficacité des méthodes d’optimisation modernes, associée à l’augmentation des ressources informatiques, a conduit à la possibilité d’utiliser ces algorithmes d’optimisation en temps réel agissant dans des rôles critiques. Cependant, cela ne peut se produire sans porter une certaine attention à la validité de ces algorithmes. Ce doctorat traite de la vérification formelle des algorithmes d'optimisation convexe lors qu'ils sont utilisés pour la guidance de systèmes dynamiques. En outre, nous démontrons comment les preuves théoriques des algorithmes d'optimisation en temps réel peuvent être utilisées pour décrire les propriétés fonctionnelles au niveau du code, les rendant ainsi accessibles à la communauté des méthodes formelles. / The efficiency of modern optimization methods, coupled with increasing computational resources, has led to the possibility of real-time optimization algorithms acting in safety critical roles. However, this cannot happen without addressing proper attention to the soundness of these algorithms. This PhD thesis discusses the formal verification of convex optimization algorithms with a particular emphasis on receding-horizon controllers. Additionally, we demonstrate how theoretical proofs of real-time optimization algorithms can be used to describe functional properties at the code level, thereby making it accessible for the formal methods community.

Cette thèse s'inscrit dans le cadre de la gestion d'énergie d'un Véhicule Hybride Électrique. Pour ce type de véhicule, l'optimisation énergétique est un enjeu majeur. Cela consiste à calculer les commandes optimales minimisant la consommation énergétique du véhicule sous un nombre fini de contraintes. Deux types de méthodes peuvent être utilisées pour résoudre ce problème d'optimisation. La première méthode et la plus utilisée, la méthode numérique, utilisant des modèles cartographiques basés sur des données. Elle présente deux inconvénients majeurs: temps de calcul et mémoire importants. La deuxième méthode, appelée analytique, qui permet de remédier à ces deux problèmes, a été utilisée dans cette thèse. Plus l'architecture du véhicule devient complexe (plusieurs machines électriques, moteur thermique, élévateur de tension), plus l'intérêt de cette approche sera important. La méthodologie analytique, proposée dans cette thèse, est composée principalement de trois étapes : la modélisation convexe, le calcul analytique des commandes et la validation des commandes analytiques sur un simulateur de véhicule. Cette méthodologie a été appliquée sur les trois configurations possibles du véhicule étudié : parallèle, bi-parallèle et série. Finalement, l'ajout de l'élévateur de tension dans la gestion d'énergie ainsi que l'étude de son impact sur la consommation énergétique du véhicule sont présentés dans le dernier chapitre. Les résultats obtenus en simulation montrent que la méthode analytique a permis de réduire considérablement le temps de calcul tout en ayant une sous-optimalité très faible. / This thesis focuses on the energy management of Hybrid Electric Vehicle. In this type of vehicle, energy optimization is a major challenge. It consists of calculating optimal commands that minimize the vehicle’s energy consumption under a finite number of constraints. The optimization issue could be solved using a digital method or an analytical method. This choice depends on the nature of energy models that monitor the optimization criteria: analytical or maps of experimental measurements. However, this method presents numerous disadvantages. Its calculation is extremely time-consuming for instance. Therefore, the works presented in this thesis were directed in order to develop an analytical solution where the calculation is lesstime consuming. The architecture of the vehicle is complex. In fact, the vehicle contains two electrical machines, a thermal engine and a step-up. These components have all a straight impact on the vehicle’s energy consumption so several optimization variables were defining. Consequently, working on an analytical solution was a natural choice. The proposed analytical methodology consists of three steps: convex modeling, the command analytical calculation as well as the analytical command validation on a vehicle simulator. This methodology was applied to three possible configurations of the studied vehicle: parallel, biparallel and in serial. Finally, the step-up addition to the energy management as well as the study of itsimpact on the vehicle’s energy consumption are presented in the last chapter. The simulation results show that the analytical method reduces considerably the computing time and has an extremely low suboptimality.

En apprentissage automatique on a pour but d'apprendre un modèle, à partir de données, qui soit capable de faire des prédictions sur des nouvelles données (pas explorées auparavant). Pour obtenir un modèle qui puisse se généraliser sur les nouvelles données, et éviter le sur-apprentissage, nous devons restreindre le modèle. Ces restrictions sont généralement une connaissance a priori de la structure du modèle. Les premières approches considérées dans la littérature sont la régularisation de Tikhonov et plus tard le Lasso pour induire de la parcimonie dans la solution. La parcimonie fait partie d'un concept fondamental en apprentissage automatique. Les modèles parcimonieux sont attrayants car ils offrent plus d'interprétabilité et une meilleure généralisation (en évitant le sur-apprentissage) en induisant un nombre réduit de paramètres dans le modèle. Au-delà de la parcimonie générale et dans de nombreux cas, les modèles sont structurellement contraints et ont une représentation simple de certains éléments fondamentaux, comme par exemple une collection de vecteurs, matrices ou tenseurs spécifiques. Ces éléments fondamentaux sont appelés atomes. Dans ce contexte, les normes atomiques fournissent un cadre général pour estimer ce type de modèles. périodes de modèles. Le but de cette thèse est d'utiliser le cadre de parcimonie convexe fourni par les normes atomiques pour étudier une forme de parcimonie matricielle. Tout d'abord, nous développons un algorithme efficace basé sur les méthodes de Frank-Wolfe et qui est particulièrement adapté pour résoudre des problèmes convexes régularisés par une norme atomique. Nous nous concentrons ensuite sur l'estimation de la structure des modèles graphiques gaussiens, où la structure du modèle est encodée dans la matrice de précision et nous étudions le cas avec des variables manquantes. Nous proposons une formulation convexe avec une approche algorithmique et fournissons un résultat théorique qui énonce les conditions nécessaires pour récupérer la structure souhaitée. Enfin, nous considérons le problème de démixage d'un signal en deux composantes ou plus via la minimisation d’une somme de normes ou de jauges, encodant chacune la structure a priori des composants à récupérer. En particulier, nous fournissons une garantie de récupération exacte dans le cadre sans bruit, basée sur des mesures d'incohérence / The goal of machine learning is to learn a model from some data that will make accurate predictions on data that it has not seen before. In order to obtain a model that will generalize on new data, and avoid overfitting, we need to restrain the model. These restrictions are usually some a priori knowledge of the structure of the model. First considered approaches included a regularization, first ridge regression and later Lasso regularization for inducing sparsity in the solution. Sparsity, also known as parsimony, has emerged as a fundamental concept in machine learning. Parsimonious models are appealing since they provide more interpretability and better generalization (avoid overfitting) through the reduced number of parameters. Beyond general sparsity and in many cases, models are constrained structurally so they have a simple representation in terms of some fundamental elements, consisting for example of a collection of specific vectors, matrices or tensors. These fundamental elements are called atoms. In this context, atomic norms provide a general framework for estimating these sorts of models. The goal of this thesis is to use the framework of convex sparsity provided by atomic norms to study a form of matrix sparsity. First, we develop an efficient algorithm based on Frank-Wolfe methods that is particularly adapted to solve problems with an atomic norm regularization. Then, we focus on the structure estimation of Gaussian graphical models, where the structure of the graph is encoded in the precision matrix and study the case with unobserved variables. We propose a convex formulation with an algorithmic approach and provide a theoretical result that states necessary conditions for recovering the desired structure. Finally, we consider the problem of signal demixing into two or more components via the minimization of a sum of norms or gauges, encoding each a structural prior on the corresponding components to recover. In particular, we provide general exact recovery guarantees in the noiseless setting based on incoherence measures

Nous déterminons d’abord l’impact d’un plan infini réfléchissant sur l’espace occupé par une marche brownienne bidimensionnelle à un temps fixé, que nous caractérisons par le périmètre moyen de son enveloppe convexe (plus petit polygone convexe contenant toute la trajectoire). Nous déterminons également la longueur moyenne de la portion du plan visitée par le marcheur, et la probabilité de survie d’un marcheur brownien dans un secteur angulaire absorbant.Nous étudions ensuite le temps mis par un marcheur sur réseau pour visiter tous les sites d’un volume, ou une partie d’entre eux. Nous calculons la moyenne de ce temps, dit de couverture, à une dimension pour une marche aléatoire persistante. Nous déterminons également la distribution du temps de couverture et d’autres observables assimilées pour la classe des processus non compacts, qui décrivent un large spectre de recherches aléatoires.Dans un troisième temps, nous calculons et analysons la probabilité de sortie conditionnelle d’un marcheur brownien évoluant dans un intervalle se dilatant ou se contractant à vitesse constante.Enfin, nous étudions plusieurs aspects du modèle du marcheur aléatoire “affamé”, qui meurt si les visites de nouveaux sites, grâce auxquelles il engrange des ressources, ne sont pas suffisamment regulières. Nous en proposons un traitement de type champ moyen à deux dimensions, puis nous déterminons l’impact de la régénération des ressources sur les propriétés de survie du marcheur. Nous considérons finalement un modèle d’exploitation de parcelles de nourriture prenant explicitement en compte le mouvement du marcheur, qui se ramène de manière naturelle au modèle du marcheur aléatoire affamé. / We first determine the impact of an infinite reflecting wall on the space occupied by a planar Brownian motion at a fixed observation time. We characterize it by the mean perimeter of its convex hull, defined as the minimal convex polygon enclosing the whole trajectory. We also determine the mean length of the visited portion of the wall, and the survival probability of a Brownian walker in an absorbing wedge.We then study the time needed for a lattice random walker to visit every site of a confined volume, or a fraction of them. We calculate the mean value of this so-called cover time in one dimension for a persistant random walk. We also determine the distribution of the cover time and related observables for the class of non compact processes, which describes a wide range of random searches.After that, we calculate and analyze the splitting probability of a one-dimensional Brownian walker evolving in an expanding or contracting interval.Last, we study several aspects of the model of starving random walk, where the walker starves if its visits to new sites, from which it collects resources, are not regular enough. We develop a mean-field treatment of this model in two dimensions, then determine the impact of regeneration of resources on the survival properties of the walker. We finally consider a model of exploitation of food patches taking explicitly into account the displacement of the walker in the patches, which can be mapped onto the starving random walk model.