Omitting constraints of polynomial system

Question

Let $n_1, n_2 \geq 1$ be known integer constants.

Suppose that we have the following system of $n$ polynomial inequalities for which we know that there exists a feasible solution $(p_1, p_2) \in (0,1)^2$. Furthermore, we assume that each $\epsilon_i$ is much smaller than the corresponding $\mu_i$ ($\epsilon_i$ actually correspond to error terms).

\begin{align*} \mu_1 - \epsilon_1 &\leq n_1 q_1^1 + n_2 q_2^1 \leq \mu_1 + \epsilon_1 \\ \mu_2 - \epsilon_2 &\leq n_1 q_1^2 + n_2 q_2^2 \leq \mu_2 + \epsilon_2 \\ &\vdots \\ \mu_n - \epsilon_n &\leq n_1 q_1^n + n_2 q_2^n \leq \mu_n + \epsilon_n \\ 0 &\leq q_1, q_2 \leq 1\\ \end{align*}

I know that we can use Renegar's Algorithm [1] to solve this system.

Question

If the errors $\epsilon_i$ were $0$ I would need just two equations to find the exact solution of the system $(p_1, p_2)$. I would like to know how the set of the solutions of this system changes when I omit some constraints. Assuming that $n$ is huge I have the intuition that dropping many (let's say $\sqrt{n}$) of the constraints should not have a large "impact" on the feasible set since the dimension of the system is very small ($2$). Is there any way that I could measure the "impact" that deleting a constraint has on the area of the feasible set?

[1] : http://www.mathunion.org/ICM/ICM1990.2/Main/icm1990.2.1595.1606.ocr.pdf

Answer 1

Here are some thoughts:

• The system $x+2y=0.75,x^2+2y^2=0.25$ Is the intersection of a line and an ellipse with two exact solutions, One near $(0.45,0.15)$ and the other near $(0.05,0.35).$ A system of your type could have two solution regions. It almost certainly would if $n_1=n_2=1$ and hence if they are nearly equal. So there might be only one region for the whole system but two regions upon dropping a constraint. I'll ignore that issue. If needed (usually) we could specify which of $q_1,q_2$ is larger.

• So the solution set for your problem will be one, or maybe two, small regions. To quantify the result of dropping some constraints you could see how much the area changes.

• Consider the following problem (which is simpler and does not share all the features of your question): Given a system of constraints in one variable $$\mu_i-\epsilon_i \le nx^i \le \mu_i+\epsilon_i$$ then , of course, each single one determines a sub-interval $[\ell_i,r_i] \subseteq (0,1).$ The combined solution set is $[max(\ell_i),\min(r_j)]$ so some two (in fact two halves) determine everything and any or all of the rest could be dropped with no change. How would you quantify that? Dropping (the relevant half) of one or both of the important inequalities might dramatically enlargeIf all the intervals are (about) the same then dropping some of them has (almost) no effect.

• A closer analog would be to have many linear constraints $$\mu_i-\epsilon_i \le n_{i,1}q_1+n_{i,2}q_2 \le \mu_i+\epsilon_i$$ so each determines the thin region between two parallel lines. There could be similar phenomena. Two of the constraints might limit things so much that all the rest are automatically satisfied. Dropping either could have a big effect. On the other hand, consider a small disk centered at some point $(h,k)$ and pick the constraints so that the boundary lines are tangent to that disk. In this case each constraint removed increases the area by a positive amount, but seemingly a small amount relative to the solution set.

• Getting back to your problem, there could be similar phenomena. The relevant portions of the boundary curves are (usually) fairly short so very close to their tangents or best linear approximations.

• I thought that the paper you link to only concerns systems of linear inequalities in many variables. But I was wrong. Of course the previous result says that the constraints (in combination) are usually nearly linear.