# Software tools for medium-scale systems of polynomial equations

I am attempting to find all real solutions of a system of 12 polynomial equations in 12 unknowns. The equations each have total degree 6 and contain up to 1700 terms. I am only interested in real solutions. The equations were derived as the gradients of a sum-of-squares cost function, which I am attempting to find all global optima of. I believe there are a finite number of real solutions but I have not confirmed this yet. I have floating point coefficients and I'm looking for numerical solutions (rather than symbolic solutions).

Which software packages (and which functions specifically) are generally most promising to solve such a problem?

I am aware of various functions in Maple, Matlab, and Mathematica that can solve systems of polynomial equations but there are a large number of options in each software package and I'm interested in advice on where I should be looking first for problems of this scale.

• Seems to me like you should be looking at tools to solve the optimization problem rather than tools to solve the first order conditions. – wonko Jul 22 '14 at 18:50
• @wonko I am very much interested in global optimization rather than gradient-based iterative optimization in this problem. Methods like Gauss-Newton / Levenberg-Marquardt will not work. Having said that, are there any general purpose global optimization tools you would recommend? – Alex Flint Jul 22 '14 at 20:08
• General global optimization is quite hard unless your problem has nice structure. So the first direction I would look is to exploit structure, perhaps look for similar problems that have already been solved. If you're OK with providing some more details for your problem, I could help more. Things like the structure of the objective function and whether any of the variable are constrained. – wonko Jul 22 '14 at 21:17
• If you want a list of general purpose global optimization solvers, start with NEOS. I've used BARON before and it's quite good but slow and not open source. If your problem is quadratic a good open source solver to look at is SCIP. SCIP interfaces with MATLAB so you might find it easier to use as well. – wonko Jul 22 '14 at 21:19
• @wonko Thanks for the NEOS link - I was not aware of that service before. I would certainly value your help with this optimization problem (thanks!), and I'm happy to provide more details. I'm attempting to solve a problem in visual inertial navigation where the variables represent the trajectory of a device and the cost terms are related to sensor measurements captured over time by that device. Each term of the cost function looks like $(f(x)-y)^2$ where $y$ is a sensor measurement. There are no constraints on the variables except that they must be real numbers. – Alex Flint Jul 23 '14 at 14:28