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

Геометрическая идея метода эллипсоидов разительно отличается от движения по вершинам многогранника в симплекс-методе. Алгоритм начинает работу с построения гигантского многомерного эллипсоида, который гарантированно содержит внутри себя область допустимых решений (если она существует) и, соответственно, точку оптимума. На каждой итерации вычисляется центр текущего эллипсоида. Если этот центр не является допустимым решением или не оптимален, строится отсекающая гиперплоскость (оракул разделения), проходящая через центр, которая отсекает ровно половину эллипсоида, в которой точно нет искомого решения.

Далее вокруг оставшейся «полезной» половины (полуэллипсоида) описывается новый эллипсоид минимального объема. Важнейшим математическим свойством этого процесса является то, что объем каждого следующего эллипсоида убывает в строгой геометрической прогрессии. Отношение объемов двух последовательных эллипсоидов ограничено сверху величиной, строго меньшей единицы и зависящей только от размерности пространства задачи. Поскольку объем начального эллипсоида конечен, а минимально возможный объем многогранника решений (при его невырожденности) ограничен снизу, процесс сжатия неизбежно приведет алгоритм к попаданию центра эллипсоида в область допустимых оптимальных решений за полиномиальное число шагов.

Несмотря на колоссальный теоретический прорыв, метод эллипсоидов оказался малопригодным для практических промышленных расчетов. Постоянные множители в полиномиальной оценке времени работы огромны, а вычислительная неустойчивость, связанная с многократным извлечением квадратных корней и округлениями при описании новых эллипсоидов, делает его применение на реальных задачах крайне медленным по сравнению с симплекс-методом. Тем не менее, теоретическое значение алгоритма невозможно переоценить. Он стал мощнейшим инструментом в комбинаторной оптимизации, показав, что если для задачи существует полиномиальный оракул разделения (алгоритм, проверяющий допустимость точки и выдающий разделяющую гиперплоскость), то вся задача оптимизации может быть решена за полиномиальное время.

Именно метод эллипсоидов подготовил почву для создания алгоритмов внутренней точки Кармаркара, которые объединили полиномиальную сложность с высочайшей практической эффективностью. Понимание математики гиперсфер и аффинных преобразований, лежащих в основе метода Хачияна, обязательно для глубокого изучения теории оптимизации. Это классический пример того, как теория задает вектор для развития прикладных вычислительных методов, расширяя границы возможного в анализе данных и исследовании операций.

Список литературы:
1. Хачиян Л.Г. Полиномиальные алгоритмы в линейном программировании. — М.: ЖВМиМФ, 1980.
2. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. — М.: Мир, 1985.
3. Гротшель М., Ловас Л., Схрейвер А. Геометрические алгоритмы и комбинаторная оптимизация. — М.: Мир, 1990.