Dans ce travail de thèse, nous étudions, dans un contexte d'analyse convexe et d'optimisation, la prise en compte des contraintes dites d'autocorrélation, c'est-à-dire : nous considérons les situations où les vecteurs représentant les variables à optimiser sont contraintes à être les coefficients d'autocorrélation d'un signal discret à support fini. Cet ensemble des vecteurs à composantes autocorrélées se trouve être un cône convexe ; nous essayons d'en établir le plus de propriétés possibles : concernant sa frontière (lisse/polyédrale), ses faces, l'acuité, l'expression du cône polaire, l'évaluation du cône normal en un point, etc. Ensuite, nous étudions divers algorithmes pour résoudre des problèmes d'optimisation où le cône des vecteurs à composantes autocorrélées entre en jeu. Notre principal objet d'étude est le problème de la projection sur ce cône, dont nous proposons la résolution par trois algorithmes différents : algorithmes dits de suivi de chemin, celui des projections alternées, et via une relaxation non-convexe. Enfin, nous abordons la généralisation de la situation d'autocorrélation au cas de signaux bi-dimensionnels, avec toute la complexité que cela engendre : multiples définitions possibles, non-convexité des problèmes résultants, et complexité calculatoire accrue pour les algorithmes.

Cette thèse est dédiée à l'étude de la hiérarchie moments-sommes-de-carrés, une famille de problèmes de programmation semi-définie en optimisation polynomiale, couramment appelée hiérarchie de Lasserre. Nous examinons différents aspects de ses propriétés et applications. Comme application de la hiérarchie, nous approchons certains objets potentiellement compliqués, comme l'abscisse polynomiale et les plans d'expérience optimaux sur des domaines semi-algébriques. L'application de la hiérarchie de Lasserre produit des approximations par des polynômes de degré fixé et donc de complexité bornée. En ce qui concerne la complexité de la hiérarchie elle-même, nous en construisons une modification pour laquelle un taux de convergence amélioré peut être prouvé. Un concept essentiel de la hiérarchie est l'utilisation des modules quadratiques et de leurs duaux pour appréhender de manière flexible le cône des polynômes positifs et le cône des moments. Nous poursuivons cette idée pour construire des approximations étroites d'ensembles semi-algébriques à l'aide de séparateurs polynomiaux. / This thesis is dedicated to investigations of the moment-sums-of-squares hierarchy, a family of semidefinite programming problems in polynomial optimization, commonly called the Lasserre hierarchy. We examine different aspects of its properties and purposes. As applications of the hierarchy, we approximate some potentially complicated objects, namely the polynomial abscissa and optimal designs on semialgebraic domains. Applying the Lasserre hierarchy results in approximations by polynomials of fixed degree and hence bounded complexity. With regard to the complexity of the hierarchy itself, we construct a modification of it for which an improved convergence rate can be proved. An essential concept of the hierarchy is to use quadratic modules and their duals as a tractable characterization of the cone of positive polynomials and the moment cone, respectively. We exploit further this idea to construct tight approximations of semialgebraic sets with polynomial separators.

