Хачиян: метод эллипсоидов

Вопрос

Симплекс-метод Данцига с 1947 года работал прекрасно: на реальных задачах он находил оптимум за число шагов порядка числа ограничений. Но доказать, что так будет всегда, никому не удавалось, — и в 1972 году Виктор Кли и Джордж Минти построили пример, на котором симплекс-метод обходит все вершины многогранника, то есть работает экспоненциальное время.

Значит, вопрос открыт: лежит ли линейное программирование в классе $\mathrm{P}$? К 1979 году это была одна из самых заметных открытых задач в теории алгоритмов — тем более что вокруг, после работ Кука, Карпа и Левина, почти всё оказывалось NP-полным.

Ответ

Леонид Генрихович Хачиян, двадцати шести лет, сотрудник Вычислительного центра АН СССР, напечатал в 1979 году в «Докладах Академии наук» заметку «Полиномиальный алгоритм в линейном программировании» — четыре страницы.

Ответ: да, лежит.

Инструмент был не его. Метод эллипсоидов — это метод обобщённого градиентного спуска с растяжением пространства, построенный Наумом Шором в Киеве (1970–1972) и в другой форме — Аркадием Немировским и Давидом Юдиным (1976). Хачиян сделал то, чего не сделали они: провёл анализ битовой сложности. Он показал, что при рациональных входных данных длины $L$ битов метод сходится за число шагов, ограниченное многочленом от $n$ и $L$, и что все промежуточные числа тоже остаются полиномиальной длины (последнее было далеко не очевидно и составляло главную техническую трудность).

Как это работает

Сведём задачу к вопросу о совместности: существует ли $x$ с $Ax\leqslant b$?

1. Возьмём огромный шар $E_0$, заведомо содержащий решение, если оно есть.
2. Проверим центр текущего эллипсоида $E_k$. Если он удовлетворяет всем неравенствам — ответ найден.
3. Иначе найдётся нарушенное неравенство $a^{\mathsf T}x\leqslant\beta$. Все решения лежат в полупространстве $a^{\mathsf T}x\leqslant a^{\mathsf T}x_k$, то есть в половине эллипсоида.
4. Опишем вокруг этой половины эллипсоид наименьшего объёма — он считается явной формулой — и назовём его $E_{k+1}$. Вернёмся к шагу 2.

Ключевая оценка: объём убывает на каждом шаге в фиксированное число раз,

$$\frac{\mathrm{vol}\,E_{k+1}}{\mathrm{vol}\,E_{k}}\leqslant e^{-1/(2(n+1))}.$$

Убывание медленное, но геометрическое. А снизу объём множества решений, если оно непусто, ограничен величиной, зависящей только от длины записи чисел. Как только объём эллипсоида упал ниже этой границы, можно уверенно сказать: решений нет. Число шагов получается порядка $n^{2}L$.

Обратите внимание на устройство рассуждения: алгоритм не ищет решение, а последовательно сжимает область, где оно могло бы быть, и останавливается, когда область стала меньше самого маленького возможного решения. Это в чистом виде идея двоичного поиска, перенесённая в $n$ измерений.

7 ноября 1979 года

Работа вышла в феврале 1979-го и полгода пролежала незамеченной. Осенью её обнаружили западные специалисты, и дальше произошло то, что до сих пор приводят в пример на курсах научной журналистики.

7 ноября 1979 года New York Times вынесла на первую полосу заметку «A Soviet Discovery Rocks World of Mathematics». Через три недели вышло продолжение — «Soviet Mathematician Is Obscure No More», потому что никто на Западе не мог понять, кто такой Хачиян.

Беда была в содержании. Из статьи следовало, что советский математик решил задачу коммивояжёра, а заодно поставил под угрозу все шифры мира. Ни то, ни другое не имело отношения к делу: линейное программирование — задача из $\mathrm{P}$-стороны мира, и полиномиальный алгоритм для неё ничего не говорит об NP-полных задачах. Газета выбрала сюжет поэффектнее.

Хачияна это не радовало. Он давал понять, что его результат — теоретический и на практике ничего не ускоряет.

Честная оговорка

И он был прав. Метод эллипсоидов на практике медленнее симплекс-метода, обычно на порядки. Сходимость геометрическая, но с показателем $1/(2(n+1))$: при $n=100$ на уменьшение объёма вдвое уходит около 140 шагов. Ни одна промышленная программа линейного программирования методом эллипсоидов не пользуется.

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

Настоящая ценность

Она обнаружилась через два года, и она больше исходной.

Мартин Грётшель, Ласло Ловас и Александр Схрейвер заметили: методу эллипсоидов не нужен список ограничений. Ему нужен только оракул отделимости — процедура, которая по точке отвечает «эта точка внутри» либо предъявляет одно нарушенное неравенство.

Отсюда теорема, которую формулируют коротко: оптимизация полиномиально эквивалентна отделимости.

Следствия сильные. Если у выпуклого множества экспоненциально много граней, но по точке можно быстро найти нарушенное неравенство, то оптимизировать по нему можно быстро. Так получены полиномиальные алгоритмы там, где перебор ограничений безнадёжен:

• задача о паросочетании в общем графе (описание многогранника Эдмондса содержит экспоненциально много неравенств, но нарушенное находится быстро);
• минимизация субмодулярных функций;
• вычисление тета-функции Ловаса, зажатой между числом независимости и хроматическим числом.

То есть метод эллипсоидов оказался не алгоритмом, а инструментом доказательства полиномиальности — и в этом качестве незаменим до сих пор.

Что было дальше

В 1984 году Нарендра Кармаркар предложил метод внутренней точки: полиномиальный и при этом быстрый на практике. Из него выросло целое направление — внутренние методы для выпуклой оптимизации, разработанное в значительной мере Юрием Нестеровым и Аркадием Немировским. Сегодня промышленные решатели держат оба движка: симплекс-метод и внутреннюю точку, — и выбирают по задаче.

А вопрос, поставленный Кли и Минти, до сих пор открыт в одной части: существует ли вариант симплекс-метода с полиномиальным числом шагов? Это упирается в гипотезу Хирша о диаметре многогранника, опровергнутую в исходной форме Франсиско Сантосом в 2010 году; полиномиальная граница диаметра не доказана и не опровергнута.

Хачиян эмигрировал в 1989 году, работал в Корнелле, с 1990-го — в Ратгерском университете. Умер в 2005-м, пятидесяти двух лет.

Заметим, чем замкнулась дуга. Канторович в 1939 году поставил задачу и увидел двойственность. Данциг в 1947-м дал способ считать. Хачиян в 1979-м доказал, что считать можно быстро всегда. Сорок лет от фанерного треста до теоремы о классе сложности.

Задача. Посмотрите, во что превращается метод эллипсоидов при $n=1$, и сравните точное убывание объёма с общей оценкой $e^{-1/(2(n+1))}$.
(Ответ: «эллипсоид» на прямой — это отрезок, его центр — середина, а «половина эллипсоида» — половина отрезка; наименьший отрезок, содержащий её, — она сама. Значит, метод превращается в обычное деление отрезка пополам, и длина убывает ровно вдвое: коэффициент $0{,}5$. Общая оценка даёт $e^{-1/4}\approx0{,}78$ — она сильно занижена, потому что рассчитана на худший случай в любой размерности. Заметьте и обратное: с ростом $n$ множитель стремится к единице, и медленность метода — не дефект реализации, а свойство самой геометрии.)

Следующая точка: Мюррей-Хилл — где у всей защищённой связи обнаружится срок годности.