How "hard" is it to maximize a polynomial function subject to linear constraints? General Problem

Suppose we have a multivariate polynomial function $f(\mathbf{x})$, and several linear functions $\ell_i(\mathbf{x})$. What is known about the complexity of solving the following optimization problem?

\begin{align*}
 \text{Maximize} &amp; \;\; f(\mathbf{x}) \\
  \text{Subject to: } &amp; \;\, \ell_i(\mathbf{x}) \le 0\text{ for all } i 
\end{align*}

We can assume that the region determined by the constraints is bounded.

Related, but More Specific, Problem

Suppose we have a bounded polytope (represented as the intersection of a set of linear inequalities). 
I want to compute the maximum volume of an (axis parallel) hyperrectangle completely contained in the polytope. What is the complexity of solving this problem? 

Help on either of these problems is greatly appreciated.
Your problem is NP-hard, even for polynomials of degree 2. 
The crucial reference is  


  Theodore Motzkin and Ernst Strauss  (1965)
  "Maxima for graphs and a new proof of a theorem of Turan"
  Canadian Journal of Mathematics 17, pp 533-540  


Motzkin and Strauss consider an undirected graph $G=(V,E)$ 
with vertex set $V=\{1,2,\ldots,n\}$. 
They show that the optimal objective value of the following optimization problem equals $1-1/\omega$, where $\omega$ is the clique number of $G$:

\begin{eqnarray*}
\max &amp;&amp;\sum_{ij\in E} x_ix_j \\[2ex]
s.t. &amp;&amp;\sum_{i\in V} x_i=1 \\[1ex]
&amp;&amp; 0\le x_i\le 1~~~ \text{ for all $i\in V$}
\end{eqnarray*}

Since computing the clique number is NP-hard, this implies the NP-hardness of maximizing a multivariate polynomial function subject to linear constraints.