Pour l’évaluation de la résistance ultime des ouvrages l’ingénieur de génie civil fait appel à différentes méthodes plus ou moins empiriques, dont de nombreuses manuelles, du fait de la lourdeur excessive des méthodes par éléments finis non-linéaires mises en œuvre dans les logiciels de calcul à sa disposition. Le calcul à la rupture, théorisé par J. Salençon, indique la voie de méthodes rigoureuses, tout à fait adaptées à cette problématique, mais dont la mise en œuvre systématique dans un logiciel a longtemps buté sur l’absence de méthodes numériques efficaces. Ce verrou de mathématique numérique a été levé récemment (Algorithme de point intérieur).Dans ce contexte l’objectif de la présente thèse est de mettre au point les méthodes permettant d’analyser, au moyen du calcul à la rupture, la capacité ultime d’éléments en béton armé tridimensionnels. Les deux approches du calcul à la rupture, que sont les approches statique et cinématiques, seront mises en œuvre numériquement sous la forme d’un problème d’optimisation résolu à l’aide d’un solveur mathématique dans le cadre de la programmation semi définie positive (SDP).Une large partie du travail sera consacré à la modélisation des différents matériaux constituant le béton armé. Le choix du critère pour modéliser la résistance du béton sera discuté, tout comme la méthode pour prendre en compte le renforcement. La méthode d’homogénéisation sera utilisée dans le cas de renforcement périodique et une adaptation de cette méthode sera utilisée dans le cas de renforts isolés. Enfin, les capacités et le potentiel de l’outil développé et mis en œuvre au cours de cette thèse seront exposés au travers d’exemples d’application sur des structures massives / To evaluate the load bearing capacity of structures, civil engineers often make use of empirical methods, which are often manuals, instead of nonlinear finite element methods available in existing civil engineering softwares, which are long to process and difficult to handle. Yield design (or limit analysis) approach, formalized by J. Salençon, is a rigorous method to evaluate the capacity of structures and can be used to answer the question of structural failure. It was, yet, not possible to take advantage of these theoretical methods due to the lack of efficient numerical methods. Recent progress in this field and notably in interior point algorithms allows one to rethink this opportunity. Therefore, the main objective of this thesis is to develop a numerical model, based on the yield design approach, to evaluate the ultimate capacity of massive (3D) reinforced concrete structural elements. Both static and kinematic approaches are implemented and expressed as an optimization problem that can be solved by a mathematical optimization solver in the framework of Semi-Definite Programming (SDP).A large part of this work is on modelling the resistance of the different components of the reinforced concrete composite material. The modelling assumptions taken to model the resistance of concrete are discussed. And the method used to model reinforcement is also questioned. The homogenization method is used to model periodic reinforcement and an adaptation of this technique is developed for isolated rebars. To conclude this work, a last part is dedicated to illustrate the power and potentialities of the numerical tool developed during this PhD thesis through various examples of massive structures

Le déséquilibre d'un sommet dans un graphe orienté est la valeur absolue de la différence entre son degré sortant et son degré entrant. Nous étudions le problème de trouver une orientation des arêtes du graphe telle que l'image du vecteur dont les composantes sont les déséquilibres des sommets par une fonction objectif f est maximisée. Le premier cas considéré est le problème de maximiser le minimum des déséquilibres sur toutes les orientations possibles. Nous caractérisons les graphes dont la valeur objective optimale est nulle. Ensuite nous donnons plusieurs résultats concernant la complexité du problème. Enfin, nous introduisons différentes formulations du problème et présentons quelques résultats numériques. Par la suite, nous montrons que le cas f=1/2 | |·| |₁ mène au célèbre problème de la coupe de cardinalité maximale. Nous introduisons de nouvelles formulations ainsi qu'un nouveau majorant qui domine celui de Goemans et Williamson. Des résultats théoriques et numériques concernant la performance des approches sont présentés. Pour finir, dans le but de renforcer certaines des formulations des problèmes étudiés, nous étudions une famille de polyèdres spécifique consistant en l'enveloppe convexe des matrices d'affectation 0/1 (où chaque colonne contient exactement une composante égale à 1) annexée avec l'indice de leur ligne non-identiquement nulle la plus basse. Nous donnons une description complète de ce polytope ainsi que certaines de ses variantes qui apparaissent naturellement dans le contexte de divers problèmes d'optimisation combinatoire. Nous montrons également que résoudre un programme linéaire sur un tel polytope peut s'effectuer en temps polynomial / The imbalance of a vertex in a directed graph is the absolute value of the difference between its outdegree and indegree. In this thesis we study the problem of orienting the edges of a graph in such a way that the image of the vector which components are the imbalances of the vertices of the graph under an objective function f is maximized. The first case considered is the problem of maximizing the minimum imbalance of all the vertices over all the possible orientations of the input graph. We first characterize graphs for which the optimal objective value is zero. Next we give several results concerning the computational complexity of the problem. Finally, we deal with several mixed integer programming formulations for this problem and present some numerical experiments. Next, we show that the case for f=1/2 | |·| |₁ leads to the famous unweighted maximum cut problem. We introduce some new formulations along with a new bound shown to be tighter than Michel Goemans & David Williamson's. Theoretical and computational results regarding bounds quality and performance are also reported. Finally, in order to strengthen some formulations of the studied problems, we study a specific class of polytopes. Consider the polytope consisting in the convex hull of the 0/1 assignment matrices where each column contains exactly one coefficient equal to 1 appended with their index of the lowest row that is not identically equal to the zero row. We give a full description of this polytope and some of its variants which naturally appear in the context of several combinatorial optimization problems. We also show that linear optimization over those polytopes can be done in polynomial time