Linear optimization is concerned with maximizing, or minimizing, a linear objective function over a feasible region defined as the intersection of a finite number of hyperplanes. Pivot-based simplex methods and central-path following interior point methods are the computationally most efficient algorithms to solve linear optimization instances. Discrete optimization further assumes that some of the variables are integer-valued. This dissertation focuses on the geometric properties of the feasible region under some structural assumptions. In the first part, we consider lattice (d,k)-polytopes; that is, the convex hull of a set of points drawn from {0,1,...,k}^d, and study the largest possible diameter, delta(d,k), that a lattice (d,k)- polytope can achieve. We present novel properties and an enumeration algorithm to determine previously unknown values of delta(d,k). In particular, we determine the values for delta(3,6) and delta(5,3), and enumerate all the lattice (3,3)-polytopes achieving delta(3,3). In the second part, we consider the convex hull of all the 2^(2^d - 1) subsums of the 2^d - 1 nonzero {0,1}-valued vectors of length d, and denote by a(d) the number of its vertices. The value of a(d) has been determined until d =8 as well as asymptotically tight lower and upper bounds for loga(d). This convex hull forms a so-called primitive zonotope that is dual to the resonance hyperplane arrangement and belongs to a family that is conjectured to include lattice polytopes achieving the largest possible diameter over all lattice (d,k)-polytopes. We propose an algorithm exploiting the combinatorial and geometric properties of the input and present preliminary computational results. / Thesis / Doctor of Philosophy (PhD)

Le calcul des ensembles atteignables est une approche de facto utilisée dans de nombreuses méthodes de vérification formelles pour les systèmes hybrides. Mais le calcul exact de l'ensemble atteignable est un problème insurmontable pour de nombreux types de systèmes hybrides, soit en raison de l'indécidabilité ou de la complexité de calcul élevée. Alternativement, beaucoup de recherches ont été axées sur l'utilisation de représentations d'ensembles qui peuvent être manipulées efficacement pour calculer une surestimation suffisamment précise de l'ensemble atteignable. Les zonotopes sont une représentation utile de l'ensemble dans l'analyse de l'accessibilité en raison de leur fermeture et de leur faible complexité pour le calcul de la transformation linéaire et des opérations sommaires de Minkowski. Mais pour approximer les ensembles de temps non bornés atteignables par des invariants positifs, les zonotopes ont l'inconvénient suivant. L'efficacité d'une représentation d'ensemble pour calculer un invariant positif dépend de l'encodage efficace des directions de convergence des états vers un équilibre. Dans un système hybride affine, certaines des directions de convergence peuvent être codées par les vecteurs propres à valeur complexe des matrices de transformation. Mais la représentation zonotopique ne peut pas exploiter la structure propre complexe des matrices de transformation car elle n'a que des générateurs à valeur réelle.Par conséquent, nous étendons les zonotopes réels au domaine de valeur complexe d'une manière qui peut capturer la contraction le long de vecteurs évalués complexes. Cela donne une nouvelle représentation d'ensemble appelée zonotope complexe. Géométriquement, les zonotopes complexes représentent une classe plus large d'ensembles qui comprennent des ensembles non polytopiques ainsi que des zonotopes polytopiques. Ils conservent le mérite des zonotopes réels que nous pouvons effectuer efficacement la transformation linéaire et les opérations sommaires de Minkowski et calculer la fonction de support. De plus, nous montrons qu'ils peuvent capturer la contraction le long de vecteurs propres complexes. De plus, nous développons des approximations traitables par calcul pour la vérification d'inclusion et l'intersection avec des demi-espaces. En utilisant ces opérations sur des zonotopes complexes, nous développons des programmes convexes pour vérifier les propriétés d'invariance linéaire des systèmes hybrides affines à temps discret et la stabilité exponentielle des systèmes impulsifs linéaires. Nos expériences sur certains exemples de benchmarks démontrent l'efficacité des techniques de vérification basées sur des zonotopes complexes. / Computing reachable sets is a de facto approach used in many formal verification methods for hybrid systems. But exact computation of the reachable set is an in- tractable problem for many kinds of hybrid systems, either due to undecidability or high computational complexity. Alternatively, quite a lot of research has been focused on using set representations that can be efficiently manipulated to com- pute sufficiently accurate over-approximation of the reachable set. Zonotopes are a useful set representation in reachability analysis because of their closure and low complexity for computing linear transformation and Minkowski sum operations. But for approximating the unbounded time reachable sets by positive invariants, zonotopes have the following drawback. The effectiveness of a set representation for computing a positive invariant depends on efficiently encoding the directions for convergence of the states to an equilibrium. In an affine hybrid system, some of the directions for convergence can be encoded by the complex valued eigen- vectors of the transformation matrices. But the zonotope representation can not exploit the complex eigenstructure of the transformation matrices because it only has real valued generators.Therefore, we extend real zonotopes to the complex valued domain in a way that can capture contraction along complex valued vectors. This yields a new set representation called complex zonotope. Geometrically, complex zonotopes repre- sent a wider class of sets that include some non-polytopic sets as well as polytopic zonotopes. They retain the merit of real zonotopes that we can efficiently perform linear transformation and Minkowski sum operations and compute the support function. Additionally, we show that they can capture contraction along complex valued eigenvectors. Furthermore, we develop computationally tractable approx- imations for inclusion-checking and intersection with half-spaces. Using these set operations on complex zonotopes, we develop convex programs to verify lin- ear invariance properties of discrete time affine hybrid systems and exponential stability of linear impulsive systems. Our experiments on some benchmark exam- ples demonstrate the efficiency of the verification techniques based on complex zonotopes.

