Resumen Técnico: Desigualdades de Rango Conjunto para QCQP No Convexos

Planteamiento del Problema

El artículo aborda el desafío de generar planos de corte efectivos para programas cuadráticos con restricciones cuadráticas (QCQP) no convexos, una clase central de problemas en la Programación Lineal Entera Mixta (MINLP). Si bien las relajaciones estándar como la Técnica de Reformulación Lineal (RLT) y las relajaciones de Programación Semidefinida (SDP) (por ejemplo, la relajación de Shor), proporcionan aproximaciones convexas, estas suelen sufrir un compromiso entre la estrechez (tightness) y la dispersión (sparsity). Específicamente, las reformulaciones de autovalores y las restricciones SDP densas suelen destruir la dispersión de la formulación original del QCQP, lo que conduce a cortes computacionalmente costosos que son difíciles de integrar en los resolvedores de MINLP. Los autores buscan un marco para derivar desigualdades válidas y fuertes que preserven la dispersión de la formulación original del QCQP mientras explotan la geometría no convexa.

Metodología: Enfoque de Proyectar-luego-Elevar (Project-Then-Lift)

Los autores proponen una estrategia de "proyectar-luego-elevar" inspirada en las desigualdades de Redondeo Entero Mixto (MIR) utilizadas en la Programación Lineal Entera Mixta (MILP). La metodología procede de la siguiente manera:

1. Desigualdades Base y Proyección:
   Partiendo de dos desigualdades válidas base para la formulación extendida del QCQP (que involucra variables $x$ y la matriz elevada $X$), los autores definen un mapa afín $A_{JR}$ que proyecta estas desigualdades en un espacio de imagen bidimensional. Sean las desigualdades base $\phi_i + \langle \Theta_i, X \rangle + \theta_i^\top x \geq 0$ para $i=1,2$. La proyección mapea pares $(X, x)$ factibles a un vector $y = (y_1, y_2)$, donde $y_i$ corresponde al lado izquierdo de la $i$-ésima desigualdad.

2. Análisis del Rango Conjunto:
   El núcleo del método analiza el rango conjunto $F(\mathbb{R}^n)$ de las dos funciones cuadráticas $f_1(x)$ y $f_2(x)$ asociadas con las desigualdades base. El conjunto de puntos proyectados factibles es la intersección de este rango conjunto con un cono simplicial $K_{JR}$ definido por las desigualdades base.

   • Caso No Convexo: Los autores caracterizan el envolvente convexo cerrado del rango conjunto cuando este es no convexo. Demuestran que, bajo condiciones específicas (dependencia lineal de las partes cuadráticas), el rango conjunto toma una forma no convexa explícita, como el límite o el exterior de un cuenco parabólico.
   • Caso Convexo: Cuando el rango conjunto es convexo, proporcionan una representación de Programación Semidefinida (SDP).

3. Caracterización del Envolvente e Derivación de Desigualdades:
   Los autores derivan una descripción en forma cerrada del envolvente convexo del conjunto proyectado ($H_{JR} = \text{cl}(\text{conv}(F(\mathbb{R}^n) \cap K_{JR}))$).

   • Para los casos no convexos, el envolvente se describe mediante la intersección del cono simplicial con el cuenco parabólico o su complemento, lo que a menudo resulta en cortes "secantes" (cortes de intersección) definidos por los puntos donde los rayos del cono salen del conjunto no convexo.
   • Para los casos convexos, el envolvente se describe a través de funciones de soporte, lo que conduce a un problema de separación con restricciones SDP.

4. Elevación y Preservación de la Dispersión:
   Las desigualdades válidas derivadas en el espacio de imagen 2D se elevan de nuevo al espacio original $(X, x)$ utilizando la inversa del mapa afín. Crucialmente, debido a que la proyección se basa en solo dos desigualdades base, las desigualdades elevadas resultantes heredan la dispersión (soporte) de dichas desigualdades base. Esto evita los problemas de densidad asociados con las relajaciones SDP completas.

5. Desigualdades de Rango Mixto-Conjunto Secante:
   Extendiendo el concepto de MIR, los autores introducen "desigualdades de rango mixto-conjunto secante". Estas implican la extracción de términos "mixtos" (combinaciones lineales fraccionarias o variables continuas) de las desigualdades base para formar un par central que satisfaga las condiciones parabólicas no convexas. Esto permite manejar estructuras más complejas de manera similar a cómo MIR maneja los términos fraccionarios en MILP.

