Квадратичная безусловная бинарная оптимизация
Комбинаторная задача оптимизации

Квадратичная безусловная бинарная оптимизация ( QUBO ), также известная как безусловная бинарная квадратичная оптимизация ( UBQP ), представляет собой комбинаторную задачу оптимизации с широким спектром приложений от финансов и экономики до машинного обучения . [1] QUBO является NP-сложной задачей, и для многих классических задач из теоретической информатики , таких как максимальный разрез , раскраска графа и проблема разбиения , были сформулированы вложения в QUBO. [2] [3] Вложения для моделей машинного обучения включают опорные векторные машины , кластеризацию и вероятностные графические модели . [4] Более того, из-за своей тесной связи с моделями Изинга , QUBO представляет собой центральный класс задач для адиабатических квантовых вычислений , где она решается с помощью физического процесса, называемого квантовым отжигом . [5]

Определение

Набор двоичных векторов фиксированной длины обозначается как , где — набор двоичных значений (или битов ). Нам дана вещественная верхняя треугольная матрица , элементы которой определяют вес для каждой пары индексов внутри двоичного вектора. Мы можем определить функцию , которая присваивает значение каждому двоичному вектору через н > 0 {\displaystyle n>0} Б н {\displaystyle \mathbb {B} ^{n}} Б = { 0 , 1 } {\displaystyle \mathbb {B} =\lbrace 0,1\rbrace} В ∈ Р н × н {\displaystyle Q\in \mathbb {R} ^{n\times n}} В я дж {\displaystyle Q_{ij}} я , дж ∈ { 1 , … , н } {\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace } ф В : Б н → Р {\displaystyle f_{Q}:\mathbb {B} ^{n}\rightarrow \mathbb {R} }

ф В ( х ) = х ⊤ В х = ∑ я = 1 н ∑ дж = я н В я дж х я х дж {\displaystyle f_{Q}(x)=x^{\top }Qx=\sum _{i=1}^{n}\sum _{j=i}^{n}Q_{ij}x_{i}x_{j}}

Интуитивно понятно, что вес добавляется, если оба и имеют значение 1. Когда , значения добавляются, если , как и для всех . В я дж {\displaystyle Q_{ij}} х я {\displaystyle x_{i}} х дж {\displaystyle x_{j}} я = дж {\displaystyle i=j} В я я {\displaystyle Q_{ii}} х я = 1 {\displaystyle x_{i}=1} х я х я = х я {\displaystyle x_{i}x_{i}=x_{i}} х я ∈ Б {\displaystyle x_{i}\in \mathbb {B} }

Задача QUBO состоит в нахождении двоичного вектора , минимального относительно , ​​а именно х ∗ {\displaystyle x^{*}} ф В {\displaystyle f_{Q}}

∀ х ∈ Б н :   ф В ( х ∗ ) ≤ ф В ( х ) {\displaystyle \forall x\in \mathbb {B} ^{n}:~f_{Q}(x^{*})\leq f_{Q}(x)}

В общем случае не является уникальным, то есть может существовать набор минимизирующих векторов с одинаковым значением wrt . Сложность QUBO возникает из числа кандидатов на двоичные векторы для оценки, поскольку растет экспоненциально в . х ∗ {\displaystyle x^{*}} ф В {\displaystyle f_{Q}} | Б н | = 2 н {\displaystyle |\mathbb {B} ^{n}|=2^{n}} н {\displaystyle n}

Иногда QUBO определяют как задачу максимизации , что эквивалентно минимизации . ф В {\displaystyle f_{Q}} ф − В = − ф В {\displaystyle f_{-Q}=-f_{Q}}

Характеристики

QUBO масштабно инвариантен для положительных факторов , которые оставляют оптимум неизменным: α > 0 {\displaystyle \альфа >0} х ∗ {\displaystyle x^{*}}

