MAX-CUT и SDP: округлить направления случайной гиперплоскостью

Коротко

В MAX-CUT нужно разделить вершины на две части, максимизируя вес рёбер между ними. Монетка для каждой вершины даёт половину общего веса в ожидании. Алгоритм Гоэманса-Уильямсона заменяет знак каждой вершины единичным вектором и решает полуопределённую релаксацию, SDP. Затем случайная гиперплоскость через начало разделяет векторы по сторонам. Ребро между векторами с углом θ разрезается с вероятностью θ/π. Сопоставление этой вероятности с вкладом ребра в релаксацию даёт ожидаемую гарантию не меньше 0,878·OPT при неотрицательных весах. Это гарантия округления найденного оптимума SDP, а не свойство произвольно выбранных векторов.

Если видишь разницу между допустимыми векторами и оптимумом SDP - переходи к «Теперь сам».

Как думаешь: чем направление лучше дробного знака?

Целый разрез можно записать числами s_v ∈ {−1,+1}. Вклад ребра uv равен w_uv(1 − s_u s_v)/2: одинаковые знаки дают ноль, разные - полный вес. Если заменить каждый знак независимым числом между минус единицей и единицей, связи между соседями теряются. Векторы разрешают промежуточное отношение «скорее по разные стороны», сохраняя согласованность сразу всех пар.

В треугольнике все три ребра нельзя разрезать одновременно. Но три вектора можно разнести на углы 120 градусов: каждая пара будет «больше чем противоположной наполовину». Релаксация даст верхнюю границу, которой реальный разрез может не достигнуть. Округление должно потерять контролируемую долю этой границы.

На что это похоже

Представь людей за круглым столом. Каждому надо назначить одну из двух команд, но до окончательного решения разрешено выбрать место за столом. Далёкие места легче разделить случайной прямой через центр, близкие - труднее. Место ещё не команда: оно задаёт согласованные отношения с остальными, а общая случайная прямая превращает их в один допустимый выбор команд.

Механизм: матрица скалярных произведений

Вместо знаков выбираем единичные векторы v_i. Релаксация максимизирует Σw_ij(1 − v_i·v_j)/2. Любой настоящий разрез вложен в неё: достаточно направить все векторы вдоль одной оси со знаками исходного решения. Значит, оптимум релаксации не меньше OPT.

Чтобы записать задачу без неизвестной размерности векторов, вводят матрицу Грама X_ij = v_i·v_j. На диагонали стоят единицы. Матрица положительно полуопределена, если для любого вещественного столбца z выполняется zᵀXz ≥ 0. Это ровно условие существования вещественных векторов с такими скалярными произведениями. Ограничения на X, диагональ и линейная целевая функция образуют SDP. Оптимум вычисляют с заданной численной точностью; стоимость зависит и от неё. Это не обычная ЛП, поскольку условие на все z не является конечным списком скалярных линейных неравенств по наивной записи.

Для округления берут случайное направление r, равномерное по сфере, и назначают знак по скалярному произведению r·v_i. Обе стороны гиперплоскости автоматически образуют допустимый разрез. Для пары векторов достаточно посмотреть на плоскость, которую они натягивают. Разделяющие направления занимают долю θ/π полного оборота, поэтому вероятность разрезания ребра именно такая.

В релаксации вклад единичного ребра равен (1 − cos θ)/2. Отношение ожидаемого вклада округления к нему - 2θ / (π(1 − cos θ)). Минимум по углам между нулём и π примерно 0,87856. Поэтому для каждого ребра вероятность не меньше 0,878 его расслабленного вклада. Суммируем с неотрицательными весами: ожидаемый разрез не меньше 0,878 значения SDP, а значит и 0,878·OPT. Отрицательные веса в это рассуждение подставлять нельзя: умножение неравенства на отрицательное число меняет знак.

Правило

Сначала оптимизируется согласованная векторная релаксация, затем один общий случайный разрез пространства округляет все вершины. Для неотрицательных весов ожидаемый результат не меньше 0,878 оптимального разреза с учётом точности решения SDP. Отдельный запуск может оказаться хуже этой ожидаемой величины.

