1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ The short answer is: very hard. You might get a better response if you stated the actual problem you want to solve. $\endgroup$
    – Chris Godsil
    Apr 23, 2012 at 16:13
  • $\begingroup$ 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$? $\endgroup$
    – Brian Borchers
    Apr 23, 2012 at 17:26
  • $\begingroup$ 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. $\endgroup$
    – Dima Pasechnik
    Apr 23, 2012 at 18:10
  • $\begingroup$ 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) $\endgroup$
    – Jennifer Gao
    Apr 23, 2012 at 18:22

1 Answer 1

Reset to default
1
$\begingroup$

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

http://homepages.laas.fr/henrion/software/gloptipoly3/

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Brian Borchers
    Apr 24, 2012 at 0:22

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.