L'optimització binària quadràtica sense restriccions (QUBO), també coneguda com a programació quadràtica binària sense restriccions (UBQP), és un problema d'optimització combinatòria amb una àmplia gamma d'aplicacions, des de les finances i l'economia fins a l'aprenentatge automàtic. QUBO és un problema NP difícil, i per a molts problemes clàssics de la informàtica teòrica, com el tall màxim, la coloració de grafs i el problema de partició, s'han formulat incrustacions a QUBO. Les incrustacions per a models d'aprenentatge automàtic inclouen màquines de vectors de suport, agrupament i models gràfics probabilístics. A més, a causa de la seva estreta connexió amb els models d'Ising, QUBO constitueix una classe de problemes central per a la computació quàntica adiabàtica, on es resol mitjançant un procés físic anomenat recuit quàntic.
Definició Deixa el conjunt de dígits binaris (o bits), aleshores és el conjunt de vectors binaris de longitud fixa Donada una matriu simètrica o triangular superior , les entrades del qual definir un pes per a cada parell d'índexs , podem definir la funció que assigna un valor a cada vector binari a través
Alternativament, les parts lineal i quadràtica es poden separar com
on i Això és equivalent a la definició anterior a través de utilitzant l'operador diag, explotant això per a tots els valors binaris .
Intuïtivament, el pes s'afegeix si tots dos i El problema QUBO consisteix a trobar un vector binari que minimitza , és a dir, .
En general, no és únic, és a dir, que hi pot haver un conjunt de vectors minimitzants amb el mateix valor respecte a La complexitat de QUBO sorgeix del nombre de vectors binaris candidats a avaluar, ja que creix exponencialment en .
De vegades, QUBO es defineix com el problema de maximitzar , que és equivalent a minimitzar
Propietats QUBO és invariant a l'escala per a factors positius , que deixen l'òptim sense canvis:
En la seva forma general, QUBO és NP-difícil i no es pot resoldre eficientment amb cap algorisme de temps polinòmic. Tanmateix, hi ha casos especials amb resolució polinòmica, on té certes propietats, per exemple:
Si tots els coeficients són positius, l'òptim és trivialment De la mateixa manera, si tots els coeficients són negatius, l'òptim és . Si és diagonal, els bits es poden optimitzar independentment i el problema es pot resoldre en Les assignacions òptimes de variables són simplement si , i altrament. Si tots els elements fora de la diagonal de són no positius, el problema QUBO corresponent es pot resoldre en temps polinòmic.See Theorem 3.16 in Punnen (2022); note that the authors assume the maximization version of QUBO.
QUBO es pot resoldre utilitzant solucionadors de programació lineal entera com CPLEX o Gurobi Optimizer. Això és possible ja que QUBO es pot reformular com un problema d'optimització binària amb restriccions lineals. Per aconseguir-ho, substituïu el producte per una variable binària addicional i afegiu les restriccions , i Tingueu en compte que també es pot relaxar a variables contínues dins dels límits zero i u.
Aplicacions QUBO és un problema d'optimització estructuralment simple, però computacionalment difícil. Es pot utilitzar per codificar una àmplia gamma de problemes d'optimització de diverses àrees científiques.
Tall màxim Donat un gràfic amb conjunt de vèrtexs i vores , el problema del tall màxim (max-cut) consisteix a trobar dos subconjunts amb , de manera que el nombre d'arestes entre i està maximitzat.
El problema de tall màxim ponderat més general assumeix pesos de vora , amb , i demana una partició que maximitza la suma dels pesos de les arestes entre i , és a dir,
En configurar per a tots això esdevé equivalent al problema original de màxim tall anterior, i és per això que ens centrem en aquesta forma més general a continuació.
Per a cada vèrtex de introduïm una variable binària amb la interpretació si i si Com , cada està exactament en un conjunt, és a dir, hi ha una correspondència 1:1 entre vectors binaris i particions de en dos subconjunts.
Observem que, per a qualsevol , l'expressió s'avalua a 1 si i només si i es troben en subconjunts diferents, equivalents a l'operació XOR lògica. Sigui amb . Si estenem l'expressió anterior a la forma matriu-vector, trobem que
és la suma dels pesos de totes les arestes entre i , on . Com que es tracta d'una funció quadràtica sobre , és un problema QUBO la matriu de paràmetres del qual podem llegir de l'expressió anterior com
després de invertir el signe per convertir-lo en un problema de minimització.
Anàlisi de clústers A continuació, considerem el problema de l'anàlisi de clústers, on se'ns dóna un conjunt de punts en espai de dimensió i volem assignar cada punt a una de dues classes o clústers, de manera que els punts del mateix clúster siguin similars entre si. Per a aquest exemple, establim i Les dades es donen com una matriu , on cada fila conté dues coordenades cartesianes. Per a dos clústers, podem assignar una variable binària fins al punt corresponent a la -èsima fila de , indicant si pertany al primer ( ) o segon clúster ( ). En conseqüència, tenim 20 variables binàries, que formen un vector binari que correspon a una assignació de clúster de tots els punts (vegeu la figura).
Una manera de derivar un agrupament és considerar les distàncies per parells entre punts. Donada una assignació de clúster , l'expressió s'avalua a 1 si punts i es troben al mateix clúster. De la mateixa manera, indica que es troben en clústers diferents. Sigui denota la distància euclidiana entre els punts i , és a dir,
on és el -èsima fila de .
Per tal de definir una funció de cost per minimitzar, quan els punts i estan al mateix clúster, sumem la seva distància positiva , i restar-ho quan es troben en clústers diferents. D'aquesta manera, una solució òptima tendeix a col·locar els punts que estan allunyats en clústers diferents i els punts que estan a prop en el mateix clúster.
Sigui amb per a tots . Se li ha assignat una tasca , aquesta funció de cost ve donada per
on .
A la segona línia podem veure que aquesta expressió es pot reorganitzar a un problema QUBO definint
i ignorant el terme constant . Utilitzant aquests paràmetres, un vector binari que minimitza aquesta instància de QUBO correspondrà a una assignació de clúster òptima respecte a la funció de cost.
Connexió amb models d'Ising QUBO està molt estretament relacionat i computacionalment equivalent al model d'Ising, la funció hamiltoniana del qual es defineix com
amb paràmetres amb valors reals per a tots Les variables d'espín són binaris amb valors de en lloc de . Cal tenir en compte que aquesta formulació està simplificada, ja que, en un context de física, són típicament operadors de Pauli, que són matrius de valors complexos de mida , mentre que aquí les tractem com a variables binàries. Moltes formulacions del model hamiltonià d'Ising assumeixen a més que les variables estan disposades en una xarxa, on només parells de variables veïnes pot tenir coeficients diferents de zero; aquí, simplement suposem que si i no són veïns.
Aplicant la identitat dóna un problema QUBO equivalent
la matriu de pesos de la qual ve donat per
ignorant de nou el terme constant, que no afecta la minització. Utilitzant la identitat , un problema QUBO amb matriu es pot convertir a un model d'Ising equivalent utilitzant la mateixa tècnica, donant com a resultat
i un desplaçament constant de
Referències
Categoria:Algorismes Categoria:Aprenentatge automàtic