8
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.