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. Subject to certain conditions, 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. We design non-uniform deterministic or uniform probabilistic algorithms of intrinsic, quasi-polynomial complexity which solve these problems.