This thesis deals with the topic of min-max formulations of robust model predictive control problems. The sets involved in guaranteeing robust feasibility of the min-max program in the presence of state constraints are of particular interest, and expanding the applicability of well understood solvers of linearly constrained quadratic min-max programs is the main focus. To this end, a generalisation for the set of uncertainty is considered: instead of fixed bounds on the uncertainty, state- and input-dependent bounds are used. To deal with state- and input dependent constraint sets a framework for a particular class of set-valued maps is utilised, namely parametrically convex set-valued maps. Relevant properties and operations are developed to accommodate parametrically convex set-valued maps in the context of robust model predictive control. A quintessential part of this work is the study of fundamental properties of piecewise polyhedral set-valued maps which are parametrically convex, we show that one particular property is that their combinatorial structure is constant. The study of polytopic maps with a rigid combinatorial structure allows the use of an optimisation based approach of robustifying constrained control problems with probabilistic constraints. Auxiliary polytopic constraint sets, used to replace probabilistic constraints by deterministic ones, can be optimised to minimise the conservatism introduced while guaranteeing constraint satisfaction of the original probabilistic constraint. We furthermore study the behaviour of the maximal robust positive invariant set for the case of scaled uncertainty and show that this set is continuously polytopic up to a critical scaling factor, which we can approximate a-priori with an arbitrary degree of accuracy. Relevant theoretical statements are developed, discussed and illustrated with examples.

Nous introduisons d'abord la classe des graphes $k$-dégénérés qui est souvent utilisée pour modéliser des grands graphes épars issus du monde réel. Nous proposons de nouveaux algorithmes d'énumération pour ces graphes. En particulier, nous construisons un algorithme énumérant tous les cycles simples de tailles fixés dans ces graphes, en temps optimal.Nous proposons aussi un algorithme dont la complexité dépend de la taille de la solution pour le problème d'énumération des cliques maximales de ces graphes. Dans un second temps nous considérons les graphes en tant que systèmes distribués et nous nous intéressons à des questions liées à la notion de couplage lorsqu’aucune supposition n’est faite sur l'état initial du système, qui peut donc être correct ou incorrect. Dans ce cadre nous proposons un algorithme retournant une deux tiers approximation du couplage maximum.Nous proposons aussi un algorithme retournant un couplage maximal quand les communications sont restreintes de telle manière à simuler le paradigme du passage de message. Le troisième objet d'étude n'est pas directement lié à l'algorithmique de graphe, bien que quelques techniques classiques de ce domaine soient utilisées pour obtenir certains de nos résultats.Nous introduisons et étudions certaines familles de polytopes, appelées Zonotopes Primitifs, qui peuvent être décrits comme la somme de Minkowski de vecteurs primitifs. Nous prouvons certaines propriétés combinatoires de ces polytopes et illustrons la connexion avec le plus grand diamètre possible de l'enveloppe convexe de points à coordonnées entières à valeurs dans$[k]$, en dimension $d$. Dans un second temps,nous étudions des paramètres de petites instances de Zonotopes Primitifs, tels que leur nombre de sommets, entre autres. / We start by studying the class of $k$-degenerate graphs which are often used to model sparse real-world graphs. We focus one numeration questions for these graphs. That is,we try and provide algorithms which must output, without duplication, all the occurrences of some input subgraph. We investigate the questions of finding all cycles of some givensize and all maximal cliques in the graph. Ourtwo contributions are a worst-case output sizeoptimal algorithm for fixed-size cycleenumeration and an output sensitive algorithmfor maximal clique enumeration for this restricted class of graphs. In a second part weconsider graphs in a distributed manner. Weinvestigate questions related to finding matchings of the network, when no assumptionis made on the initial state of the system. Thesealgorithms are often referred to as selfstabilizing.Our two main contributions are analgorithm returning an approximation of themaximum matching and a new algorithm formaximal matching when communication simulates message passing. Finally, weintroduce and investigate some special families of polytopes, namely primitive zonotopes,which can be described as the Minkowski sumof short primitive vectors. We highlight connections with the largest possible diameter ofthe convex hull of a set of points in dimension d whose coordinates are integers between 0 and k.Our main contributions are new lower bounds for this diameter question as well as descriptions of small instances of these objects.

