As a practical matter, a lot depends on $n$ and the dimension of $x$.  If the problem is small enough then you might not be in deep trouble.  If the problem is large (e.g. $x$ might have thousands of components), then it could be very hard.  
 
If the problem is quite small, then you might consider using an approach that exploits the polynomial structure of your optimization problem.  There are convex relaxations of such polynomial optimization problems that provide very tight lower bounds and software can often use these lower bounds to find a globally optimal solution.  See for example the Gloptipoly2 software:
 
  http://homepages.laas.fr/henrion/software/gloptipoly2/