Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 :
Preprints, Working Papers, ...
Complete list of metadatas

https://hal.inria.fr/hal-00815123
Contributor : Mohab Safey El Din <>
Submitted on : Thursday, April 18, 2013 - 11:14:48 AM
Last modification on : Friday, January 8, 2021 - 5:42:02 PM
Long-term archiving on: : Friday, July 19, 2013 - 4:01:21 AM

Files

opt_27_03_13.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00815123, version 1
  • ARXIV : 1304.5214

Citation

Bernd Bank, Marc Giusti, Joos Heintz, Mohab Safey El Din. Intrinsic complexity estimates in polynomial optimization. 2013. ⟨hal-00815123v1⟩

Share

Metrics

Record views

72

Files downloads

272