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 $(sd{)}^{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 $(nd{)}^{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.

References in corpus (3)

• Exact relaxation for polynomial optimization on semi-algebraic sets
• A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set
• Degeneracy loci and polynomial equation solving

Cited by in corpus (1)

• Probabilistic Algorithm for Polynomial Optimization over a Real Algebraic Set