maximización cuadrática entera con forma semidefinida positiva

Question

No tengo experiencia en optimizaciones de enteros, pero necesitaba resolver $$\max_{\boldsymbol{x} \in \{\pm 1\}^N}\; \boldsymbol{x}^{\mathrm{T}}G\boldsymbol{x}$$ donde $G$ es un valor real $N\times N$ matriz semidefinida positiva de (bajo) rango $r$ .

Como me pareció divertido, no leí mucho antes de ponerme manos a la obra. Para $r>1$ He conseguido demostrar que el problema puede resolverse exactamente con la complejidad $\mathcal{O}\left(N^{r-1}\right)$ .

A continuación empecé a leer literatura, pero típicamente sólo me encontré con el caso de una minimización con una matriz semidefinida positiva de alto rango $G$ . Supongo que la razón es que mi caso es demasiado simple para ser estudiado. Ahora me pregunto si existen buenas referencias para mi caso.

Gracias/Fredrik

Answer 1

La razón por la que sólo encontraste minimización tiene que ver con la convexidad. Los algoritmos exactos para programas enteros (algoritmos que garantizan la búsqueda de un óptimo demostrable, si se dispone de tiempo y memoria suficientes) suelen seguir alguna versión del marco "branch-and-bound", que requiere la capacidad de calcular límites (límites inferiores para problemas de minimización, límites superiores para problemas de maximización) de forma eficiente a partir de soluciones parciales. Esto suele hacerse resolviendo la relajación continua del problema, lo que en su caso significaría sustituir el dominio $\lbrace \pm 1 \rbrace ^N$ con el hipercubo $[-1, 1]^N$ . El mínimo (máximo) de una función convexa (cóncava) es relativamente fácil de encontrar. Tu función objetivo es convexa, pero necesitas el máximo, que es donde las cosas se ponen difíciles.

Haciendo una conversión variable de $x_i\in \lbrace -1, 1\rbrace$ à $y_i\in \lbrace 0, 1\rbrace$ tu problema se convierte en un optimización cuadrática binaria sin restricciones (QUBO). Puede que quieras investigar la literatura sobre QUBOs.