ф α В ( х ) = ∑ я ≤ дж ( α В я дж ) х я х дж = α ∑ я ≤ дж В я дж х я х дж = α ф В ( х ) {\displaystyle f_{\alpha Q}(x)=\sum _{i\leq j}(\alpha Q_{ij})x_{i}x_{j} =\alpha \sum _{i\leq j} Q_{ij}x_{i}x_{j}=\alpha f_{Q}(x)}

В своей общей форме QUBO является NP-трудной задачей и не может быть эффективно решена никаким полиномиальным алгоритмом. [6] Однако существуют полиномиально решаемые особые случаи, где имеет определенные свойства, [7] например: В {\displaystyle Q}

  • Если все коэффициенты положительны, оптимум тривиально равен . Аналогично, если все коэффициенты отрицательны, оптимум равен . х ∗ = ( 0 , … , 0 ) {\displaystyle x^{*}=(0,\точки,0)} х ∗ = ( 1 , … , 1 ) {\displaystyle x^{*}=(1,\точки,1)}
  • Если диагональна , биты можно оптимизировать независимо, и задача разрешима за . Оптимальные назначения переменных — это просто, если , и в противном случае. В {\displaystyle Q} О ( н ) {\displaystyle {\mathcal {O}}(n)} х я ∗ = 1 {\displaystyle x_{i}^{*}=1} В я я < 0 {\displaystyle Q_{ii}<0} х я ∗ = 0 {\displaystyle x_{i}^{*}=0}
  • Если все недиагональные элементы неположительны, соответствующая задача QUBO разрешима за полиномиальное время. [8] В {\displaystyle Q}

QUBO можно решить с помощью решателей целочисленного линейного программирования, таких как CPLEX или Gurobi Optimizer . Это возможно, поскольку QUBO можно переформулировать как линейную ограниченную бинарную задачу оптимизации. Чтобы добиться этого, замените произведение дополнительной двоичной переменной и добавьте ограничения , и . Обратите внимание, что также можно ослабить до непрерывных переменных в пределах от нуля до единицы. х я х дж {\displaystyle x_{i}x_{j}} з я дж ∈ { 0 , 1 } {\displaystyle z_{ij}\in \{0,1\}} х я ≥ з я дж {\displaystyle x_{i}\geq z_{ij}} х дж ≥ з я дж {\displaystyle x_{j}\geq z_{ij}} х я + х дж − 1 ≤ з я дж {\displaystyle x_{i}+x_{j}-1\leq z_{ij}} з я дж {\displaystyle z_{ij}}

Приложения

QUBO — это структурно простая, но вычислительно сложная задача оптимизации. Она может быть использована для кодирования широкого спектра задач оптимизации из различных научных областей. [9]

Кластерный анализ

Двоичная кластеризация с QUBO
Визуальное представление задачи кластеризации с 20 точками: Круги одного цвета принадлежат одному кластеру. Каждый круг можно понимать как бинарную переменную в соответствующей задаче QUBO.

В качестве наглядного примера того, как QUBO может быть использован для кодирования задачи оптимизации, рассмотрим задачу кластерного анализа . Здесь нам дан набор из 20 точек в 2D-пространстве, описанный матрицей , где каждая строка содержит две декартовы координаты . Мы хотим назначить каждую точку одному из двух классов или кластеров , так чтобы точки в одном кластере были похожи друг на друга. Для двух кластеров мы можем назначить бинарную переменную точке, соответствующей -й строке в , указав, принадлежит ли она первому ( ) или второму кластеру ( ). Следовательно, у нас есть 20 бинарных переменных, которые образуют бинарный вектор , который соответствует кластерному назначению всех точек (см. рисунок). Д ∈ Р 20 × 2 {\displaystyle D\in \mathbb {R} ^{20\times 2}} х я ∈ Б {\displaystyle x_{i}\in \mathbb {B} } я {\displaystyle я} Д {\displaystyle D} х я = 0 {\displaystyle x_{i}=0} х я = 1 {\displaystyle x_{i}=1} х ∈ Б 20 {\displaystyle x\in \mathbb {B} ^{20}}