Разбор: треугольник и угол 120 градусов

В программе не решается SDP общего графа. Проверяется известное симметричное решение для треугольника и геометрия округления. Это явно отделяет вычисление релаксации от проверки формулы.

max-cut-vektory.py

from math import pi, sin, cos
from itertools import product


def razrez(rebra, znaki):
    return sum(w for u, v, w in rebra if znaki[u] != znaki[v])


def tochno(n, rebra):
    return max(razrez(rebra, p)
               for p in product([-1, 1], repeat=n))


def otnoshenie(theta):
    return 2 * theta / (pi * (1 - cos(theta)))


rebra = [(0, 1, 1), (1, 2, 1), (0, 2, 1)]
ugly = [0, 2 * pi / 3, 4 * pi / 3]
vektory = [(cos(t), sin(t)) for t in ugly]
sdp = sum((1 - cos(ugly[u] - ugly[v])) / 2
          for u, v, _ in rebra)
vesa = []
for k in range(3600):
    t = (k + 0.37) * 2 * pi / 3600
    r = (cos(t), sin(t))
    znaki = [1 if r[0] * x + r[1] * y >= 0 else -1
             for x, y in vektory]
    vesa.append(razrez(rebra, znaki))
print('точный оптимум:', tochno(3, rebra))
print('векторная граница:', round(sdp, 6))
print('среднее по направлениям:', round(sum(vesa) / len(vesa), 6))
print('каждый разрез имеет вес два:', set(vesa) == {2})
mini = min(otnoshenie(k * pi / 100000)
           for k in range(1, 100001))
print('минимум отношения на сетке:', round(mini, 6))

↳ выводpython3 max-cut-vektory.py

точный оптимум: 2
векторная граница: 2.25
среднее по направлениям: 2.0
каждый разрез имеет вес два: True
минимум отношения на сетке: 0.878567

SDP оценивает треугольник в 9/4, хотя настоящий разрез имеет вес не больше двух. Округление симметричных векторов всегда даёт разрез веса два, кроме граничных направлений нулевой меры. Отношение 2 / 2,25 = 8/9 выше общей нижней границы. Численный поиск на сетке иллюстрирует константу; доказательство нижней границы использует анализ функции, а не конечный перебор углов.

Разбор: плохие векторы не дают хорошего алгоритма

Для графа с одним ребром можно назначить обеим вершинам один вектор. Такое решение допустимо для SDP, но его значение ноль и округление никогда не разрежет ребро. OPT равен единице. Противоречия нет: гарантия связывает округление со значением выбранных векторов, а связь с OPT возникает после оптимизации релаксации. Подстановка произвольного набора направлений пропускает ключевой шаг алгоритма.

Что ломается без этого

Независимые случайные знаки вместо общей гиперплоскости возвращают простую половинную гарантию и теряют информацию о векторах. Одна случайная гиперплоскость не обещает минимум 0,878·OPT в каждом запуске. Численный решатель, вернувший сильно неоптимальную матрицу, тоже не даёт исходную теорему автоматически: надо учитывать точность решения и корректность округления.

Зачем это в работе

MAX-CUT возникает при разбиении конфликтующих объектов и в квадратичной булевой оптимизации. Векторные релаксации дают более сильные границы, чем простая монетка, и служат примером, как геометрия улучшает алгоритм с доказательством. При применении сначала проверяют знак весов и модель задачи; одинаковое название «разрез» не делает минимальный разрез и максимальный разрез одной постановкой.

Теперь сам

Два единичных вектора перпендикулярны. Каков вклад единичного ребра в SDP и вероятность его разрезания случайной гиперплоскостью?

Ответ. Скалярное произведение ноль, расслабленный вклад (1 − 0)/2 = 1/2. Угол π/2, вероятность (π/2)/π = 1/2. Для этой пары округление не теряет ничего относительно релаксации. Потеря в общей теореме определяется другим углом, где отношение минимально.

Главное

Геометрическое округление полезно потому, что вероятность разделения каждой пары сравнима с её вкладом в совместную релаксацию.