Lorenzo Baldi, POEMA ESR9 at Inria d'Université Côte d'Azur will defend his Phd on the topic of "Effective Representations in Real Algebraic Geometry and Polynomial Optimization"
The defence will take place on Wednesday 26th October at 14:00 in room,room Euler Violet at Inria Sophia Antipolis.
Additionally, the defence will be broadcast over zoom via the following link: https://cutt.ly/aromath.
The jury is composed of:
- Monique LAURENT, Professeure, Centrum Wiskunde & Informatica, Amsterdam, and,Tilburg University, Tilburg,
- Markus SCHWEIGHOFER, Professeur, Universität Konstanz, Constance,
Examinateurs:
- Jean-Bernard LASSERRE, Directeur de Recherche émérite, Laboratoire d’analyse et,d’architecture des systèmes – CNRS, Toulouse
- Adam PARUSIŃSKI, Professeur, Université Côte d’Azur, Nice
- Mihai PUTINAR, Professeur, University of California, Santa Barbara
- Marie-Françoise ROY, Professeure émérite, Université de Rennes 1, Rennes
Phd thesis director: Bernard MOURRAIN, Directeur de Recherche, Inria Sophia Antipolis
Abstract: In polynomial optimization, two different and dual approaches are considered: the approxi-,mation 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 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 dependency on ε^−1 . The bounds also show a new,explicit dependency on the Łojasiewicz exponent Ł and constant c, 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 sequences) 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 obtained,results 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. Finally, we briefly discuss examples of the alternate current - optimal power flow,problem. 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.
