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.

  • 1
    $\begingroup$ 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? $\endgroup$ – Wolfgang Bangerth Jul 30 '19 at 21:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Springberg Jul 30 '19 at 22:09
  • 1
    $\begingroup$ Could you solve it as a geometric program? $\endgroup$ – Richard Jul 31 '19 at 17:06
  • 1
    $\begingroup$ And can you post a toy problem, or code that generates an instance of the problem you wish to solve? $\endgroup$ – Richard Jul 31 '19 at 17:18

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.