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

Комбинаторная задача оптимизации

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

Определение

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

${\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}}$ ${\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}}$ ${\displaystyle |\mathbb {B} ^{n}|=2^{n}}$ ${\displaystyle n}$

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

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

QUBO масштабно инвариантен для положительных факторов , которые оставляют оптимум неизменным: ${\displaystyle \alpha >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}$

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

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

Приложения

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

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

Двоичная кластеризация с QUBO

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

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

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

${\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 можно легко найти, переставив их следующим образом:

${\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 очень тесно связана и вычислительно эквивалентна модели Изинга , функция Гамильтона которой определяется как

${\displaystyle H(\sigma )=-\sum _{\langle i~j\rangle }J_{ij}\sigma _{i}\sigma _{j}-\mu \sum _{j}h_{j}\sigma _{j}}$

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

${\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}}}$

где

${\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}}}$

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

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

Ссылки

1. Кохенбергер, Гэри; Хао, Цзинь-Као; Гловер, Фред; Льюис, Марк; Лу, Чжипэн; Ван, Хайбо; Ван, Ян (2014). «Неограниченная бинарная задача квадратичного программирования: обзор» (PDF) . Журнал комбинаторной оптимизации . 28 : 58–81. doi :10.1007/s10878-014-9734-0. S2CID  16808394.
2. Гловер, Фред; Кохенбергер, Гэри (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 .