Practical polynomial optimization through positivity certificates with and without denominators - LAAS - Laboratoire d'Analyse et d'Architecture des Systèmes Accéder directement au contenu
Thèse Année : 2022

Practical polynomial optimization through positivity certificates with and without denominators

Optimisation polynomiale pratique grâce à des certificats de positivité avec et sans dénominateurs

Ngoc Hoang Anh Mai
  • Fonction : Auteur
  • PersonId : 1226597
  • IdRef : 267256175

Résumé

Positivity certificates or Positivstellens"atze provide representations of polynomials positive on basic semialgebraic sets, i.e., sets defined by finitely many polynomial inequalities. The famous Putinar's Positivstellensatz states that every positive polynomial on a basic closed semialgebraic set dollarSdollar can be written as a linear weighted combination of the polynomials describing dollarSdollar, under a certain condition on dollarSdollar slightly stronger than compactness. When written in this it becomes obvious that the polynomial is positive on dollarSdollar, and therefore this alternative description provides a certificate of positivity on dollarSdollar. Moreover, as the polynomial weights involved in Putinar's Positivstellensatz are sums of squares (SOS), such Positivity certificates enable to design convex relaxations based on semidefinite programming to solve polynomial optimization problems (POPs) that arise in various real-life applications, e.g., in management of energy networks and machine learning to cite a few. Originally developed by Lasserre, the hierarchy of semidefinite relaxations based on Putinar's Positivstellensatz is called the emph{Moment-SOS hierarchy}. In this thesis, we provide polynomial optimization methods based on positivity certificates involving specific SOS weights, without or with denominators.
Les certificats de positivité ou Positivstellens"atze fournissent des représentations de polynômes positifs sur des ensembles semialgébriques de basiques, c'est-à-dire des ensembles définis par un nombre fini d'inégalités polynomiales. Le célèbre Positivstellensatz de Putinar stipule que tout polynôme positif sur un ensemble semialgébrique basique fermé dollarSdollar peut être écrit comme une combinaison pondérée linéaire des polynômes décrivant dollarSdollar, sous une certaine condition sur dollarSdollar légèrement plus forte que la compacité. Lorsqu'il est écrit comme ceci, il devient évident que le polynôme est positif sur dollarSdollar, et donc cette description alternative fournit un certificat de positivité sur dollarSdollar. De plus, comme les poids polynomiaux impliqués dans le Positivstellensatz de Putinar sont des sommes de carrés (SOS), de tels certificats de positivité permettent de concevoir des relaxations convexes basées sur la programmation semidéfinie pour résoudre des problèmes d'optimisation polynomiale (POP) qui surviennent dans diverses applications réelles, par exemple dans la gestion des réseaux d'énergie et l'apprentissage automatique pour n'en citer que quelques unes. Développée à l'origine par Lasserre, la hiérarchie des relaxations semidéfinies basée sur le Positivstellensatz de Putinar est appelée la emph{hiérarchie Moment-SOS}. Dans cette thèse, nous proposons des méthodes d'optimisation polynomiale basées sur des certificats de positivité impliquant des poids SOS spécifiques, sans ou avec dénominateurs.
Fichier principal
Vignette du fichier
2022TOU30165a.pdf (2.78 Mo) Télécharger le fichier
Origine : Version validée par le jury (STAR)

Dates et versions

tel-03843327 , version 1 (08-11-2022)
tel-03843327 , version 2 (26-01-2023)

Identifiants

  • HAL Id : tel-03843327 , version 2

Citer

Ngoc Hoang Anh Mai. Practical polynomial optimization through positivity certificates with and without denominators. Optimization and Control [math.OC]. Université Paul Sabatier - Toulouse III, 2022. English. ⟨NNT : 2022TOU30165⟩. ⟨tel-03843327v2⟩
72 Consultations
33 Téléchargements

Partager

Gmail Facebook X LinkedIn More