Intrinsic complexity estimates in polynomial optimization

Abstract : 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.
Type de document :
Article dans une revue
Journal of Complexity, Elsevier, 2014, 30 (4), pp.430-443. <10.1016/j.jco.2014.02.005>
Liste complète des métadonnées


https://hal.inria.fr/hal-00815123
Contributeur : Mohab Safey El Din <>
Soumis le : lundi 10 février 2014 - 17:39:28
Dernière modification le : jeudi 9 février 2017 - 15:06:25
Document(s) archivé(s) le : dimanche 11 mai 2014 - 07:35:10

Fichiers

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

Identifiants

Collections

Citation

Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din. Intrinsic complexity estimates in polynomial optimization. Journal of Complexity, Elsevier, 2014, 30 (4), pp.430-443. <10.1016/j.jco.2014.02.005>. <hal-00815123v2>

Partager

Métriques

Consultations de
la notice

412

Téléchargements du document

307