11
$\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.

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ You might want to ask your second problem separately, in a separate post. $\endgroup$
    – D.W.
    Jul 27, 2018 at 6:02

1 Answer 1

Reset to default
25
$\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 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Aug 22, 2019 at 21:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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