1
$\begingroup$
FindInstance[
 0 < x1 + x2 + x3=x4 < 2 && 0 < x4 < x3 < x2 < x1 < 1 && 
  1/x1 + 1/(x1 - x2) + 1/(x1 - x3) + 1/(x1 - x4) < 1/(1 - x1) && 
  1/x2 + -1/(x1 - x2) + 1/(x2 - x3) + 1/(x2 - x4) < 1/(1 - x2) && 
  1/x3 - 1/(x1 - x3) - 1/(x2 - x3) + 1/(x3 - x4) < 1/(1 - x3) && 
  1/x4 - 1/(x1 - x4) - 1/(x2 - x4) - 1/(x3 - x4) < 1/(1 - x4), {x1, 
  x2, x3, x4}, Reals]

FindInstance[
 2 < x1 + x2 + x3+x4 < 2.1 && 0 < x4 < x3 < x2 < x1 < 1 && 
  1/x1 + 1/(x1 - x2) + 1/(x1 - x3) + 1/(x1 - x4) < 1/(1 - x1) && 
  1/x2 + -1/(x1 - x2) + 1/(x2 - x3) + 1/(x2 - x4) < 1/(1 - x2) && 
  1/x3 - 1/(x1 - x3) - 1/(x2 - x3) + 1/(x3 - x4) < 1/(1 - x3) && 
  1/x4 - 1/(x1 - x4) - 1/(x2 - x4) - 1/(x3 - x4) < 1/(1 - x4), {x1, 
  x2, x3, x4}, Reals]

I'm trying to run the above above commands. I suspect that the first wouldn't have a solution while the second would, however FindInstance does not return an answer, or at least running it for an hour didn't result in anything. How can I speed up FindInstance, at least in this case?

I should note that I was able to quickly compute (<1 second) the 3-dimensional analog of the above.

$\endgroup$
-1
$\begingroup$

FindInstance is designed for finding and before that searching of calculating instance. Inequalities are designed to separate points, lines, curves, regions, volumes and alike from each other.

Like the examples for the built-in FindInstance show the methods prefer polynomials, geometrics, booleans. It works with Inequalities and polynomials and multidimensional.

The first fitting example is "A quantified polynomial system.

So start over:

FindInstance[
 1/(-1 + x1) + 1/x1 + 1/(x1 - x2) + 1/(x1 - x3) + 1/(x1 - x4) < 
  0, {x1, x2, x3, x4}, Reals]

{{x1 -> -2, x2 -> 0, x3 -> -3, x4 -> -1}}

Is the unique solution for the second inequality given.

This is in contradiction to

FindInstance[0 < x1 + x2 + x3 = x4 < 2, {x1, x2, x3, x4}, Reals]
{{x1 -> -(1/2), x2 -> -(9/5), x3 -> 3/5, x4 -> -73}}

It is astonishing that this has a Mathematica solution. For example:

FullSimplify[0 < x1 + x2 + x3 = x4 < 2]
x4 < 2

Both throw the message Set; Tag Less in 0

Same for the second FindInstance problem:

FindInstance[2 < x1 + x2 + x3 + x4 < 2.1, {x1, x2, x3, x4}, Reals]
{{x1 -> 2.05, x2 -> 0., x3 -> 0., x4 -> 0.}}

FindInstance[
 1/x1 + 1/(x1 - x2) + 1/(x1 - x3) + 1/(x1 - x4) < 1/(1 - x1), {x1, x2,
   x3, x4}, Reals]
{{x1 -> -2, x2 -> 0, x3 -> -3, x4 -> -1}}

Both sets of the solution are already in contradiction. Mind this solves the inequalities and therefore if the {x1,x2,x3,x4} are not required to be the same anymore there might be solutions for other sets.

It is clear that the logicals can be demanded to be solved by Mathematica or by yourself. Both paths to the solution have to be the very same.

