0
$\begingroup$

I am trying to find a way to automate solving for all possible numerical values in a large multivariable system of equations. By this I mean equations such as

k(90)*g(-3)=434

and

k(47)*g(-5)=237

Essentially I want to solve for variables such as g and k in the context of one another and all the equations (the equations are much more complex - I am simplifying for clarity).

Is this a feasible approach and if so how would I go about achieving this? In addition, is this doable if I want the product value to be within a set number range? For example,

k(47)*g(-5)= a number from 217-257

If this is also doable, I am eager to hear it.

Apologies if I sound incoherent-- if any clarification is needed feel free to ask. Many thanks in advance.

Edited to add: These equations will all be either linear or quadratic in nature. I am looking for integer solutions preferably, but finding real number solutions would also work.

$\endgroup$
2
  • $\begingroup$ There are ways. The best method depends a lot on what types of equations you have. Are all of the equations quadratic? Are you looking for solutions that are integers, or real numbers, or something else? Please edit the question to provide more details. $\endgroup$
    – D.W.
    Jan 8 at 4:38
  • $\begingroup$ Just added an edit for clarification. $\endgroup$ Jan 8 at 6:03

2 Answers 2

1
$\begingroup$

If we take the equalities from your example:

$$\begin{eqnarray*} 90k - 3g & = & 434 \\ 47k - 5g & = & 237 \end{eqnarray*}$$

Well, that's just a linear system, and can be solved by Gaussian elimination or other similar technique.

If we look at the inequalities:

$$\begin{eqnarray*} 47k - 5g & \le & 257 \\ -47k + 5g & \le & 217 \\ \end{eqnarray*}$$

That's a linear program. If you want integer solutions, then this is exactly the integer linear program feasibility problem, which is known to be NP-hard. For rational solutions, this is solvable in polynomial time, but in practice, the simplex method works extremely well.

If you have quadratic equality constraints, then Quadratic programming isn't quite what you want, because most of the algorithms for that only talk about quadratic objective functions, not equality constraints. Someone else might know better than I do on this point, but you may want to look into something like cylindrical algebraic decomposition, which in theory should work with any polynomials.

$\endgroup$
0
$\begingroup$

The problem is NP-hard, when you have quadratic constraints.

Solving over the reals: then your problem is an instance of quadratically constrained quadratic programming (QCQP), and you can find a single solution with a QCQP solver. Finding all solutions is challenging. One standard approach is to find one solution, then add a "blocking constraint" to rule out that one solution and solve again. For instance, if you have the single solution $x=13$, $y=15$, it might work to add the blocking constraint $(x-13)^2+(y-15)^2 > 0$ to the system of equations, and solve it again. (This requires the solver to allow "$>$" inequalities. If it only accepts "$\ge$" inequalities, one possibility is to try picking some small $\epsilon$, and require $\ge \epsilon$ instead of $>0$, but this is a heuristic that is not guaranteed to work.) There might be better ways.

You could also try Groebner bases.

Solving over the integers: It appears it is undecidable whether there exists any solution over the integers. See https://math.stackexchange.com/a/616704/14578. I am not an expert in this area, so I can't independently confirm or refute that statement.

Standard warning: there might be exponentially many solutions, so if you really want to enumerate all solutions, then enumerating all of them can take exponential time in the worst case.

Related: Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?, https://en.wikipedia.org/wiki/System_of_polynomial_equations, Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP?, https://math.stackexchange.com/q/2084636/14578, https://math.stackexchange.com/q/1366528/14578.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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