# 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} & \;\; 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.

• You may want to take a look at this paper. – Rodrigo de Azevedo Jul 26 '18 at 20:16
• You might want to ask your second problem separately, in a separate post. – D.W. Jul 27 '18 at 6:02

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 coincides with the reciprocal $$1/\omega$$ of the clique number $$\omega$$ 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.

• 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 Aug 22 '19 at 21:19