Optimización binaria cuadrática sin restricciones

La optimización binaria cuadrática sin restricciones ( QUBO ), también conocida como programación binaria cuadrática sin restricciones ( UBQP ), es un problema de optimización combinatoria con una amplia gama de aplicaciones, desde finanzas y economía hasta aprendizaje automático . ^{[ 1 ]} QUBO es un problema NP-difícil , y para muchos problemas clásicos de la informática teórica , como el corte máximo , la coloración de grafos y el problema de partición , se han formulado incrustaciones en QUBO. ^{[ 2 ] [ 3 ]} Las incrustaciones para modelos de aprendizaje automático incluyen máquinas de vectores de soporte , agrupamiento y modelos gráficos probabilísticos . ^{[ 4 ]} Además, debido a su estrecha conexión con los modelos de Ising , QUBO constituye una clase de problemas centrales para la computación cuántica adiabática , donde se resuelve mediante un proceso físico llamado recocido cuántico . ^{[ 5 ]}

Dejar${\displaystyle \mathbb {B} =\lbrace 0,1\rbrace }$el conjunto de dígitos binarios (o bits ), entonces${\displaystyle \mathbb {B} ^{n}}$es el conjunto de vectores binarios de longitud fija${\displaystyle n\in \mathbb {N} }$. Dada una matriz simétrica o triangular superior${\displaystyle {\boldsymbol {Q}}\in \mathbb {R} ^{n\times n}}$, cuyas entradas${\displaystyle Q_{ij}}$Defina un peso para cada par de índices.${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }$, podemos definir la función${\displaystyle f_{\boldsymbol {Q}}:\mathbb {B} ^{n}\rightarrow \mathbb {R} }$que asigna un valor a cada vector binario${\displaystyle {\boldsymbol {x}}}$a través de

${\displaystyle f_{\boldsymbol {Q}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}}=\sum _{i=1}^{n}\sum _{j=1}^{n}Q_{ij}x_{i}x_{j}.}$

Alternativamente, las partes lineal y cuadrática se pueden separar como

