Baldi, Lorenzo, STAR, ABES, AlgebRe, geOmetrie, Modelisation et AlgoriTHmes (AROMATH), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-National and Kapodistrian University of Athens (NKUA), Université Côte d'Azur (UCA), Université Côte d'Azur, and Bernard Mourrain more...
In polynomial optimization, two different and dual approaches are considered: the approximation of positive polynomials using sums of squares (SoS), that translates into Lasserre's SoS hierarchy, and the approximation of measures using truncated positive linear functionals (or truncated pseudo-moment sequences), that translates into Lasserre's moment hierarchy. In this thesis, we investigate exact and approximate representation properties in both the two cases. The representation of positive polynomials in terms of sums of squares is a central question in real algebraic geometry, that is answered by the Positivstellensätze. In particular, we investigate effective version of Putinar's Positivstellensatz, and provide new bounds on the degree of representation of a strictly positive polynomial on a basic compact semialgebraic set S, under the Archimedean condition. These bounds involve a parameter ε, measuring how close is the strictly positive polynomial to have a zero on the semialgebraic set: these are the first bounds with a polynomial dependence on ε -1. The bounds also show a new explicit dependence on the Łojasiewicz exponent Ł and constant cst, arising from a Łojasiewicz inequality between the distance and semialgebraic distance functions from S. We analyze in detail regular cases, where we can show that the Łojasiewicz exponent is equal to one and we have explicit bounds for the Łojasiewicz constant. We interpret our effective Putinar's Positivstellensatz as a result of quantitative approximation of positive polynomials, and deduce the first general polynomial convergence for Lasserre's hierarchies. On the dual side, we deduce convergence rates of truncated positive linear functionals (or truncated pseudo-moment sequances) to measures. We then move to exact representations on the dual side. We investigate properties of the dual cones of truncated quadratic modules, and we introduce the concept of exactness for Lasserre's moment hierarchy, that is closely related to the flat truncation property. We show that the dual of the moment hierarchy coincides with an extended SoS hierarchy, and we detail the analysis for zero dimensional semialgebraic sets. Finally, we apply the results obtained to the study of flat truncation. We give the first necessary and sufficient condition for flat truncation, under the finite convergence assumption, giving bounds for the order of relaxation needed. As corollaries, we conclude that flat truncation holds under generic assumptions, and we give a unified presentation of different results in the zero dimensional case. As an application, we present a new algorithm for computing the real radical of an ideal I. We exploit properties of truncated positive linear functionals and techniques from numerical algebraic geometry. We give an effective, general stopping criterion on the degree, to detect when the kernel of the moment matrix of a generic linear functional can be used to compute equations for the irreducible components of the real variety defined by I. Finally, we compute the real radical as the intersection of real prime ideals lying over I, and illustrate this approach in several examples., Dans le domaine de l'optimisation polynomiale, deux approches différentes et duales sont considérées : l'approximation de polynômes positifs à l'aide de sommes de carrés (SoS), qui se traduit par la hiérarchie SoS de Lasserre, et l'approximation de mesures à l'aide de fonctions linéaires positives tronquées (ou de séquences de pseudo-moments tronquées), qui se traduit par la hiérarchie des moments de Lasserre. Dans cette thèse, nous étudions les propriétés de représentation exactes et approchées dans les deux cas. La représentation des polynômes positifs en termes de sommes de carrés est une question centrale en géométrie algébrique réelle, à laquelle répondent les Positivstellensätze. En particulier, nous étudions une version effective du Positivstellensatz de Putinar, et fournissons de nouvelles bornes sur le degré de représentation d'un polynôme strictement positif sur un ensemble semialgébrique de base S compact, sous la condition Archimedienne. Ces bornes font intervenir un paramètre ε, qui mesure à quelle distance se trouve le polynôme strictement positif d'avoir un zéro sur l'ensemble semialgébrique : ce sont les premières bornes avec une dépendance polynomiale de ε -1. Dans les bornes, on trouve également une nouvelle dépendance explicite de l'exposant de Łojasiewicz Ł et de la constante cst, provenant d'une inégalité Łojasiewicz entre les fonctions de distance et de distance semialgébrique de S. Nous analysons en détail les cas réguliers, dans lesquels nous pouvons montrer que l'exposant Łojasiewicz est égal à un et nous avons des limites explicites pour la constante Łojasiewicz. Nous interprétons notre Positivstellensatz effectif de Putinar comme un résultat d'approximation quantitatif des polynômes positifs, et déduisons la première convergence polynomiale générale pour les hiérarchies de Lasserre. Du point de vue dual, nous déduisons les taux de convergence des fonctions linéaires positives tronquées (ou des séquences pseudo-momentales tronquées) vers les mesures. Nous passons ensuite aux représentations exactes dans le dual. Nous étudions les propriétés des cônes duaux des modules quadratiques tronqués, et nous introduisons le concept d'exactitude pour la hiérarchie des moments de Lasserre, qui est étroitement lié à la propriété de troncation plate. Nous montrons que le dual de la hiérarchie des moments coïncide avec une hiérarchie SoS étendue, et nous détaillons l'analyse pour les ensembles semialgébriques de dimension zéro. Enfin, nous appliquons les résultats obtenus à l'étude de la troncation plate. Nous donnons la première condition nécessaire et suffisante pour la troncature plate, sous l'hypothèse de convergence finie, en donnant des limites pour l'ordre de relaxation nécessaire. Comme corollaires, nous concluons que la troncation plate est vérifiée sous des hypothèses génériques, et nous donnons une présentation unifiée des différents résultats dans le cas de la dimension zéro. Comme application, nous présentons un nouvel algorithme pour calculer le radical réel d'un idéal I. Nous exploitons les propriétés des fonctions linéaires positives tronquées et les techniques de la géométrie algébrique numérique. Nous donnons un critère d'arrêt efficace et général sur le degré, pour détecter quand le noyau de la matrice des moments d'une fonction linéaire générique peut être utilisé pour calculer les équations des composantes irréductibles de la variété réelle définie par I. Enfin, nous calculons le radical réel comme l'intersection d'idéaux premiers réels contenant sur I, et illustrons cette approche par plusieurs exemples. more...