Dans le contexte des systèmes dynamiques, cette thèse développe des techniques d'estimation d'état ensemblistes pour différentes classes de systèmes. On considère pour cela le cas d'un système standard linéaire invariant dans le temps soumis à des perturbations, des bruits de mesure et des incertitudes inconnus, mais bornés. Dans une première étape, une technique d'estimation d'état ellipsoïdale est étendue, puis appliquée sur un modèle d'octorotor utilisé dans un contexte radar. Une extension de cette approche ellipsoïdale d'estimation d'état est proposée pour des systèmes descripteurs. Dans la deuxième partie, nous proposons une méthode fondée sur la minimisation du P-rayon d'un zonotope, appliquée à un modèle d'octorotor. Cette méthode est ensuite étendue pour traiter les systèmes affines par morceaux. Dans la continuité des approches précédentes, un nouveau filtre de Kalman sous contraintes zonotopiques est proposé dans la dernière partie de cette thèse. En utilisant la forme duale d'un problème d'optimisation, l'algorithme projette l'état sur un zonotope qui forme l'enveloppe de l'ensemble des contraintes auxquelles l'état est soumis. La complexité de l'algorithme est ensuite améliorée en remplaçant le zonotope initial par une forme réduite en limitant son nombre de générateurs. / In the context of dynamical systems, this thesis focuses on the development of robust set-membership state estimation procedures for different classes of systems. We consider the case of standard linear time-invariant systems, subject to unknown but bounded perturbations and measurement noises. The first part of this thesis builds upon previous results on ellipsoidal set-membership approaches. An extended ellipsoidal set-membership state estimation technique is applied to a model of an octorotor used for radar applications. Then, an extension of this ellipsoidal state estimation approach is proposed for descriptor systems. In the second part, we propose a state estimation technique based on the minimization of the P-radius of a zonotope, applied to the same model of the octorotor. This approach is further extended to deal with piecewise affine systems. In the continuity of the previous approaches, a new zonotopic constrained Kalman filter is proposed in the last part of this thesis. By solving a dual form of an optimization problem, the algorithm projects the state on a zonotope forming the envelope of the set of constraints that the state is subject to. Then, the computational complexity of the algorithm is improved by replacing the original possibly large-scale zonotope with a reduced form, by limiting its number of generators.

