<p>Your problem is NP-hard, even for polynomials of degree 2. 
The crucial reference is  </p>

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

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

<p><span class="math-container">\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*}</span></p>

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

CC BY-SA 4.0
2019-08-22T21:19:13.837Z
In an optimal solution, the value of each $x_v$ should be $1/\omega$ if $v$ is in the clique (and $0$ elsewhere), and the optimal objective value coincides with $(1-1/\omega)/2$. This is because giving value $1/\omega$ to each clique vertex means that each of the $(\omega^2-\omega)/2$ clique edges contributes $1/\omega^2$ to OPT. The natural generalization of this same calculation shows that this is optimal.
Yonatan N
CC BY-SA 4.0
2018-07-24T16:30:45.417Z
2020-05-31T10:08:48.877Z
2020-05-31T10:08:48.877Z
Gamow
<p><strong>General Problem</strong></p>

<p>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?</p>

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

<p>We can assume that the region determined by the constraints is bounded.</p>

<p><strong>Related, but More Specific, Problem</strong></p>

<p>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? </p>

<p>Help on either of these problems is greatly appreciated.</p>

CC BY-SA 4.0
2018-07-27T06:02:41.200Z
You might want to ask your second problem separately, in a separate post.
D.W.
<cc.complexity-theory><complexity-classes><time-complexity><linear-programming><polynomials>
How "hard" is it to maximize a polynomial function subject to linear constraints?
Naysh
# How "hard" is it to maximize a polynomial function subject to linear constraints?

(Asked by: username_0 on 2018-07-24)

**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} & \;\; f(\mathbf{x}) \\
\text{Subject to: } & \;\, \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.

**Tags:** cc.complexity-theory, complexity-classes, time-complexity, linear-programming, polynomials
> **Comments:**
> **username_1**: You might want to ask your second problem separately, in a separate post.  

---

## 1 answers

### Answer by username_2 on 2018-07-24. Score: 25 | Accepted answer

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 &&\sum\_{ij\in E} x\_ix\_j \\[2ex]
s.t. &&\sum\_{i\in V} x\_i=1 \\[1ex]
&& 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.

> **Comments:**
> **username_3**: In an optimal solution, the value of each $x_v$ should be $1/\omega$ if $v$ is in the clique (and $0$ elsewhere), and the optimal objective value coincides with $(1-1/\omega)/2$. This is because giving value $1/\omega$ to each clique vertex means that each of the $(\omega^2-\omega)/2$ clique edges contributes $1/\omega^2$ to OPT. The natural generalization of this same calculation shows that this is optimal.  

---