${\displaystyle f_{{\boldsymbol {Q}}',{\boldsymbol {q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Q}}'{\boldsymbol {x}}+{\boldsymbol {q}}^{\intercal }{\boldsymbol {x}},}$

dónde${\displaystyle {\boldsymbol {Q}}'\in \mathbb {R} ^{n\times n}}$y${\displaystyle {\boldsymbol {q}}\in \mathbb {R} ^{n}}$Esto es equivalente a la definición anterior a través de${\displaystyle {\boldsymbol {Q}}={\boldsymbol {Q}}'+\operatorname {diag} [{\boldsymbol {q}}]}$utilizando el operador diag , explotando eso${\displaystyle x=x\cdot x}$para todos los valores binarios${\displaystyle x}$.

Intuitivamente, el peso${\displaystyle Q_{ij}}$se agrega si ambos${\displaystyle x_{i}=1}$y${\displaystyle x_{j}=1}$El problema QUBO consiste en encontrar un vector binario${\displaystyle {\boldsymbol {x}}^{*}}$que minimiza${\displaystyle f_{\boldsymbol {Q}}}$, es decir,${\displaystyle \forall {\boldsymbol {x}}\in \mathbb {B} ^{n}:~f_{\boldsymbol {Q}}({\boldsymbol {x}}^{*})\leq f_{\boldsymbol {Q}}({\boldsymbol {x}})}$.

En general,${\displaystyle {\boldsymbol {x}}^{*}}$no es único, lo que significa que puede haber un conjunto de vectores minimizadores con igual valor con respecto a${\displaystyle f_{\boldsymbol {Q}}}$La complejidad de QUBO surge del número de vectores binarios candidatos que deben evaluarse, como${\displaystyle \left|\mathbb {B} ^{n}\right|=2^{n}}$crece exponencialmente en${\displaystyle n}$.

A veces, QUBO se define como el problema de maximizar${\displaystyle f_{\boldsymbol {Q}}}$, lo cual es equivalente a minimizar${\displaystyle f_{-{\boldsymbol {Q}}}=-f_{\boldsymbol {Q}}}$.

QUBO es invariante de escala para factores positivos.${\displaystyle \alpha >0}$, que dejan el óptimo${\displaystyle {\boldsymbol {x}}^{*}}$sin alterar:

${\displaystyle f_{\alpha {\boldsymbol {Q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }(\alpha {\boldsymbol {Q}}){\boldsymbol {x}}=\alpha ({\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}})=\alpha f_{\boldsymbol {Q}}({\boldsymbol {x}})}$.

En su forma general, QUBO es NP-difícil y no puede resolverse eficientemente mediante ningún algoritmo conocido de tiempo polinomial. ^{[ 6 ]} Sin embargo, existen casos especiales que se pueden resolver en tiempo polinomial, donde${\displaystyle {\boldsymbol {Q}}}$tiene ciertas propiedades, ^{[ 7 ]} por ejemplo:

• Si todos los coeficientes son positivos, el óptimo es trivial.${\displaystyle {\boldsymbol {x}}^{*}=(0,\dots ,0)^{\intercal }}$. De manera similar, si todos los coeficientes son negativos, el óptimo es${\displaystyle {\boldsymbol {x}}^{*}=(1,\dots ,1)^{\intercal }}$.
• Si${\displaystyle {\boldsymbol {Q}}}$es diagonal , los bits se pueden optimizar de forma independiente y el problema es resoluble en${\displaystyle {\mathcal {O}}(n)}$. Las asignaciones de variables óptimas son simplemente${\displaystyle x_{i}^{*}=1}$si${\displaystyle Q_{ii}<0}$, y${\displaystyle x_{i}^{*}=0}$de lo contrario.
• Si todos los elementos fuera de la diagonal de${\displaystyle {\boldsymbol {Q}}}$son no positivos, el problema QUBO correspondiente es resoluble en tiempo polinomial. ^{[ 8 ]}

QUBO se puede resolver utilizando solucionadores de programación lineal entera como CPLEX o Gurobi Optimizer . Esto es posible ya que QUBO se puede reformular como un problema de optimización binaria con restricciones lineales. Para lograr esto, sustituya el producto${\displaystyle x_{i}x_{j}}$mediante una variable binaria adicional${\displaystyle z_{ij}\in \mathbb {B} }$y agregar las restricciones${\displaystyle x_{i}\geq z_{ij}}$,${\displaystyle x_{j}\geq z_{ij}}$y${\displaystyle x_{i}+x_{j}-1\leq z_{ij}}$. Tenga en cuenta que${\displaystyle z_{ij}}$También se puede relajar a variables continuas dentro de los límites cero y uno.

QUBO es un problema de optimización estructuralmente simple, pero computacionalmente difícil. Puede utilizarse para codificar una amplia gama de problemas de optimización de diversas áreas científicas. ^{[ 9 ]}

Análisis de clúster

Agrupamiento binario con QUBO

Una mala asignación de clúster.

Una buena asignación de clúster.

Representación visual de un problema de agrupamiento con 20 puntos: Los círculos del mismo color pertenecen al mismo grupo. Cada círculo puede interpretarse como una variable binaria en el problema QUBO correspondiente.

A continuación, consideramos el problema del análisis de clústeres , donde se nos da un conjunto de${\displaystyle N}$puntos en${\displaystyle d}$espacio -dimensional y queremos asignar cada punto a una de dos clases o clústeres , de manera que los puntos en el mismo clúster sean similares entre sí. Para este ejemplo establecemos${\displaystyle N=20}$y${\displaystyle d=2}$Los datos se proporcionan como una matriz.${\displaystyle {\boldsymbol {X}}\in \mathbb {R} ^{20\times 2}}$donde cada fila contiene dos coordenadas cartesianas . Para dos grupos, podemos asignar una variable binaria.${\displaystyle x_{i}\in \mathbb {B} }$hasta el punto correspondiente a la${\displaystyle i}$-ésima fila en${\displaystyle {\boldsymbol {X}}}$, indicando si pertenece al primero (${\displaystyle x_{i}=0}$) o segundo grupo (${\displaystyle x_{i}=1}$). En consecuencia, tenemos 20 variables binarias, que forman un vector binario.${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{20}}$que corresponde a una asignación de clúster de todos los puntos (véase la figura).

Una forma de derivar una agrupación es considerar las distancias por pares entre puntos. Dada una asignación de clúster${\displaystyle {\boldsymbol {x}}}$, la expresión${\displaystyle x_{i}x_{j}+(1-x_{i})(1-x_{j})}$se evalúa a 1 si puntos${\displaystyle i}$y${\displaystyle j}$están en el mismo grupo. De manera similar,${\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}=1}$indica que están en grupos diferentes.${\displaystyle d_{ij}>0}$denota la distancia euclidiana entre los puntos${\displaystyle i}$y${\displaystyle j}$, es decir,

${\displaystyle d_{ij}={\sqrt {{\boldsymbol {X}}_{i}^{\intercal }{\boldsymbol {X}}_{j}}}}$,

dónde${\displaystyle {\boldsymbol {X}}_{i}}$es el${\displaystyle i}$-fila de${\displaystyle {\boldsymbol {X}}}$.

Para definir una función de costo a minimizar, cuando los puntos${\displaystyle i}$y${\displaystyle j}$están en el mismo grupo sumamos su distancia positiva${\displaystyle d_{ij}}$y restarlo cuando se encuentran en grupos diferentes. De esta manera, una solución óptima tiende a colocar los puntos que están muy separados en grupos diferentes, y los puntos que están cerca en el mismo grupo.

Dejar${\displaystyle {\boldsymbol {D}}\in \mathbb {R} ^{N\times N}}$con${\displaystyle D_{ij}=d_{ij}/2}$a pesar de${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }$. Dada una tarea${\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{N}}$, dicha función de coste viene dada por

${\displaystyle {\begin{aligned}f({\boldsymbol {x}})&={\boldsymbol {x}}^{\intercal }{\boldsymbol {Dx}}-{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})-({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Dx}}+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}},\end{aligned}}}$