La modélisation géométrique de quelques problèmes de gestion de la fabrication des mélanges en pétrochimie a amené a introduire des polytopes particuliers appelés zonotopes. Le critère de gestion utilise a conduit a la resolution d'un probleme d'optimisation non linéaire avec contraintes. Les données de ce probleme sont constituées par des caractéristiques des produits de base. Ces caractéristiques sont des résultats de mesures, donc sujettes a des erreurs. Nous étudions la variation de la solution du probleme d'optimisation par rapport a ces erreurs et nous caractérisons la région de confiance de la solution quand celles-ci sont supposées gaussiennes et indépendantes. Un zonoide est la limite au sens de la métrique de hausdorff d'une suite de zonotopes. Dans le cas des processus continus de fabrication, la modélisation a amené a considérer des zonoides particuliers appelés zonoides associes a une courbe paramétrique. Nous donnons quelques propriétés de ces ensembles, nous présentons une paramétrisation de la surface représentant leurs bords et nous étudions la régularité de cette paramétrisation connaissant celles des courbes paramétriques auxquelles ils sont associes. Nous abordons ensuite le probleme d'approximation de zonoides par des zonotopes. Une methode de construction de suites de zonotopes convergeant vers un zonoide donne est etablie. Pour chaque zonotope, élément de la suite, nous évaluons l'erreur d'approximation. L'ordre de convergence de ces suites est calcule.

Cette thèse se compose de plusieurs travaux portant sur l'énumération et le comportement asymptotique de structures combinatoires apparentées aux partitions d'entiers. Un premier travail s'intéresse aux partitions d'entiers bipartites, qui constituent une généralisation bidimensionnelle des partitions d'entiers. Des équivalents du nombre de partitions sont obtenus dans le régime critique où l'un des entiers est de l'ordre du carré de l'autre entier et au delà de ce régime critique. Ceci complète les résultats établis dans les années cinquante par Auluck, Nanda et Wright. Le deuxième travail traite des chaînes polygonales à sommets entiers dans le plan. Pour un modèle statistique introduit par Sinaï, une représentation intégrale exacte de la fonction de partition est donnée. Ceci conduit à un équivalent du nombre de chaînes joignant deux points distants qui fait intervenir les zéros non triviaux de la fonction zêta de Riemann. Une analyse combinatoire détaillée des chaînes convexes est présentée. Elle permet de montrer l'existence d'une forme limite pour les chaînes convexes aléatoires ayant peu de sommets, répondant ainsi à une question ouverte de Vershik. Un troisième travail porte sur les zonotopes à sommets entiers en dimension supérieure. Un équivalent simple est donné pour le logarithme du nombre de zonotopes contenus dans un cône convexe et dont les extrémités sont fixées. Une loi des grands nombres est établie et la forme limite est caractérisée par la transformée de Laplace du cône. / This thesis consists of several works dealing with the enumeration and the asymptotic behaviour of combinatorial structures related to integer partitions. A first work concerns partitions of large bipartite integers, which are a bidimensional generalization of integer partitions. Asymptotic formulæ are obtained in the critical regime where one of the numbers is of the order of magnitude of the square of the other number, and beyond this critical regime. This completes the results established in the fifties by Auluck, Nanda, and Wright. The second work deals with lattice convex chains in the plane. In a statistical model introduced by Sinaï, an exact integral representation of the partition function is given. This leads to an asymptotic formula for the number of chains joining two distant points, which involves the non trivial zeros of the Riemann zeta function. A detailed combinatorial analysis of convex chains is presented. It makes it possible to prove the existence of a limit shape for random convex chains with few vertices, answering an open question of Vershik. A third work focuses on lattice zonotopes in higher dimensions. An asymptotic equality is given for the logarithm of the number of zonotopes contained in a convex cone and such that the endings of the zonotope are fixed. A law of large numbers is established and the limit shape is characterized by the Laplace transform of the cone.