Cette thèse présente une étude des applications des groupes de réflexion finis aux problems liés aux réseaux bidimensionnels et aux polytopes tridimensionnels. Plusieurs familles de fonctions orbitales, appelées fonctions orbitales de Weyl, sont associées aux groupes de réflexion cristallographique. Les propriétés exceptionnelles de ces fonctions, telles que l’orthogonalité continue et discrète, permettent une analyse de type Fourier sur le domaine fondamental d’un groupe de Weyl affine correspondant. Dans cette considération, les fonctions d’orbite de Weyl constituent des outils efficaces pour les transformées discrètes de type Fourier correspondantes connues sous le nom de transformées de Fourier–Weyl. Cette recherche limite notre attention aux fonctions d’orbite de Weyl symétriques et antisymétriques à deux variables du groupe de réflexion cristallographique A2. L’objectif principal est de décomposer deux types de transformations de Fourier–Weyl du réseau de poids correspondant en transformées plus petites en utilisant la technique de division centrale. Pour les cas non cristallographiques, nous définissons les indices de degré pair et impair pour les orbites des groupes de réflexion non cristallographique avec une symétrie quintuple en utilisant un remplacement de représentation-orbite. De plus, nous formulons l’algorithme qui permet de déterminer les structures de polytopes imbriquées. Par ailleurs, compte tenu de la pertinence de la symétrie icosaédrique pour la description de diverses molécules sphériques et virus, nous étudions la brisure de symétrie des polytopes doubles de type non cristallographique et des structures tubulaires associées. De plus, nous appliquons une procédure de stellation à la famille des polytopes considérés. Puisque cette recherche se concentre en partie sur les fullerènes icosaédriques, nous présentons la construction des nanotubes de carbone correspondants. De plus, l’approche considérée pour les cas non cristallographiques est appliquée aux structures cristallographiques. Nous considérons un mécanisme de brisure de symétrie appliqué aux polytopes obtenus en utilisant les groupes Weyl tridimensionnels pour déterminer leurs extensions structurelles possibles en nanotubes. / This thesis presents a study of applications of finite reflection groups to the problems related to two-dimensional lattices and three-dimensional polytopes. Several families of orbit functions, known as Weyl orbit functions, are associated with the crystallographic reflection groups. The exceptional properties of these functions, such as continuous and discrete orthogonality, permit Fourier-like analysis on the fundamental domain of a corresponding affine Weyl group. In this consideration, Weyl orbit functions constitute efficient tools for corresponding Fourier-like discrete transforms known as Fourier–Weyl transforms. This research restricts our attention to the two-variable symmetric and antisymmetric Weyl orbit functions of the crystallographic reflection group A2. The main goal is to decompose two types of the corresponding weight lattice Fourier–Weyl transforms into smaller transforms using the central splitting technique. For the non-crystallographic cases, we define the even- and odd-degree indices for orbits of the non-crystallographic reflection groups with 5-fold symmetry by using a representation-orbit replacement. Besides, we formulate the algorithm that allows determining the structures of nested polytopes. Moreover, in light of the relevance of the icosahedral symmetry to the description of various spherical molecules and viruses, we study symmetry breaking of the dual polytopes of non-crystallographic type and related tube-like structures. As well, we apply a stellation procedure to the family of considered polytopes. Since this research partly focuses on the icosahedral fullerenes, we present the construction of the corresponding carbon nanotubes. Furthermore, the approach considered for the non-crystallographic cases is applied to crystallographic structures. We consider a symmetry-breaking mechanism applied to the polytopes obtained using the three-dimensional Weyl groups to determine their possible structural extensions into nanotubes.

No description available.

