HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

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.
Document type :
Journal articles
Complete list of metadata

Cited literature [47 references]  Display  Hide  Download

Contributor : Mohab Safey El Din Connect in order to contact the contributor
Submitted on : Monday, February 10, 2014 - 5:39:28 PM
Last modification on : Friday, January 21, 2022 - 3:21:47 AM
Long-term archiving on: : Sunday, May 11, 2014 - 7:35:10 AM


Files produced by the author(s)



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⟩



Record views


Files downloads