Intrinsic complexity estimates in polynomial optimization - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2013

Intrinsic complexity estimates in polynomial optimization

Résumé

It is known that point searching in basic semialgebraic sets and the search for globally minimal points in polynomial optimization tasks can be carried out using $(s\,d)^{O(n)}$ arithmetic operations, where $n$ and $s$ are the numbers of variables and constraints and $d$ is the maximal degree of the polynomials involved.\spar \noindent We associate to each of these problems an intrinsic system degree which becomes in worst case of order $(n\,d)^{O(n)}$ and which measures the intrinsic complexity of the task under consideration.\spar \noindent We design non-uniformly deterministic or uniformly probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.
Fichier principal
Vignette du fichier
opt_27_03_13.pdf (185.56 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-00815123 , version 1 (18-04-2013)
hal-00815123 , version 2 (10-02-2014)

Identifiants

Citer

Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din. Intrinsic complexity estimates in polynomial optimization. 2013. ⟨hal-00815123v1⟩
339 Consultations
533 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More