¿Qué tan "difícil" es maximizar una función polinómica sujeta a restricciones lineales?

Problema general

Supongamos que tenemos una función polinomial multivariada y varias funciones lineales . ¿Qué se sabe sobre la complejidad de resolver el siguiente problema de optimización? $f(\mathbf{x})$ $\ell_i(\mathbf{x})$

\begin{aligned} Maximizar & F (X) \\ Sujeto a: & ℓ_{yo} (X) \leq 0 0 para todos yo \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 suponer que la región determinada por las restricciones está limitada.

Problema relacionado, pero más específico

Supongamos que tenemos un politopo acotado (representado como la intersección de un conjunto de desigualdades lineales). Quiero calcular el volumen máximo de un hiperrectángulo (eje paralelo) completamente contenido en el politopo. ¿Cuál es la complejidad de resolver este problema?

Ayuda en cualquiera de estos problemas es muy apreciada.

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

Es posible que desee echar un vistazo a este documento .

Rodrigo de Azevedo

Es posible que desee preguntar su segundo problema por separado, en una publicación separada.

Respuestas:

Su problema es NP-hard, incluso para polinomios de grado 2. La referencia crucial es

Theodore Motzkin y Ernst Strauss (1965)
"Maxima para gráficos y una nueva prueba de un teorema de Turan"
Canadian Journal of Mathematics 17, pp 533-540

Motzkin y Strauss consideran un grafo no dirigido $G=(V,E)$ con conjunto de vértices $V=\{1,2,\ldots,n\}$ . Muestran que el valor objetivo óptimo del siguiente problema de optimización coincide con el recíproco $1/\omega$ del número de camarilla $\omega$ de $G$ :

\begin{array}{rcl} max & \sum_{i j \in E} x_{i} x_{j} \\ s . t . & \sum_{i \in V} x_{i} = 1 \\ 0 \leq x_{i} \leq 1 for all i \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*}$

Dado que calcular el número de camarilla es NP-duro, esto implica la dureza NP de maximizar una función polinomial multivariada sujeta a restricciones lineales.

Gamow
fuente

En una solución óptima, el valor de cada debe ser si está en la camarilla (y otra parte), y el valor objetivo óptimo coincide con . Esto se debe a que dar valor a cada vértice de la camarilla significa que cada uno de los bordes de la camarilla contribuye con a OPT. La generalización natural de este mismo cálculo muestra que esto es óptimo.

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