A reduction in complexity is complication by the inverse and hyperbolic. It nicer and a speed up to multiply all denominators and find instances with the corresponding polynomials. Since in both problems all variables are ordered no change in the order in the inequalities occurs. It is an speed up already in the question that the order is given. This might, on the other hand, prohibits to find solutions.

A big deal is the number of inequalities given. There are four independent variables that have to satisfy up to eight or five inequalities in the first problem and eight in the second. A good problem has as many inequalities as variables. All others are ill-posed with increasing ill-posedness. They can be solved in cases by chance or design.

I can too am able to solve the problem with three independent variables and the lesser inequalities:

FindInstance[
 0 < x3 < x2 < x1 < 1 && 
  1/x1 + 1/(x1 - x2) + 1/(x1 - x3) < 1/(1 - x1) && 
  1/x2 + -1/(x1 - x2) + 1/(x2 - x3) < 1/(1 - x2) && 
  1/x3 - 1/(x1 - x3) - 1/(x2 - x3) < 1/(1 - x3), {x1, x2, x3}, Reals]

{{x1 -> 319/384, x2 -> 97/192, x3 -> 7/40}}

in no real long time.

So take the steps inequality by inequality:

FindInstance[
 0 < x4 < x3 < x2 < x1 < 1 && 
  1/x1 + 1/(x1 - x2) + 1/(x1 - x3) < 1/(1 - x1) && 
  1/x2 + -1/(x1 - x2) + 1/(x2 - x3) < 1/(1 - x2) && 
  1/x3 - 1/(x1 - x3) - 1/(x2 - x3) < 1/(1 - x3), {x1, x2, x3}, Reals]
{{x1 -> 319/384, x2 -> 97/192, x3 -> 7/40, x4 -> 7/80}}

That solves immediately, no problem.

FindInstance[
 0 < x4 < x3 < x2 < x1 < 1 && 
  1/x1 + 1/(x1 - x2) + 1/(x1 - x3) + 1/(x1 - x4) < 1/(1 - x1) && 
  1/x2 + -1/(x1 - x2) + 1/(x2 - x3) < 1/(1 - x2) && 
  1/x3 - 1/(x1 - x3) - 1/(x2 - x3) < 1/(1 - x3), {x1, x2, x3, 
  x4}, Reals]
{{x1 -> 4099008467319/4810363371520, x2 -> 8355/16384, 
  x3 -> 7207/40960, x4 -> 1/128}}

But the next inequality set with the x4 added enlarges already the computing to very large.

This can be done with the other inequalities too. Just two of them extended with x4 cause the expansion in computing time.

Mathematica methods behind FindInstance, Reduce, and alike are too much related to fundamental geometry to be optimized for higher dimensions. As long as these are simple extensions to 3D the advantages remain in many situations.

The few speedups are not suitable enough for these problems. In many cases as in this one, a geometric representation of the problem is nice, but it is not available. Only projections are possible. Remember the Tesseract, the 4-dimensional-cube, the projections are really different from intuition. So like the approximate reduction, the results will be far from the truth. RegionPlot is a nice path to visuality.

Possible for parallel computers the computing time will be more moderate. The concept of taxation for x4 might be worth an attempt. Use the 3D result and look for x4 alone. Since x4 is the smallest this might be a got result close to the true result.

On the basis of 4 inequalities and an extra condition of ordered results, Eliminate may be a better path for dimension reduction in this case. For me Eliminate works with the equalities but not much faster.

{x1 -> 4099008467319/4810363371520, x2 -> 8355/16384, 
      x3 -> 7207/40960, x4 -> 1/128}

is a good approach since x4 is small. There might be many others.

$\endgroup$
2
  • 1
    $\begingroup$ "A good problem has as many inequalities as variables. All others are ill-posed with increasing ill-posedness" This is just utterly wrong. $\endgroup$ – Henrik Schumacher Jun 6 '20 at 20:39
  • $\begingroup$ You say that the first output of FindInstance "Is the unique solution for the second inequality given." This is not true. Ask FindInstance for 5 answers and it will give you 5 different answers. $\endgroup$ – bill s Jun 7 '20 at 1:41

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.