Fast algorithmn for deciding whether a polynomial system of inequalities has a solution

Question

I am looking for a fast algorithmn that decides whether a given system of k polynomial inequalities in n variables has a solution ( I do not need the solution )

For k > n.

I have read about Cylindrical Algebraic Decomposition but have not been able to find anything better than that so far.

EDIT:

It is about polynomials with real coefficients over the real numbers.

Answer 1

Any other solution is not known. You have to enumerate the components in some kind of CAD by finding at least one point per component and then check those points for satisfying the inequalities.

You can read about the modern approaches in Basu, Pollack, Roy: "Algorithms in real algebraic geometry"

Answer 2

Maple's package regular chains has a command IsEmpty?

The command IsEmpty(sys, R) checks whether the zero set of the set of constraints sys is empty or not. The constraints in sys can be any polynomial equations, inequations or inequalities given by polynomials of R. The zero set of sys is regarded as the set of the real solutions of the polynomial system defined by sys. This assumes that R has characteristic zero.

I'm not sure what is the algorithm used but see:

Xia, Bican, and Lu Yang. "An algorithm for isolating the real solutions of semi-algebraic systems." Journal of Symbolic Computation 34, no. 5 (2002): 461-477.

Answer 3

Deciding if a system of polynomial inequalities is feasible is a very hard mathematical problem and a lot of research in real algebraic geometry has to do with it.

Apart from cylindrical algebraic decomposition there are theorems of the alternative also for these sets. The most notable result is Stengle's Positivstellensatz which roughly says that if it is infeasible, then you can prove that it is infeasible by combining the positivity requirements from the constraints in a positive way so that the result is -1. This contradiction proves infeasibility.

Finding these certificates can be very bad algorithmically, but you can look at so called moment relaxations of your set. These are slighly larger sets whose feasibility can be decided with semi-definite programming. Algorithms for this are well-developed.

In total, there is a hierarchy of larger and larger convex optimization problems in which you eventually find a solution to the question of infeasibility. Of course in practice all this can be spoiled by numerical problems, etc. An implementation of this is the Matlab package yalmip

Answer 4

Assuming that the parameter is real you can find the roots of the polynom (assuming that you include n into the polynom) and the solution would be the set of intervals where X is greater than 0.

You can also use the results of the derivatives to determine the trend of the function.