Exact relaxation for polynomial optimization on semi-algebraic sets

Marta Abril Bucero 1 Bernard Mourrain 1
1 GALAAD2 - Géométrie , Algèbre, Algorithmes
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : In this paper, we study the problem of computing by relaxation hierarchies the infimum of a real polynomial function f on a closed basic semialgebraic set and the points where this infimum is reached, if they exist. We show that when the infimum is reached, a relaxation hierarchy constructed from the Karush-Kuhn-Tucker ideal is always exact and that the vanishing ideal of the KKT minimizer points is generated by the kernel of the associated moment matrix in that degree, even if this ideal is not zero-dimensional. We also show that this relaxation allows to detect when there is no KKT minimizer. We prove that the exactness of the relaxation depends only on the real points which satisfy these constraints.This exploits representations of positive polynomials as elementsof the preordering modulo the KKT ideal, which only involves polynomials in the initial set of variables. Applications to global optimization, optimization on semialgebraic sets defined by regular sets of constraints, optimization on finite semialgebraic sets, real radical computation are given.
Type de document :
Pré-publication, Document de travail
2014
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00846977
Contributeur : Marta Abril Bucero <>
Soumis le : mardi 1 juillet 2014 - 17:04:18
Dernière modification le : mercredi 4 mai 2016 - 01:01:29
Document(s) archivé(s) le : mercredi 1 octobre 2014 - 13:15:34

Fichiers

certifiedrevised.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00846977, version 4
  • ARXIV : 1307.6426

Collections

Citation

Marta Abril Bucero, Bernard Mourrain. Exact relaxation for polynomial optimization on semi-algebraic sets. 2014. 〈hal-00846977v4〉

Partager

Métriques

Consultations de la notice

492

Téléchargements de fichiers

112