Один из способов вывести кластеризацию — рассмотреть парные расстояния между точками. При задании кластера один из или оценивается в 1, если точки и находятся в одном кластере. Аналогично, один из или указывает, что они находятся в разных кластерах. Пусть обозначает евклидово расстояние между точками и . Чтобы определить функцию стоимости для минимизации, когда точки и находятся в одном кластере, мы добавляем их положительное расстояние и вычитаем его, когда они находятся в разных кластерах. Таким образом, оптимальное решение имеет тенденцию размещать точки, которые находятся далеко друг от друга, в разных кластерах, а точки, которые находятся близко, в одном кластере. Таким образом, функция стоимости сводится к х {\displaystyle x} х я х дж {\displaystyle x_{i}x_{j}} ( 1 − х я ) ( 1 − х дж ) {\displaystyle (1-x_{i})(1-x_{j})} i {\displaystyle i} j {\displaystyle j} x i ( 1 − x j ) {\displaystyle x_{i}(1-x_{j})} ( 1 − x i ) x j {\displaystyle (1-x_{i})x_{j}} d i j ≥ 0 {\displaystyle d_{ij}\geq 0} i {\displaystyle i} j {\displaystyle j} i {\displaystyle i} j {\displaystyle j} d i j {\displaystyle d_{ij}}

f ( x ) = ∑ i < j d i j ( x i x j + ( 1 − x i ) ( 1 − x j ) ) − d i j ( x i ( 1 − x j ) + ( 1 − x i ) x j ) = ∑ i < j [ 4 d i j x i x j − 2 d i j x i − 2 d i j x j + d i j ] {\displaystyle {\begin{aligned}f(x)&=\sum _{i<j}d_{ij}(x_{i}x_{j}+(1-x_{i})(1-x_{j}))-d_{ij}(x_{i}(1-x_{j})+(1-x_{i})x_{j})\\&=\sum _{i<j}\left[4d_{ij}x_{i}x_{j}-2d_{ij}x_{i}-2d_{ij}x_{j}+d_{ij}\right]\end{aligned}}}

Из второй строки параметры QUBO можно легко найти, переставив их следующим образом:

Q i j = { d i j if  i ≠ j − ( ∑ k = 1 i − 1 d k i + ∑ ℓ = i + 1 n d i ℓ ) if  i = j {\displaystyle {\begin{aligned}Q_{ij}&={\begin{cases}d_{ij}&{\text{if }}i\neq j\\-\left(\sum \limits _{k=1}^{i-1}d_{ki}+\sum \limits _{\ell =i+1}^{n}d_{i\ell }\right)&{\text{if }}i=j\end{cases}}\end{aligned}}}

При использовании этих параметров оптимальное решение QUBO будет соответствовать оптимальному кластеру относительно приведенной выше функции затрат.

Связь с моделями Изинга

QUBO очень тесно связана и вычислительно эквивалентна модели Изинга , функция Гамильтона которой определяется как

H ( σ ) = − ∑ ⟨ i   j ⟩ J i j σ i σ j − μ ∑ j h j σ j {\displaystyle H(\sigma )=-\sum _{\langle i~j\rangle }J_{ij}\sigma _{i}\sigma _{j}-\mu \sum _{j}h_{j}\sigma _{j}}

с действительными параметрами для всех . Спиновые переменные являются бинарными со значениями из вместо . Более того, в модели Изинга переменные обычно располагаются в решетке, где только соседние пары переменных могут иметь ненулевые коэффициенты. Применение тождества дает эквивалентную задачу QUBO: [2] h j , J i j , μ {\displaystyle h_{j},J_{ij},\mu } i , j {\displaystyle i,j} σ j {\displaystyle \sigma _{j}} { − 1 , + 1 } {\displaystyle \lbrace -1,+1\rbrace } B {\displaystyle \mathbb {B} } ⟨ i   j ⟩ {\displaystyle \langle i~j\rangle } σ ↦ 2 x − 1 {\displaystyle \sigma \mapsto 2x-1}

f ( x ) = ∑ ⟨ i   j ⟩ − J i j ( 2 x i − 1 ) ( 2 x j − 1 ) + ∑ j μ h j ( 2 x j − 1 ) = ∑ ⟨ i   j ⟩ ( − 4 J i j x i x j + 2 J i j x i + 2 J i j x j − J i j ) + ∑ j ( 2 μ h j x j − μ h j ) using  x j = x j x j = ∑ ⟨ i   j ⟩ ( − 4 J i j x i x j ) + ∑ ⟨ i   j ⟩ 2 J i j x i + ∑ ⟨ i   j ⟩ 2 J i j x j + ∑ j 2 μ h j x j − ∑ ⟨ i   j ⟩ J i j − ∑ j μ h j = ∑ ⟨ i   j ⟩ ( − 4 J i j x i x j ) + ∑ ⟨ j   i ⟩ 2 J j i x j + ∑ ⟨ i   j ⟩ 2 J i j x j + ∑ j 2 μ h j x j − ∑ ⟨ i   j ⟩ J i j − ∑ j μ h j using  ∑ ⟨ i   j ⟩ = ∑ ⟨ j   i ⟩ = ∑ ⟨ i   j ⟩ ( − 4 J i j x i x j ) + ∑ j ∑ ⟨ k = j   i ⟩ 2 J k i x j + ∑ j ∑ ⟨ i   k = j ⟩ 2 J i k x j + ∑ j 2 μ h j x j − ∑ ⟨ i   j ⟩ J i j − ∑ j μ h j = ∑ ⟨ i   j ⟩ ( − 4 J i j x i x j ) + ∑ j ( ∑ ⟨ i   k = j ⟩ ( 2 J k i + 2 J i k ) + 2 μ h j ) x j − ∑ ⟨ i   j ⟩ J i j − ∑ j μ h j using  ∑ ⟨ k = j   i ⟩ = ∑ ⟨ i   k = j ⟩ = ∑ i = 1 n ∑ j = 1 i Q i j x i x j + C {\displaystyle {\begin{aligned}f(x)&=\sum _{\langle i~j\rangle }-J_{ij}(2x_{i}-1)(2x_{j}-1)+\sum _{j}\mu h_{j}(2x_{j}-1)\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j}+2J_{ij}x_{i}+2J_{ij}x_{j}-J_{ij})+\sum _{j}(2\mu h_{j}x_{j}-\mu h_{j})&&{\text{using }}x_{j}=x_{j}x_{j}\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{\langle i~j\rangle }2J_{ij}x_{i}+\sum _{\langle i~j\rangle }2J_{ij}x_{j}+\sum _{j}2\mu h_{j}x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{\langle j~i\rangle }2J_{ji}x_{j}+\sum _{\langle i~j\rangle }2J_{ij}x_{j}+\sum _{j}2\mu h_{j}x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}&&{\text{using }}\sum _{\langle i~j\rangle }=\sum _{\langle j~i\rangle }\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{j}\sum _{\langle k=j~i\rangle }2J_{ki}x_{j}+\sum _{j}\sum _{\langle i~k=j\rangle }2J_{ik}x_{j}+\sum _{j}2\mu h_{j}x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{j}\left(\sum _{\langle i~k=j\rangle }(2J_{ki}+2J_{ik})+2\mu h_{j}\right)x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}&&{\text{using }}\sum _{\langle k=j~i\rangle }=\sum _{\langle i~k=j\rangle }\\&=\sum _{i=1}^{n}\sum _{j=1}^{i}Q_{ij}x_{i}x_{j}+C\end{aligned}}}

где

