Mapping multivariate polynomial inequalities system to subspace

Question

What I will ask, more than a solution, is better mathematical definition of my problem and directions to find the solution.

I have a set of linear equations, e.g.:

\begin{align} d_1 &= L_1 - 9\,m_1 - 9\,m_2 \\ d_2 &= x_1 + 3\,m_1 + 3\,m_2 \\ d_3 &= y_1 \\ d_4 &= L_2 - 4\,m_2 \\ d_5 &= x_2 + 2\,m_2 \\ d_6 &= y_2 \end{align}

where $d_1,d_2,...,d_6$ are linear combinations of $L_1,x_1,y_1,m_1,L_2,x_2,y_2,m_2 \in \mathbb{R}$.

$L_1,x_1,y_1,m_1,L_2,x_2,y_2,m_2$ are physical parameters which have physical nonlinear constraints, in the form of polynomial inequalities, e.g.:

\begin{align} m_1 &>0\\ L_1m_1−x^2_1−y^2_1 &>0\\ m_2 &>0\\ L_2m_2−x^2_2−y^2_2 &>0 \end{align}

---

I would like to rewrite constraints in terms of $d_1,d_2,...,d_6$ only.

I.e., I would like to find constrains over $d_1,d_2,...,d_6$ parameters (only), so that when a numerical set of $d_1,d_2,...,d_6$ verifies the new mapped constraints that would mean that there is at least one $L_1,x_1,y_1,m_1,L_2,x_2,y_2,m_2$ solution (it doesn't matter what) which verify the former constraints. If the new constraints are not verified it must mean that no $L_1,x_1,y_1,m_1,L_2,x_2,y_2,m_2$ solution exists.

Here I presented a particularly small example, for it I was already able to find the constraints doing manual equation manipulation ($d_1 + 6 d_2 > 0$ and $- 9 d_{5}^{2} - 9 d_{6}^{2} + \left(d_{1} + 6 d_{2}\right) \left(d_{4} + 4 d_{5}\right) >0$) However, I have problems with up to 70 linear equations and 30 higher order polynomial inequalities constraints.

What I need is a systematic method to write the constrains over $d_1,d_2,...,d_6$.

I think that in geometrical thinking this is like projecting the intersection of a set of non-linear volumes/regions of $n$-dimensional space ($n>>1$) onto a subspace of it, where the coefficients of the linear system are the basis of such subspace.

Now the questions:

• What kind of problem do I have?
• Which mathematical fields shall I study, and which directions must I follow?

My background is in engineering so my mathematical writing is not very formal.

Thanks.

Answer 1

This is a classic problem in a field called Real Semialgebraic Geometry (RSG), an introduction to which can be found here. RSG deals with what are called "semialgebraic sets", which are essentially sets of points in $\mathbb R^n$ which satisfy a system of algebraic equalities and inequalities, as well as certain well-behaved functions from $\mathbb R^n$ to $\mathbb R^m$ which are called "semialgebraic functions". In your case, you have the set $S$ of points in $\mathbb R^8$ which satisfy the system $$\begin{align} m_1 &>0\\\\ L_1m_1−x^2_1−y^2_1 &>0\\\\ m_2 &>0\\\\ L_2m_2−x^2_2−y^2_2 &>0 \end{align}$$ and the semialgebraic map $f:\mathbb R^8\to\mathbb R^6$ defined by $$f(L_1,x_1,y_1,m_1,L_2,x_2,y_2,m_2)=(d_1,d_2,d_3,d_4,d_5,d_6)$$ and you want to find a system of inequalities which defines the image $f[S]$. Of course, it is easy to define $f[S]$ by saying "$p\in f[S]$ iff there exists some $q\in S$ such that $f(q)=p$", but this formula has an existence quantifier. Luckily, the image of a semialgebraic set under a semialgebraic map is a semialgebraic map, so it is a theorem that you can find some quantifier-free formula which defines $f[S]$. A quantifier-free formula is not necessarily a system of inequalities, but rather a finite collection of systems of algebraic equalities and inequalities such that $p\in F[S]$ iff $p$ satisfies one of these systems. There are almost certainly algorithms to do this, but I do not know them, and they probably have at least exponential runtimes in the sum of the degrees of the polynomial constraints. The terms here should at least give you something to search with.

Answer 2

See at CAD (Cylindrical_Algebraic_Decompositions) algorithm for multivariate polynomial inequality systems:

http://www.csd.uwo.ca/~moreno/Publications/An_Incremental_Algorithm_for_Computing_Cylindrical_Algebraic_Decompositions.pdf

or view at Wolfram|Alpha org site for Internal Implementation:

http://reference.wolfram.com/language/tutorial/SomeNotesOnInternalImplementation.html#25940

to decide which algorithm must to implement.