Take the 2-minute tour ×

How hard is it to solve a system of equalities of the form

$a_{k1}x_1^k + \cdots + a_{kn}x_n^k = b_k$

with $k$ ranging from $1$ to $m$? I realize that this is a non-convex system but it seems plausible that it might be tractable. If the theoretical complexity is bad, how might one go about finding a feasible solution to such a system in practice? In my case I have $m < n \leq 10$. We also happen to know that $x_i \geq 0$, in case that helps. Other suggestions for tags are welcome.

share|improve this question
The short answer is: very hard. You might get a better response if you stated the actual problem you want to solve. –  Chris Godsil Apr 23 '12 at 16:13
Asymptotically, for large values of $n$ or $m$, you're in deep trouble. For small values of $m$ and $n$ there are some interesting and useful approaches that can work very well in practice. How big are your $m$ and $n$? –  Brian Borchers Apr 23 '12 at 17:26
your only real bet might be for the case when $a_{kj}=a_{1,j}$ for all $k$ and $j$. Then you could use Prony's method. –  Dima Pasechnik Apr 23 '12 at 18:10
Thanks, Chris and Brian -- this is very helpful. Brian: Both $m$ and $n$ are quite small, say $10$ or so (and I have amended the question appropriately). Is there some sort of branch-and-bound based approach that might be feasible here? Chris: The actual problem is one communicated to me by a colleague involving estimation of some physical constants, so I do not have more detail yet to give (it will be forthcoming after we discuss it in the near future) –  Jennifer Gao Apr 23 '12 at 18:22

1 Answer 1

Your problem might be small enough that it is within the range of polynomial optimization techniques based on SDP relaxations of sums of squares problem. This has been implemented in software packages such as GLOPTIPOLY. See


share|improve this answer
Your problem might well have infinitely many solutions. It might also have no solutions! You should consider whether or not you would like to find a least squares solution rather than an exact solution, and whether you want to pick out some particular solution if there are many solutions. Both of these could be dealt with in the polynomial optimization approach that I've suggested. –  Brian Borchers Apr 24 '12 at 0:22

Your Answer