Contribuciones Clave

• Envolventes Convexos en Forma Cerrada: El artículo proporciona una caracterización completa y en forma cerrada del envolvente convexo para la intersección de un cono simplicial y un rango conjunto no convexo de dos funciones cuadráticas. Esto incluye descripciones geométricas explícitas para diversas configuraciones (por ejemplo, el ápice dentro o fuera del cuenco parabólico, rayos de recesión).
• Nuevas Familias de Cortes: Los autores introducen desigualdades de rango conjunto y desigualdades de rango mixto-conjunto secante. Estas son válidas para la formulación extendida del QCQP y se derivan mediante cortes de intersección en el espacio proyectado 2D.
• Preservación de la Dispersión: A diferencia de los cortes basados en SDP estándar, las desigualdades propuestas son dispersas. El soporte de cada desigualdad elevada está estrictamente controlado por el soporte de las dos desigualdades base utilizadas para generarla.
• Representación SDP para Casos Convexos: Para rangos conjuntos convexos, los autores proporcionan una representación semidefinida que ofrece una ruta dispersa para linealizar la relajación SDP de Shor.
• Clasificación Algorítmica: Se presenta un algoritmo para clasificar el rango conjunto como convexo o no convexo y para determinar su forma geométrica específica (por ejemplo, límite parabólico, región sólida o plano perforado).

Resultados

El artículo reporta experimentos geométricos preliminares comparando la fuerza de las desigualdades de rango conjunto propuestas frente a la relajación RLT estándar de primer nivel.

• Métrica: La fuerza se mide mediante la razón del área de la intersección entre la relajación RLT proyectada y el envolvente del rango conjunto respecto al área de la relajación RLT proyectada por sí sola. Una razón menor indica un corte más fuerte (mayor reducción de área).
• Hallazgos:
  • En casos "no recortados" (unclipped) donde el rango conjunto está enteramente contenido dentro del cono, los cortes no proporcionan reducción adicional (razón = 1).
  • En casos no convexos no triviales (por ejemplo, "Cuenco Truncado por Cuerda" y "Cuenco Truncado por Rayo"), el envolvente del rango conjunto reduce significativamente el área proyectada. La media geométrica desplazada de la razón de área osciló aproximadamente entre 0.108 y 0.490 en diferentes dimensiones y configuraciones.
  • Los casos de rango conjunto convexo (Caso 7) también demostraron una reducción de área sustancial (razones entre 0.219 y 0.403).
  • Los resultados sugieren que el enfoque propuesto puede estrechar sustancialmente la relajación proyectada construida mediante RLT.

Significancia y Reivindicaciones

Los autores afirman que este trabajo cierra la breancia entre la fuerza geométrica de los cortes de intersección y la necesidad computacional de la dispersión en los resolvedores de MINLP.

• Separación de Geometría y Dimensión: La principal significancia es el desacoplamiento del paso geométrico difícil (manejo de la no convexidad) de la dimensión ambiental. La compleja geometría se resuelve en un espacio de baja dimensión (2D) donde existen soluciones de forma cerrada, mientras que el corte final permanece disperso en el espacio de alta dimensión original.
• Explotación de la No Convexidad: El marco expone y explota explícitamente los rangos conjuntos no convexos, que son inaccesibles para enfoques que dependen únicamente de la "convexidad oculta" (como la lema de S) o de las relajaciones convexas estándar.
• Generalización de MIR: El enfoque generaliza el exitoso paradigma de proyectar-luego-elevar de las desigualdades MIR al dominio no lineal de los QCQP, ofreciendo un mecanismo para generar cortes fuertes sin requerir restricciones de matrices densas.
• Direcciones Futuras: Los autores señalan modestamente que un estudio sistemático dentro de un resolvedor MINLP completo está más allá del alcance actual. Identifican la automatización de la selección de pares de desigualdades base efectivas como una dirección principal para la investigación futura, sugiriendo que se podrían adaptar heurísticas similares a las utilizadas para la separación de MIR para "alinear" los coeficientes cuadráticos de modo que induzcan la necesaria geometría no convexa.