Fast way to solve system of non-linear equations and linear inequalities?

user_14067415 0
Viewed 128

I have a set of polynomial equations and linear inequalities for real numbers. How can I determine whether a solution exists? I need no symbolic solution or a guarantee that the answer is correct, but the algorithm should give the correct answer most of the time.

Example: Consider the system of polynomials consisting of just the single polynomial x^2+y^2-1 for real numbers x and y. The linear inequalities prescribe that I am looking for a solution on a small square, i.e.: 0.500<x<0.501, 0.865<y<0.866. The system is then:

x^2+y^2-1==0,
0.500<x<0.501,
0.865<y<0.866

There are infinitely many solutions to this system, for example x=0.5005, y=Sqrt(1-x^2)=0.865737....

Language would ideally be Python, but other languages are welcome.

equation-solving inequality math python
1 Answers

If there is a single polynomial equation that needs to solved inside a rectangular domain, then there is a nice algorithm based on Bernstein polynomials.

Assume your domain is [0,1]x[0,1], which can be achieved by rescaling. You can convert your polynomial equation into one using the Bernstein polynomials. The 1D case is easiest to describe, for a 2 degree polynomial you can write it as

B(x) = b_0 x^2 + 2 b_1 x (1-x) + b_2 (1-x)^2

What these polynomials give you is a simple convexity test for zeros. If all the coefficients, b_0, b_1, b_2 are positive, then you can guarantee that B(x) is strictly positive in the domain [0,1]. Likewise, if they are all negative, then it is strictly negative. So to have a zero the coefficients must differ in sign, or be zero.

You can then proceed in a recursive fashion, split the domain in half, rescale to fit [0,1] calculate the new Bernstein polynomial and apply the zero test. In this way you can quickly narrow down on where the zeros are, ignoring large parts of the domain.

This algorithm was describe in the 2D case in P. Milne, 1991, Zero set of Multivarient Polynomial Equations, Mathematics of Surfaces IV. I've adapted it to 3D in my paper at A new method for drawing Algebraic Surfaces https://singsurf.org/papers/algsurf/index.html which describes all the relevant algorithms, and you can see a live demo at Implict curve plotter with code on github.

There is a vast literature on this problem and plenty of other algorithms for it. Marching squares is a popular algorithm.

user_8654810
Related