3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Seems to me like you should be looking at tools to solve the optimization problem rather than tools to solve the first order conditions. $\endgroup$ – wonko Jul 22 '14 at 18:50
  • $\begingroup$ @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? $\endgroup$ – Alex Flint Jul 22 '14 at 20:08
  • 1
    $\begingroup$ 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. $\endgroup$ – wonko Jul 22 '14 at 21:17
  • $\begingroup$ 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. $\endgroup$ – wonko Jul 22 '14 at 21:19
  • $\begingroup$ @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. $\endgroup$ – Alex Flint Jul 23 '14 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.