0
$\begingroup$

I need to check whether an inequality can have solutions in the real numbers, given some extra constraints on the variables. I suspect that no solutions exist but I would like some verification of that claim. My code is the following:

ineq := {(2/9) * (l1 + l2 + l3)^2 > RankedMax[
  Eigenvalues[
   Transpose[{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, t2, 
       t3 + l3}}].{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, 
      t2, t3 + l3}}], 1] + 
 RankedMax[
  Eigenvalues[
   Transpose[{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, t2, 
       t3 + l3}}].{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, 
      t2, t3 + l3}}], 2]};
con1 = {1 >= l1 >= -1};
con2 = {1 >= l2 >= - 1};
con3 = {1 >= l3 >= -1};

In practice I have four more constraints on the $t_i$ and $\lambda_i$ but to keep things simple I have omitted them. Now, since I am not optimistic that the Reduce command could track the problem, I use NSolve instead. It would be great if I can find even one solution to this inequality and not a general characterisation of the solutions, if they exist (I doubt it). Thus, I run the command:

NSolve[{ineq[[1]], con1[[1]], con2[[1]], con3[[1]]}, {l1, l2, l3, t1, t2,t3}]

However the program runs forever and even if I simplify it by letting the $t_i$ be equal to zero, in which case I know there are no solutions to the inequality by a slightly different analysis, I still get no quick answer. I try the simple case with the following command:

NSolve[{ineq[[1]], con1[[1]], con2[[1]], con3[[1]], t1 == 0, t2 == 0, 
t3 == 0}, {l1, l2, l3}]

This makes me think that my code is not very good and I am wondering if there is something that can be done to make this actually work.

Thank you in advance!

$\endgroup$
1
$\begingroup$

I find that when the solver options are behaving incredibly slowly, the local minimizers and maximizers (FindMinimum and FindMaximum) can help. We just have to rewrite the system a little bit. This is based on the question as it was originally posted, but this approach can prove helpful to try to quickly find a solution if it exists:

lhs = (2/9)*(l1 + l2 + l3)^2;
rhs = RankedMax[
     Eigenvalues[
      Transpose[{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, t2, 
          t3 + l3}}].{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, 
         t2, t3 + l3}}], 1]^2 + 
   RankedMax[
     Eigenvalues[
      Transpose[{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, t2, 
          t3 + l3}}].{{t1 + l1, t2, t3}, {-t1, -t2 - l2, -t3}, {t1, 
         t2, t3 + l3}}], 2]^2;

First, to simplify the manipulation of the inequality, I separated the left and right hand sides. We want to see if we can find a scenario where lhs > rhs, which is the same as finding a scenario where lhs - rhs > 0. I declare the constraints and the final system as follows:

constraints = {1 >= l1 >= -1, 1 >= l2 > -1, 1 >= l3 >= -1};
sys = {lhs - rhs, Sequence @@ constraints};

We can use FindMaximum to try to maximize lhs - rhs, and see if we can find a maximum greater than 0. I try the local maximizer first because if a solution exists it will probably be found rather quickly, but if we are trying to prove that a solution does not exist we would need to use a global maximizer, such as Maximize.

max = FindMaximum[
  sys, {{t1, 1/2}, {l1, 1/2}, {t2, 1/2}, {l2, 1/2}, {t3, 1/2}, {l3, 1/2}}]

{0.327656, {t1 -> 0.0129505, l1 -> 0.863786, t2 -> -0.0120477, l2 -> 0.90072, t3 -> -0.0139592, l3 -> 0.904819}}

The maximum value found is greater than 0 (0.327656), and the it provides a sensible set of parameters to achieve that maxima. However, let's check that it satisfies the original inequality and the constraints:

{lhs > rhs, constraints} /. max[[2]]

{True, {True, True, True}}

Thus, by example, this inequality does have at least one solution.

Unfortunately, this approach does not find a clear cut solution for the updated question using FindMaximum or NMaximize.

$\endgroup$
  • $\begingroup$ First of all, thanks for the answer! Then, apologies but I found some mistakes on the posted code: I had extra squares on the RankedMax's. After fixing this and running your code again, I get the following answer: {-1.28856*10^-15, {t1 -> 0.0000500457, l1 -> -0.000292867, t2 -> 0.0000500457, l2 -> -0.000292867, t3 -> 0.0000500492, l3 -> -0.000292906}} Does this, in your opinion, demonstrate that maybe no solutions exist? $\endgroup$ – AG1123 Dec 6 '18 at 7:43
  • $\begingroup$ Assuming this is the case, how can I modify your code so that I can try to get an exact answer (e.g. using Reduce or Solve) to whether this inequality can ever be fulfilled? $\endgroup$ – AG1123 Dec 6 '18 at 8:19
  • 2
    $\begingroup$ FindMaximum is a local solver, so it's not sufficient proof that there are no solutions. NMaximize is a global solver, but it is numerical in nature, so it's not airtight proof that there is no solution. Maximize is a global symbolic solver, but probably won't be any faster than Solve or Reduce here. This approach isn't easily modifiable to prove the non-existence of a solution, sorry. This won't make Solve or Reduce any faster here either. With the unedited question it was easy to show that there was at least one solution, but your problem's a lot harder now. $\endgroup$ – eyorble Dec 6 '18 at 8:44
  • $\begingroup$ I see. That was my suspicion too. Anyway, thanks a lot for the help! I definitely got something from your answer, so if there are no answers that completely solve my problem soon, I will accept yours. $\endgroup$ – AG1123 Dec 6 '18 at 9:16

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.