A Compressive Sensing Inspired Monte-Carlo Method for Combinatorial Optimization

Resumen Técnico: Un Método de Monte Carlo Inspirado en el Procesamiento de Señales Comprimido para la Optimización Combinatoria

Planteamiento del Problema
El artículo aborda el desafío de resolver problemas de optimización combinatoria, específicamente aquellos definidos sobre un espacio binario discreto $\{0,1\}^N$. Los autores se centran en escenarios donde la función objetivo (costo o recompensa) es compleja, potencialmente no convexa, no diferenciable o una "Caja Negra" sin una forma analítica explícita. Estos problemas, que incluyen Hamiltonianos de Ising generalizados, el problema de la mochila y el problema del viajante, suelen sufrir una complejidad de tiempo exponencial cuando se abordan mediante búsqueda de fuerza bruta o búsqueda ingenua. Si bien las metaheurísticas como el recocido simulado (simulated annealing) y los algoritmos genéticos son estándares, los autores argumentan que los métodos eficientes para funciones de costo binarias generales siguen siendo limitados.

Metodología: Optimización de Monte Carlo Compresiva (MCCO)
La solución propuesta es el algoritmo de Optimización de Monte Carlo Compresiva (MCCO, por sus siglas en inglés). Este integra principios de procesamiento de señales comprimido (compressive sensing), aprendizaje compresivo estadístico y métodos de Monte Carlo para encontrar el óptimo global de una función basándose en una muestra de sus valores, incluso si el óptimo en sí mismo nunca es observado directamente durante el muestreo.

El algoritmo procede a través de los siguientes pasos:

1. Muestreo Aleatorio: Se genera una muestra $S_f$ de la función objetivo $f$ extrayendo $n$ índices de una distribución uniforme y evaluando $f$ en estos puntos.
2. Umbralización (Thresholding): Se aplica un operador de umbralización dura $T_t$ a la muestra, anulando los valores por debajo de un umbral específico $t$. Este paso es crucial para el rendimiento, ya que introduce una no linealidad que supera a los simples mapas lineales aleatorios.
3. Esquematización (Sketching/Measurement): Se aplica un mapa de esquematización $\Phi$ a la muestra umbralizada para producir un vector de esquema $y$. Este vector contiene estimaciones empíricas de los momentos generalizados de la distribución. El artículo utiliza tres tipos de funciones de esquema:
   • Interacciones de Cuadrupletos/Quíntupletos: Mapas deterministas estructurados basados en interacciones locales de cadenas de bits (por ejemplo, 4 o 5 bits consecutivos).
   • Esquema Aleatorio: Una matriz con coeficientes extraídos de una distribución Gaussiana.
4. Decodificación (Recuperación): Se aplica un procedimiento de decodificación codiciosa $\Delta$ (específicamente Orthogonal Matching Pursuit en los experimentos numéricos) a $y$ para reconstruir una estimación $\tilde{f}$. Los autores eligen explícitamente métodos codiciosos sobre la minimización $\ell_1$ (Basis Pursuit) para evitar el sobreajuste (overfitting) al ejemplo específico y, en su lugar, capturar las características globales de la distribución.
5. Optimización: Se toma el valor máximo de la función reconstruida $\tilde{f}$ como la estimación del óptimo global.

El método está diseñado para problemas "compresibles", definidos como aquellos donde la función de costo puede ser determinada o bien aproximada por un conjunto corto de reglas (una representación dispersa en una base conocida), incluso si dicha representación no es conocida explícitamente por el usuario.

Contribuciones Clave

• Novedad Algorítmica: La introducción de MCCO, que reaprovecha las técnicas de recuperación de procesamiento de señales comprimido para la optimización combinatoria, aprovechando específicamente algoritmos codiciosos para prevenir el sobreajuste en un entorno de Monte Carlo.
• Justificación Teórica: El artículo proporciona un análisis teórico (Teorema 1) que demuestra que la probabilidad de que el máximo verdadero sobreviva al proceso de muestreo y esquematización depende de la media y la varianza de la brecha entre el valor más grande y el segundo más grande de la función objetivo. Demuestra que, bajo un muestreo suficiente, el máximo puede preservarse con alta probabilidad.
• Implementación Práctica: El desarrollo de TrOMA (Tractable Optimization Modeling Approach), una biblioteca de Python de código abierto que implementa MCCO. Esta biblioteca es independiente del hardware (soporta backends clásicos y cuánticos, incluyendo computadoras cuánticas de IBM) y permite a los usuarios optimizar cualquier problema simplemente proporcionando una función de costo.
• Alcance Definido: Los autores definen una clase de problemas "compresibles" y argumentan que MCCO es particularmente efectivo para esta clase, que incluye muchos problemas NP-completos.

Resultados Numéricos
Los autores realizaron simulaciones numéricas en un problema de tamaño $N=12$ (un espacio de $2^{12}$), extraído aleatoriamente de la clase de problemas compresibles. Compararon MCCO contra Dual Annealing (una combinación de simulated annealing y fast annealing).

• Rendimiento: MCCO utilizando funciones de esquema estructuradas (Cuadrupletos y Quintupletos) superó a Dual Annealing.
  • Tasa de Éxito: MCCO con esquemas de Cuadrupletos recuperó el máximo global en aproximadamente el 58% de los casos, y Quintupletos en el 49%, frente al 46% de Dual Annealing.
  • Proximidad: Cuando no se encontraba el máximo global, las estimaciones de MCCO estaban significativamente más cerca del óptimo. Para los Cuadrupletos, el 91% de las estimaciones estaban dentro de una distancia de Hamming de 1 del óptimo real, comparado con el 81% de Dual Annealing.
  • Eficiencia de Muestreo: MCCO mostró un rendimiento competitivo o superior incluso con tamaños de muestra pequeños (50 a 400 muestras).
• Esquemas Aleatorios: El MCCO utilizando un esquema Gaussiano aleatorio funcionó peor que los esquemas estructurados y fue comparable a Dual Annealing en términos de recuperación del óptimo global (6%), aunque aun así superó a una suposición puramente aleatoria en términos de distancia de Hamming.

Significancia y Reivindicaciones
El artículo afirma que MCCO ofrece una alternativa competitiva a las metaheurísticas establecidas como Dual Annealing para una amplia clase de problemas combinatorios, particularmente aquellos que son "compresibles". La significancia radica en la capacidad del método para:

1. Manejar funciones objetivo de Caja Negra y complejas sin requerir información de gradiente.
2. Aprovechar la dispersión de la estructura subyacente del problema (incluso si es desconocida) para encontrar soluciones óptimas con menos evaluaciones de la función.
3. Ser ajustado a los recursos computacionales disponibles mediante el ajuste de parámetros heurísticos y funciones de esquema.
4. Proporcionar un puente entre la optimización clásica y la computación cuántica, ya que la decodificación de matrices estructuradas puede ser facilitada por algoritmos cuánticos.

Los autores mantienen la modestia respecto a los límites exactos de aplicabilidad del método, señalando que, si bien la clase de problemas compresibles es grande, los límites precisos de dónde MCCO supera a todos los demás métodos siguen siendo un área abierta para mayor investigación. Invitan a la comunidad a probar el método a través de la biblioteca TrOMA.