En analyse de tolérances géométriques, une approche consiste à manipuler des polyèdres de R' issus d’ensembles de contraintes linéaires. La position relative entre deux surfaces quelconques d'un mécanisme est déterminée par des opérations (somme de Minkowski et intersection) sur ces polyèdres. Ces polyèdres ne sont pas bornés selon les déplacements illimités dus aux degrés d’invariance des surfaces et aux degrés de liberté des liaisons.Dans une première partie sont introduits des demi-espaces "bouchons" destinés à limiter ces déplacements afin de transformer les polyèdres en polytopes. Cette méthode implique de maîtriser l’influence des demi-espaces bouchons sur la topologie des polytopes résultants. Ceci est primordial pour garantir la traçabilité de ces demi-espaces dans le processus d’analyse de tolérances.Une seconde partie dresse un inventaire des problématiques de mise en oeuvre numérique des polytopes. L’une d’entre elles repose sur le choix d’une configuration de calcul (point et base d’expression, coefficients d’homogénéisation) pour définir un polytope. Après avoir montré que le changement de configuration de calcul est une transformation affine, plusieurs stratégies de simulations sont déclinées afin d’appréhender les problèmes de précision numérique et de temps de calculs. / In geometric tolerancing analysis area, a classical approach consists in handling polyhedrons coming from sets of linear constraints. The relative position between any two surfaces of a mechanism is determined by operations (Minkowski sum and intersection) on these polyhedrons. The polyhedrons are generally unbounded due to the inclusion of degrees of invariance for surfaces and degrees of freedom for joints defining theoretically unlimited displacements.In a first part are introduced the cap half-spaces to limit these displacements in order to transform the polyhedron into polytopes. This method requires controlling the influence of these additional half-spaces on the topology of calculated polytopes. This is necessary to ensure the traceability of these half-spaces through the tolerancing analysis process.A second part provides an inventory of the issues related to the numerical implementation of polytopes. One of them depends on the choice of a computation configuration (expression point and base, homogenization coefficients) to define a polytope. After proving that the modification of a computation configuration is an affine transformation, several simulation strategies are listed in order to understand the problems of numerical precision and computation time.

Dans cette thèse, nous étudions l'enveloppe convexe des arbres binaires à racine sur n feuilles.Ce sont les arbres de Huffman dont les feuilles sont labellisées par n caractères. à chaque arbre de Huffman T de n feuilles, nous associons un point xT , appelé point de Huffman, dans l'espace Qn où xT est le nombre d'arêtes du chemin reliant la feuille du ième caractère et la racine.L'enveloppe convexe des points de Huffman est appelé Huffmanoèdre. Les points extrêmes de ce polyèdre sont obtenus dans un premier temps en utilisant l'algorithme d'optimisation qui est l'algorithme de Huffman. Ensuite, nous décrivons des constructions de voisinages pour un point de Huffman donné. En particulier, une de ces constructions est principalement basée sur la construction des sommets adjacents du Permutoèdre. Puis, nous présentons une description partielle du Huffmanoèdre contenant en particulier une famille d'inégalités définissant des facettes dont les coefficients, une fois triés, forment une suite de Fibonacci. Cette description bien que partielle nous permet d'une part d'expliquer la plupart d'inégalités définissant des facettes du Huffmanoèdre jusqu'à la dimension 8, d'autre part de caractériser les arbres de Huffman les plus profonds, i.e. une caractérisation de tous les facettes ayant au moins un plus profond arbre de Huffman comme point extrême. La contribution principale de ce travail repose essentiellement sur les liens que nous établissons entre la construction des arbres et la génération des facettes / In this thesis, we study the convex hull of full binary trees of n leaves. There are the Huffman trees, the leaves of which are labeled by n characters. To each Huffman tree T of n leaves, we associate a point xT , called Huffman point, in the space Qn where xT i is the lengths of the path from the root node to the leaf node marked by the ith character. The convex hull of the Huffman points is called Huffmanhedron. The extreme points of the Huffmanhedron are first obtained by using the optimization algorithm which is the Huffman algorithm. Then, we describe neighbour constructions given a Huffman point x. In particular, one of these constructions is mainly based on the neighbour construction of the Permutahedron. Thereafter, we present a partial description of the Huffmanhedron particularly containing a family of inequalities-defining facets whose coeficients follows in some way the law of the well-known Fibonacci sequence. This description allows us, on the one hand, to explain the most of inequalities-defining facets of the Huffmanhedron up to the dimension 8, on the other hand, to characterize the Huffman deepest trees, i.e a linear characterization of all the facets containing at least a Huffman deepest tree as its extreme point. The main contribution of this work is essentially base on the link what we establish between the Huffman tree construction and the facet generation.

