# Solving a particular nonlinear system of equalities

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.

-
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