Q i j = { − 4 J i j if  i ≠ j ∑ ⟨ i   k = j ⟩ ( 2 J k i + 2 J i k ) + 2 μ h j if  i = j C = − ∑ ⟨ i   j ⟩ J i j − ∑ j μ h j {\displaystyle {\begin{aligned}Q_{ij}&={\begin{cases}-4J_{ij}&{\text{if }}i\neq j\\\sum _{\langle i~k=j\rangle }(2J_{ki}+2J_{ik})+2\mu h_{j}&{\text{if }}i=j\end{cases}}\\C&=-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}\end{aligned}}}

и используя тот факт, что для двоичной переменной . x j = x j x j {\displaystyle x_{j}=x_{j}x_{j}}

Поскольку константа не изменяет положение оптимума , ею можно пренебречь во время оптимизации, она важна только для восстановления исходного значения функции Гамильтона. C {\displaystyle C} x ∗ {\displaystyle x^{*}}

Ссылки

  1. ^ Кохенбергер, Гэри; Хао, Цзинь-Као; Гловер, Фред; Льюис, Марк; Лу, Чжипэн; Ван, Хайбо; Ван, Ян (2014). «Неограниченная бинарная задача квадратичного программирования: обзор» (PDF) . Журнал комбинаторной оптимизации . 28 : 58–81. doi :10.1007/s10878-014-9734-0. S2CID  16808394.
  2. ^ ab Гловер, Фред; Кохенбергер, Гэри (2019). «Учебное пособие по формулированию и использованию моделей QUBO». arXiv : 1811.11538 [cs.DS].
  3. ^ Лукас, Эндрю (2014). «Изинговские формулировки многих NP-задач». Frontiers in Physics . 2 : 5. arXiv : 1302.5843 . Bibcode : 2014FrP.....2....5L. doi : 10.3389/fphy.2014.00005 .
  4. ^ Мюкке, Саша; Пятковски, Нико; Морик, Катарина (2019). «Изучаем понемногу: извлекаем суть машинного обучения» (PDF) . LWDA . S2CID  202760166. Архивировано из оригинала (PDF) 27.02.2020.
  5. ↑ Том Саймонайт (8 мая 2013 г.). «Квантовый компьютер D-Wave выходит на скачки и побеждает». MIT Technology Review. Архивировано из оригинала 24 сентября 2015 г. Получено 12 мая 2013 г.
  6. ^ AP Punnen (редактор), Квадратичная задача безусловной бинарной оптимизации: теория, алгоритмы и приложения, Springer, Springer, 2022.
  7. ^ Çela, E., Punnen, AP (2022). Сложность и полиномиально разрешимые особые случаи QUBO. В: Punnen, AP (ред.) Задача квадратичной неограниченной бинарной оптимизации. Springer, Cham. https://doi.org/10.1007/978-3-031-04520-2_3
  8. ^ См. теорему 3.16 в Punnen (2022); обратите внимание, что авторы предполагают максимизирующую версию QUBO.
  9. ^ Ратке, Дэниел (2021-06-10). "Список формулировок QUBO" . Получено 2022-12-16 .
  • QUBO Benchmark (тест производительности программных пакетов для точного решения QUBO; часть известной коллекции тестов Mittelmann)
  • Эндре Борос, Питер Л. Хаммер и Габриэль Таварес (апрель 2007 г.). "Локальная эвристика поиска для квадратичной неограниченной двоичной оптимизации (QUBO)". Журнал эвристики . 13 (2). Ассоциация вычислительной техники: 99–132. doi :10.1007/s10732-007-9009-3. S2CID  32887708. Получено 12 мая 2013 г.
  • Ди Ванг и Роберт Клейнберг (ноябрь 2009 г.). «Анализ квадратичных задач бинарной оптимизации без ограничений с помощью многопродуктовых потоков». Дискретная прикладная математика . 157 (18). Elsevier: 3746–3753. doi :10.1016/j.dam.2009.07.009. PMC  2808708. PMID  20161596 .


Значок заглушки

Эта статья, связанная с искусственным интеллектом , является заглушкой . Вы можете помочь Википедии, расширив ее.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Quadratic_unconstrained_binary_optimization&oldid=1253304840"