Ask Your Question
1

testing if system of inequalities has solution

asked 2018-01-22 13:05:31 -0500

ctst gravatar image

updated 2018-01-22 13:35:51 -0500

Hi there,

I have a big system of inequalities (~1500 inequalities, 45 variables) and want to check, if there exists a real solution to it. Trying out the 'solve' and 'solve_ineq' takes a huge amount of time or it breaks during calculation and after checking some of the questions here I even assume the solve-function is broken and sometimes gives wrong results. Does anybody know about a function/system which returns in a responsible time and reliable if there exists a solution or not (existence is enough) (I want to use this in an actual proof, so it would be useless, if I can't trust the result).

In my use case I have the variables $a1, ..., a15, b1,...,b15,c1,...,c15 \in \mathbb R^+$ and my inequalities are all of the form $$ \frac{f(a1,...,a15)}{g(c1,\dots, c15)} \geq \frac{f'(a1,\dots,a15)}{g'(c1,\dots, c15)}$$ (and same for combinations of (a,b) and (b,c)) for given linear functions $f,f',g,g'$ (i.e. multivariate polynomials with degree at most 1), so restricting to the variables $ai$ we get a system of linear inequalities (but even trying to solve these takes long/doesn't work with the solve function).

Actually more accuratly I have indexed sets $$F_{a,b} ={{(f_i,g_i) | i \in I }, F_{c,b} ={(p_i,q_i) | i \in I } ,F_{a,c} ={(r_i,s_i) | i \in I } $$ and want to show, that if there exists a solution $(a,b)$ of $$\frac{f_k(a)}{g_k(b)} = max_i \frac{f_i(a)}{g_i(b)}$$ then there exists a solution $(c)$ to $$\frac{r_k(a)}{s_k(c)} = max_i \frac{r_i(a)}{s_i(c)}$$ $$\frac{p_k(c)}{q_k(b)} = max_i \frac{p_i(c)}{q_i(b)}$$

So far I have a the follwing snippet:

#fractionAB are the saved fractions from above, a,b,c are arrays with e.g. a=[a1,a2,...,a15]
stopIt=False
for maxStretch in cands:    #cands is the index set I
    ineq=[fractionAB.get(maxStretch) >= fractionAB.get(cand)  for cand in cands]
    if solve(ineq,a+b):
         #try here if there exists a middle point on the geodesic, i.e. geodesic exists
        ineq.extend([fractionAC.get(maxStretch) >= fractionAC.get(cand)  for cand in cands])
        ineq.extend([fractionCB.get(maxStretch) >= fractionCB.get(cand)  for cand in cands])
        if not solve(ineq, a+b+c):
            stopIt=True
    print 'Tested for candidate ' , maxStretch
    if stopIt:
        break

I know, there is room for improvement e.g. at reusing to first solution from (a+b), the problem is, that even that first system pretty much kills the calculation. Also multiplying the denominators on each side doesn't seem to help.

PS: The mathjax seems to be broken on this site, since the code for leftbraces seems to vanish (hence the ugly "fix" above).

edit retag flag offensive close merge delete

Comments

Could you please provide the code for the inequalities ? Without a concrete example, it is hard to say.

tmonteil gravatar imagetmonteil ( 2018-01-22 14:18:55 -0500 )edit

The problem is, there are too many inequalities to post them here and to get there I already used a few hundreds of lines. I could give you access on CoCalc instead, there I have the fractions saved as an object. The only thing there is, that the calculation stops because of ram restrictions. (It even kills my computer when I try to run it one mine.) Since solve and solve_ineq returns the actual solutions, I hope there was a lighter method which returns only the existence of a solution.

ctst gravatar imagectst ( 2018-01-22 17:14:34 -0500 )edit

To summarize, we do not have the code, we do not know how the functions are implemented, we do not have a similar minimal situation with only 2 or 3 (instead of 15) variables, $f'$ is possibly not the derivative of $f$, we can not specialize (e.g. $a=b=c$) to have a start, then start a random walk to find the better direction to move... In such a case i can only suggest to pick random variables / values for $a,b,c$, then use a "win function" telling how far is the random point under examination from a valid solution, e.g. taken from the negative differences of fractions of functions, that should become positive, by summing them... Then take some $3^{15}$ points in the neighborhood by adding $\{-\epsilon,0,\epsilon\}^{\times15}$ and recalculate. Braces were typed as slash-slash-brace.

dan_fulea gravatar imagedan_fulea ( 2018-03-02 05:55:10 -0500 )edit

1 answer

Sort by ยป oldest newest most voted
0

answered 2018-06-21 17:08:05 -0500

slelievre gravatar image

Using qepcad might give better results than using solve.

Install by doing

sage -i qepcad

and then follow

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-01-22 13:05:31 -0500

Seen: 132 times

Last updated: Jun 21