Метод эллипсоидов Леонида Хачияна: доказательство полиномиальной сложности линейного программирования

Метод эллипсоидов не был изобретен с нуля; Хачиян гениально адаптировал алгоритмы нелинейной безусловной оптимизации, разработанные ранее Наумом Шором, Аркадием Немировским и Давидом Юдиным. Математическая суть алгоритма заключается в локализации области допустимых решений. Вместо того чтобы двигаться по ребрам многогранника (как симплекс-метод), метод эллипсоидов охватывает весь многогранник целиком гигантской n-мерной сферой (эллипсоидом). Алгоритм гарантирует, что искомое оптимальное решение (или допустимая точка) находится где-то внутри этой начальной сферы.

На каждом итерационном шаге алгоритм берет геометрический центр текущего эллипсоида и задает вопрос математическому «Оракулу разделения» (Separation Oracle): находится ли этот центр внутри области допустимых решений? Если нет, оракул возвращает плоскость (одно из нарушенных линейных ограничений задачи), которая строго отсекает ту половину эллипсоида, в которой точно нет решений. Алгоритм отбрасывает эту «плохую» половину и строит вокруг оставшейся «хорошей» половины новый, меньший по объему эллипсоид. Этот процесс итеративного отсечения и сжатия продолжается шаг за шагом.

Математический триумф Хачияна базировался на двух строгих доказательствах. Во-первых, он доказал, что отношение объема нового эллипсоида к объему старого всегда строго меньше единицы (объем убывает в геометрической прогрессии, зависящей только от размерности пространства n). Во-вторых, он вычислил точный минимальный предел объема, который может иметь область допустимых решений целочисленной матрицы (зависящий от длины бинарной записи исходных данных, $L$). Как только объем эллипсоида становится меньше этого предела, алгоритм может быть с уверенностью остановлен: либо внутри осталась единственная истинная вершина-решение, либо решений не существует вообще (система несовместна).

Число необходимых шагов алгоритма Хачияна ограничено величиной $O(n^4 L)$, что является строгим полиномиальным пределом. Отношение $P = NP$ для линейного программирования было закрыто. Парадокс заключается в том, что несмотря на свой теоретический триумф, метод эллипсоидов оказался абсолютно непригодным для практических расчетов. Огромные константы в полиноме и проблемы с точностью машинного округления делали его на практике в тысячи раз медленнее «экспоненциального» симплекс-метода. Однако работа Хачияна стала катализатором, который всего через пять лет привел к созданию полиномиальных алгоритмов внутренней точки (метод Кармаркара), которые сегодня являются индустриальным стандартом для решения логистических матриц с миллионами переменных.