<p>Set-based methods have been leveraged in many engineering applications from robust control and global optimization, to probabilistic planning and estimation. While useful, these methods have most widely been applied to analysis over sets that are convex, due to their ease in both representation and calculation. The representation and analysis of nonconvex sets is inherently complex. When nonconvexity arises in design and control applications, the nonconvex set is often over-approximated by a convex set to provide conservative results. However, the level of conservatism may be large and difficult to quantify, often leading to trivial results and requiring repetitive analysis by the engineer. Nonconvexity is inherent and unavoidable in many applications, such as the analysis of hybrid systems and robust safety constraints. </p> <p>In this dissertation, I present a new nonconvex set representation named the hybrid zonotope. The hybrid zonotope builds upon a combination of recent advances in the compact representation of convex sets in the controls literature with methods leveraged in solving mixed-integer programming problems. It is shown that the hybrid zonotope is equivalent to the union of an exponential number of convex sets while using a linear number of continuous and binary variables in the set’s representation. I provide identities for, and derivations of, the set operations of hybrid zonotopes for linear mappings, Minkowski sums, generalized intersections, halfspace intersections, Cartesian products, unions, complements, point containment, set containment, support functions, and convex enclosures. I also provide methods for redundancy removal and order reduction to improve the compactness and computational efficiency of the represented sets. Therefore proving the hybrid zonotopes expressive power and applicability to many nonconvex set-theoretic methods. Beyond basic set operations, I specifically show how the exact forward and backward reachable sets of linear hybrid systems may be found using identities that are calculated algebraically and scale linearly. Numerical examples show the scalability of the proposed methods and how they may be used to verify the safety and performance of complex systems. These exact methods may also be used to evaluate the level of conservatism of the existing approximate methods provided in the literature.  </p>

A spectral graph realization is an embedding of a finite simple graph into Euclidean space that is constructed from the eigenvalues and eigenvectors of the graph's adjacency matrix. It has previously been observed that some polytopes can be reconstructed from their edge-graphs by taking the convex hull of a spectral realization of this edge-graph. These polytopes, which we shall call spectral polytopes, have remarkable rigidity and symmetry properties and are a source for many open questions. In this thesis we aim to further the understanding of this phenomenon by exploring the geometric and combinatorial properties of spectral polytopes on several levels. One of our central questions is whether already weak forms of symmetry can be a sufficient reason for a polytope to be spectral. To answer this, we derive a geometric criterion for the identification of spectral polytopes and apply it to prove that indeed all polytopes of combined vertex- and edge-transitivity are spectral, admit a unique reconstruction from the edge-graph and realize all the symmetries of this edge-graph. We explore the same questions for graph realizations and find that realizations of combined vertex- and edge-transitivity are not necessarily spectral. Instead we show that we require a stronger form of symmetry, called distance-transitivity. Motivated by these findings we take a closer look at the class of edge-transitive polytopes, for which no classification is known. We state a conjecture for a potential classification and provide complete classifications for several sub-classes, such as distance-transitive polytopes and edge-transitive polytopes that are not vertex-transitive. In particular, we show that the latter class contains only polytopes of dimension d <= 3. As a side result we obtain the complete classification of the vertex-transitive zonotopes and a new characterization for root systems.

Nous nous plaçons dans le cadre de l'analyse statique de programmes, et nous nous intéressons aux propriétés numériques, c'est a dire celles qui concernent les valeurs numériques des variables de programmes. Nous essayons en particulier de déterminer une sur-approximation garantie de l'ensemble de valeurs possibles pour chaque variable numérique utilisée dans le programme à analyser. Cette analyse statique est faite dans le cadre de la théorie de l'interprétation abstraite, théorie présentant un compromis entre les limites théoriques d'indécidabilite et de calculabilite et la précision des résultats obtenus. Nous sommes partis des travaux d'Eric Goubault et Sylvie Putot, que nous avons étendus et généralisés. Notre nouveau domaine abstrait, appelé ensembles affines contraints, combine à la fois l'efficacite de calcul des domaines à base de formes affines et le pouvoir ex- pressif des domaines relationnels classiques tels que les octogones ou les polyèdres. Le nouveau domaine a été implémenté pour mettre en évidence l'intérêt de cette combinaison, ses avantages, ses performances et ses limites par rapport aux autres domaines numériques déjà existants. Le formalisme ainsi que les résultats pra- tiques ont fait l'objet de plusieurs publications [CAV 2009, CAV 2010].