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.


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

  • $\begingroup$ I may be able to identify the "most important" equations in the system but even in this case I don't have a way to quantify how much my system is affected from deleting the "redudant" constraints. $\endgroup$ – vkonton Jun 21 '17 at 21:51
  • 1
    $\begingroup$ Suppose some two of the $\epsilon_i$ are $0$ or just much smaller than rest. Then deleting the other $n-2$ constraints might have no effect on the solution set . But deleting just those two might increase the solution set quite a lot. Even something like $2q_1+q_2 \ge 0.98 + 0.02$ and $2q_1^2+q_2^2 \le 0.48+0.2$ forces the solution to be $(0.5,0)$ $\endgroup$ – Aaron Meyerowitz Jun 21 '17 at 21:55
  • 1
    $\begingroup$ Deleting redundant constraints can have arbitrarily small or even no effect. $\endgroup$ – Aaron Meyerowitz Jun 21 '17 at 21:57
  • $\begingroup$ Yep, thats also my intuition. I need a method to quantify this idea. $\endgroup$ – vkonton Jun 21 '17 at 21:58

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.

  • $\begingroup$ the paper linked talks about multivariate polynomial inequalities, too. $\endgroup$ – Dima Pasechnik Jun 22 '17 at 19:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.