Quão "difícil" é maximizar uma função polinomial sujeita a restrições lineares?

Problema Geral

Suponha que tenhamos uma função polinomial multivariada e várias funções lineares . O que se sabe sobre a complexidade de resolver o seguinte problema de otimização? $f(\mathbf{x})$ $\ell_i(\mathbf{x})$

\begin{aligned} Maximize & f (x) \\ Subject to: & ℓ_{i} (x) \leq 0 for all i \end{aligned}

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

Podemos assumir que a região determinada pelas restrições é limitada.

Problema relacionado, mas mais específico

Suponha que tenhamos um polítopo limitado (representado como a interseção de um conjunto de desigualdades lineares). Desejo calcular o volume máximo de um hiper-retângulo (paralelo ao eixo) completamente contido no politopo. Qual é a complexidade de resolver esse problema?

A ajuda em um desses problemas é muito apreciada.

cc.complexity-theory complexity-classes time-complexity linear-programming polynomials Naysh
fonte

Você pode dar uma olhada neste artigo .

Rodrigo de Azevedo

Convém perguntar ao seu segundo problema separadamente, em uma postagem separada.

Respostas:

Seu problema é difícil para NP, mesmo para polinômios de grau 2. A referência crucial é

Theodore Motzkin e Ernst Strauss (1965)
"Maxima para gráficos e uma nova prova de um teorema de Turan"
Canadian Journal of Mathematics 17, pp 533-540

$G=(V,E)$ $V=\{1,2,\ldots,n\}$ $1/\omega$ $\omega$ $G$

\begin{array}{rcl} max & \sum_{Eu j \in E} x_{Eu} x_{j} \\ s . t . & \sum_{Eu \in V} x_{Eu} = 1 \\ 0 0 \leq x_{Eu} \leq 1 para todos Eu \in V \end{array}

$\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*}$

Como a computação do número de clique é NP-difícil, isso implica a NP-dureza de maximizar uma função polinomial multivariada sujeita a restrições lineares.

Gamow
fonte

Em uma solução ideal, o valor de cada deve ser se estiver na camarilha (e outro lugar), e o valor objetivo ideal coincidir com . Isso ocorre porque atribuir o valor a cada vértice de clique significa que cada uma das arestas clique contribui com para OPT. A generalização natural desse mesmo cálculo mostra que isso é ótimo.

x_{v}

$x_v$

1 / ω

$1/\omega$

v

$v$

0

$0$

(1 - 1 / ω) / 2

$(1-1/\omega)/2$

1 / ω

$1/\omega$

(ω^{2} - ω) / 2

$(\omega^2-\omega)/2$

1 / ω^{2}

$1/\omega^2$

Yonatan N