Dans ce mémoire, nous avons proposé une nouvelle approche pour la stabilisation des polytopes de systèmes SISO LTI avec un contrôleur d’ordre fixe. En utilisant le théorème des segments étendus, nous avons montré que, pour stabiliser un polytope de systèmes LTI, il suffit de stabiliser simultanément tous ses sommets en considérant une condition supplémentaire associée à ces derniers. Nous avons présenté également dans ce mémoire des méthodes originales pour la synthèse des contrôleurs simultanés en combinant les techniques polynomiales et l’optimisation linéaire. Avec les méthodes de synthèse proposées, nous avons montré non seulement que le contrôleur stabilise simultanément les sommets du polytope de systèmes (commande simultanée), mais également tous les systèmes appartenant au polytope (commande robuste). Il s’agit donc de contrôleur simultané et robuste pour les polytopes de systèmes. Avant de pouvoir énoncer des résultats concernant la commande simultanée de l’ensemble des segments d’un polytope de systèmes, nous avons étudié la commande d’un segment de systèmes avec un contrôleur LTI. Ce segment de systèmes est défini par les deux systèmes situés à chacune de ses extrémités et par un paramètre appartenant à un intervalle donné. La question de la stabilisation de cette classe de systèmes incertains a été formulée comme celle d’un problème de commande simultanée de deux systèmes situés aux extrémités avec une contrainte d’égalité des parties paires de chacun des deux polynômes caractéristiques en boucle fermée. Des conditions d’existence d’un régulateur stabilisant un segment de systèmes ont été données en utilisant deux critères de stabilité polynomiaux : le critère d’Hermite-Fujiwara et le critère d’Hermite-Biehler. Les résultats obtenus pour la commande simultanée d’un segment de systèmes ont été étendus à la stabilisation d’un polytope de systèmes. Ce problème a été réduit à la stabilisation des sommets du polytope avec un contrôleur simultané générant des polynômes caractéristiques en boucle fermée ayant la même partie paire (ou impaire). Des conditions d’existence de ces contrôleurs simultanés robustes d’ordre fixe sont données en utilisant les deux critères de stabilité mentionnés ci-dessus. Des algorithmes de synthèse sont également développés pour calculer ces régulateurs / In this manuscript, a new approach is proposed for the stabilization of polytopes of SISO LTI systems with a fixed order controller. Using the extended segment theorem, we have shown that to stabilize a polytope of LTI systems, it is sufficient to simultaneously stabilize all its vertices by considering an additional condition associated with them. In this paper, we have also presented original methods for the synthesis of simultaneous controllers by combining polynomial techniques and linear optimization. With the proposed synthesis methods, we have shown not only that the controller simultaneously stabilizes the vertices of the system polytope (simultaneous control), but also all systems belonging to the polytope (robust control). It is therefore a simultaneous and robust controller for system polytopes. Before stating results concerning the simultaneous control of all the segments of a polytope of systems, we have studied the control of a segment of systems with an LTI controller. This segment of systems is defined by the two systems located at each of its ends and by a parameter belonging to a given interval. The question of the stabilization of this class of uncertain systems has been formulated as that of a problem of simultaneous control of two systems located at the ends with an equal constraint of the even parts of each of the two characteristic polynomials in closed loop. Conditions of existence of a stabilizing controller for a segment of systems have been given using two polynomial stability criteria : the Hermite-Fujiwara criterion and the Hermite-Biehler criterion. The results obtained for the simultaneous control of a segment of systems have been extended to the stabilization of a polytope of systems. This problem has been reduced to the stabilization of the vertices of the polytope with a simultaneous controller generating closed loop characteristic polynomials having the same even (or odd) part. The existence conditions of these robust, fixed-order and simultaneous controllers are given using the two stability criteria mentioned above. Synthesis algorithms are also developed to design these controllers