dónde${\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{N}}$.

De la segunda línea podemos ver que esta expresión se puede reordenar a un problema QUBO definiendo

${\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {D}}-4\operatorname {diag} [{\boldsymbol {D1}}]}$

e ignorando el término constante${\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}}}$. Utilizando estos parámetros, un vector binario que minimiza esta instancia de QUBO${\displaystyle {\boldsymbol {Q}}}$corresponderá a una asignación de clúster óptima con respecto a la función de costo anterior.

QUBO está muy relacionado y es computacionalmente equivalente al modelo de Ising , cuya función hamiltoniana se define como

${\displaystyle H({\boldsymbol {\sigma }})={\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}=\sum _{i,j}J_{ij}\sigma _{i}\sigma _{j}+\sum _{j}h_{j}\sigma _{j}}$

con parámetros de valor real${\displaystyle h_{j},J_{ij}}$a pesar de${\displaystyle i,j}$Las variables de espín${\displaystyle \sigma _{j}}$son binarios con valores de${\displaystyle \lbrace -1,+1\rbrace }$en lugar de${\displaystyle \mathbb {B} }$. Nótese que esta formulación está simplificada, ya que, en un contexto físico,${\displaystyle \sigma _{i}}$son típicamente operadores de Pauli , que son matrices de valores complejos de tamaño${\displaystyle 2^{n}\times 2^{n}}$, mientras que aquí las tratamos como variables binarias. Muchas formulaciones del hamiltoniano del modelo de Ising asumen además que las variables están dispuestas en una red, donde solo pares de variables vecinas${\displaystyle \langle i~j\rangle }$pueden tener coeficientes distintos de cero; aquí, simplemente asumimos que${\displaystyle J_{ij}=0}$si${\displaystyle i}$y${\displaystyle j}$no son vecinos.

Aplicando la identidad${\displaystyle \sigma =1-2x}$produce un problema QUBO equivalente ^{[ 10 ]}

${\displaystyle {\begin{aligned}&{\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}\\&=({\boldsymbol {1}}-2{\boldsymbol {x}})^{\intercal }{\boldsymbol {J}}({\boldsymbol {1}}-2{\boldsymbol {x}})+{\boldsymbol {h}}^{\intercal }({\boldsymbol {1}}-2{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {J}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {Jx}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}-2{\boldsymbol {h}}^{\intercal }{\boldsymbol {x}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}\\&={\boldsymbol {x}}^{\intercal }(4{\boldsymbol {J}}){\boldsymbol {x}}-(4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}})^{\intercal }{\boldsymbol {x}}+\underbrace {{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}} _{\text{const.}},\end{aligned}}}$

cuya matriz de pesos${\displaystyle {\boldsymbol {Q}}}$es dado por

${\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {J}}-\operatorname {diag} [4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}}],}$

Ignorando nuevamente el término constante, que no afecta la minimización. Usando la identidad${\displaystyle x=(1-\sigma )/2}$, un problema QUBO con matriz${\displaystyle {\boldsymbol {Q}}}$se puede convertir a un modelo de Ising equivalente utilizando la misma técnica, obteniendo

${\displaystyle {\begin{aligned}{\boldsymbol {J}}&={\boldsymbol {Q}}/4,&{\boldsymbol {h}}&=-({\boldsymbol {Q1}}+{\boldsymbol {Q}}^{\intercal }{\boldsymbol {1}})/4,\end{aligned}}}$

y un desplazamiento constante de${\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {Q1}}/4}$. ^{[ 10 ]}

• QUBO Benchmark (Prueba comparativa de paquetes de software para la solución exacta de QUBO; forma parte de la conocida colección de pruebas comparativas de Mittelmann)
• Endre Boros, Peter L Hammer y Gabriel Tavares (abril de 2007). "Heurísticas de búsqueda local para la optimización binaria cuadrática sin restricciones (QUBO)" . Journal of Heuristics . 13 (2). Association for Computing Machinery: 99–132 . doi : 10.1007/s10732-007-9009-3 . S2CID 32887708. Recuperado el 12 de mayo de 2013 . 
• Di Wang y Robert Kleinberg (noviembre de 2009). "Análisis de problemas de optimización binaria cuadrática sin restricciones mediante flujos multicommodity" . Discrete Applied Mathematics . 157 (18). Elsevier: 3746–3753 . doi : 10.1016/j.dam.2009.07.009 . PMC 2808708. PMID 20161596 .  
• Universidad de Hiroshima y NTT DATA Group Corporation  : "QUBO++ con solucionador QUBO GPU ABS2" # Software.