Sobre la Programación Entera Cuadrática

Question

Tengo el programa de números enteros cuadráticos sobre $\mathbb{Z}^n$

$\displaystyle\min_{z \in \mathbb{Z}^n} \Phi (z) = \frac{1}{2} z^T Q z - r^T z + s$

sujeto a $G z = h$, y $z_i \in \{0,1,2,\dots, b_i\}$ para todo $i \in \{1,2,\dots,n\}$, donde $Q$ es simétrica positiva-definida. Además, $G, h$ son de valor entero y, por lo tanto, supongo que $\{z \in \mathbb{Z}^n : G z = h\}$ define una sublátila de $\mathbb{Z}^n$.

Supongamos que resolvemos el programa cuadrático relajado sobre $\mathbb{R}^n$

$\displaystyle\min_{x \in \mathbb{R}^n} \Psi (x) = \frac{1}{2} x^T Q x - r^T x + s$

sujeto a $G x = h$, y $0 \leq x_i \leq b_i$ para todo $i \in \{1,2,\dots,n\}$. Sea $x_{opt} \in \mathbb{R}^n$ el minimizador de $\Psi$. Podemos definir un $n$-cubo (en $\mathbb{Z}^n$) que contiene a $x_{opt}$ tomando el suelo/techo de cada componente de $x_{opt}$. Intersectamos este $n$-cubo con la sublátila de enteros definida por $G z = h$, y evaluamos $\Phi$ en todos los puntos de esta intersección. Sea $z^{\ast}$ el punto en esa intersección que minimiza $\Phi$. Sea $z_{opt}$ el minimizador del programa cuadrático original. ¿Podemos decir que $z_{opt} = z^*$? No sé nada de programación entera, así que pido disculpas de antemano si mi pregunta es tonta/elemental...

En otras palabras, ¿se puede resolver un programa de números enteros cuadráticos resolviendo un programa cuadrático real relajado, y luego buscando en el vecindario de la solución real? Esto parece funcionar para $n = 1$ y $n = 2... pero también parece demasiado bueno para ser cierto en general. Si en general $z_{opt} \neq z^{\ast}$, ¿podemos (al menos) cuantificar cuánto subóptimo es $z^{\ast}$?

¡Cualquier comentario será bienvenido!

Answer 1

No creo que puedas esperar encontrar una buena aproximación de esta manera. Considera el caso especial donde $r=0$ y $s=0$. Entonces, el primer problema parece ser equivalente a encontrar el vector más corto en una red entera. El segundo problema es trivial, siendo la solución $x=0$. Se cree que el problema del vector más corto es difícil y no se conocen buenos algoritmos de aproximación. Todos los algoritmos conocidos encuentran aproximaciones que degradan de forma polinómica en la dimensión.

Ver, por ejemplo,

http://en.wikipedia.org/wiki/Lattice_problem

o uno de los muchos artículos excelentes sobre criptografía basada en redes.

Answer 2

El problema relajado de programación cuadrática es una distracción. Es cierto que la programación cuadrática sobre $\mathbb{R}$ con desigualdades lineales puede resolverse en la práctica, por una razón porque es un caso especial de programación convexa. Pero en la pregunta planteada, la desigualdad $0 \leq x_i \leq b_i$ llegó de la nada. La relajación correcta es aún más simple: solo debes minimizar $\Phi(z)$ sobre todo $\mathbb{R}^n$, y el mínimo está directamente en $z_0 = Q^{-1}r.

Después de eso, Mitch tiene razón aproximadamente. La pregunta tal como está formulada es exactamente el problema del vector más cercano, que está relacionado con el problema del vector más corto que Mitch menciona. La constante $s$ no es importante. La pregunta es encontrar el punto reticular entero $z$ que está más cerca de $z_0$ en la métrica definida por $Q$. Si deseas, puedes cambiar la distancia a la distancia euclidiana y cambiar el retículo del retículo entero estándar a algo más, aplicando el operador $Q^{-1/2}$. $L = Q^{-1/2}(\mathbb{Z}^n)$ es un cierto retículo, y estás buscando el punto que está más cerca en distancia euclidiana de $Q^{-1/2}(z_0).

En cualquier dimensión fija $n$, los problemas del vector más cercano y más corto pueden resolverse en tiempo polinómico. Hay varios algoritmos de reducción de retículos que solo buscan polinomialmente muchos puntos.

Si la dimensión $n$ es un parámetro, entonces la situación es muy diferente. Para muchos propósitos, la gente está feliz con solo un vector cercano o un vector corto, no necesariamente el más cercano o el más corto. El problema varía mucho en dificultad dependiendo de qué tan cerca es lo suficientemente bueno, o equivalentemente si hay pocos puntos reticulares que sobresalen como mucho más cerca que todos los demás. Un vector cercano es intuitivamente más difícil que un vector corto, pero hay un resultado teórico que sugiere que son aproximadamente equivalentes en dificultad. Tomando los requisitos estrictos posibles, encontrar un vector cercano es NP-duro. Hay niveles intermedios de cercanía, dados por una tolerancia que crece con $n$, que parecen difíciles pero probablemente no son NP-duros. Otros niveles de cercanía se pueden hacer en tiempo polinómico. Hay muchos artículos sobre estos dos problemas, y la página de Wikipedia que Mitch menciona es una revisión bastante buena: La sección GapCVP aborda las versiones aproximadas de la pregunta que menciono brevemente aquí.

Una debilidad de la página de Wikipedia es que tiene más que decir sobre la dificultad que sobre los algoritmos prácticos. Pero menciona dos algoritmos importantes: Lenstra-Lenstra-Lovasz y Ajtai-Kumar-Sivakumar.