Cette thèse traite du problème de la chute de robots humanoïdes. L’étude consiste à découpler la stratégie de chute en une phase de pré-impact et une phase de post-impact. Dans la première, une solution géométrique permet au robot de choisir des points d’impact dans un environnement encombré. Pour ce faire, le robot réadapte sa posture tout en évident les singularités de chute et en préparant le seconde phase. La phase de post-impact utilise une commande par Programmation Quadratique (QP) qui permet d’adapter les gains Proportionnels-Dérivés (PD)des moteurs en ligne, ceci afin d’obtenir de la compliance dans les articulations. L’approche consiste à incorporer les gains de raideur et d’amortissement dans le vecteur d’optimisation du QP avec les variables habituelles que sont l’accélération articulaire et les forces de contact. Les contraintes ont été adaptées à ce nouveau QP. Enfin,comme la solution est locale, une commande de modèle prédictif sur un modèle simplifié du robot. A chaque pas du développement, plusieurs expériences et simulations ont été effectuées. / This thesis deals with the problem of humanoid falling with a decoupled strategy consisting of a pre-impactand a post-impact stages. In the pre-impact stage, geometrical reasoning allows the robot to choose appropriateimpact points in the surrounding environment –that can be unstructured and may contain cluttered obstacles,and to adopt a posture to reach them while avoiding impact singularities and preparing for the post-impact. Thepost-impact stage uses a quadratic program controller that adapts on-line the joint proportional-derivative (PD)gains to make the robot compliant, i.e. to absorb post-impact dynamics, which lowers possible damage risks.We propose a new approach incorporating the stiffness and damping gains directly as decision variables in theQP along with the usually-considered variables that are the joint accelerations and contact forces. By doing so,various constraints can be added to the QP. Finally, since the gain adaptation is local, we added a preview ona time-horizon for more optimal gain adaptation based on model reduction. At each step of the development,several experiments on the humanoid robot HRP-4 in a full-dynamics simulator are presented and discussed.

In the dissertation the solution approaches for different fuzzy optimization problems are presented. The single-level optimization problem with fuzzy objective is solved by its reformulation into a biobjective optimization problem. A special attention is given to the computation of the membership function of the fuzzy solution of the fuzzy optimization problem in the linear case. Necessary and sufficient optimality conditions of the the convex nonlinear fuzzy optimization problem are derived in differentiable and nondifferentiable cases. A fuzzy optimization problem with both fuzzy objectives and constraints is also investigated in the thesis in the linear case. These solution approaches are applied to fuzzy bilevel optimization problems. In the case of bilevel optimization problem with fuzzy objective functions, two algorithms are presented and compared using an illustrative example. For the case of fuzzy linear bilevel optimization problem with both fuzzy objectives and constraints k-th best algorithm is adopted.

Le polytope des m-sous-espaces est défini comme l'enveloppe convexe des vecteurs caractéristiques de tous les sous-espaces de dimension m d'un espace affin fini. Le cas particulier du polytope des hyperplans a été étudié par Maurras (1993) et Anglada et Maurras (2003), qui ont obtenu une description complète des facettes. Le polytope général des m-sous-espaces que nous considérons possède une structure plus complexe, notamment concernant les facettes. Néanmoins, nous établissons dans cette thèse plusieurs familles de facettes. Nous caractérisons également complètement le groupe des automorphismes du polytope ainsi que l'adjacence des sommets du polytope des m-sous-espaces. Un tangle est un ensemble d'hyperplans d'un espace affin contenant un hyperplan par classe d'hyperplans parallèles. Anglada et Maurras ont montré que les tangles définissent des facettes du polytope des hyperplans et que toutes les facettes de ce polytope proviennent de tangles. Nous tentons d'établir une généralisation de ce résultat. Nous élaborons une classification des tangles en familles pour de petites dimensions d'espaces affins. / Doctorat en sciences, Spécialisation mathématiques / info:eu-repo/semantics/nonPublished