# Minimizing a polynomial with millions of monomials

I need to minimize a single polynomial $$P(x_1,x_2,...,x_n)$$ with the constraint that for each $$i$$, $$0\leq x_i \leq 1$$. The number of variables in my practical problem is at most $$50$$. The degree is at most $$10$$. The number of monomials is about 2 million.

Are there any tools that can handle such minimization problems? An approximate solution which is guaranteed to be off by some multiplicative factor would also be welcome.

• What have you read about the problem so far? The optimality conditions form a large system of polynomial equations, which systems such as Bertini solve. Have you looked at the papers that discuss these sorts of problems? – Wolfgang Bangerth Jul 30 at 21:57
• I have read some material related to SOS methods, which seem to provide an upper bound, at least in the case of unconstrained optimization (when each variables can range over $R$). I don't know if this works for constrained optimization. In particular, in my case the variables are allowed to range between 0 and 1. If SOS works in this case, it would be better than nothing. However, it seems that the complexity of the SOS algorithms $n^{f(d)}$ in the worst case for some function $f$. Since my $d=10$, I don't know if such methods will work. – Springberg Jul 30 at 22:09
• Could you solve it as a geometric program? – Richard Jul 31 at 17:06
• And can you post a toy problem, or code that generates an instance of the problem you wish to solve? – Richard Jul 31 at 17:18