Метод эллипсоидов

Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств. Разработан А. С. Немировским и доведён до алгоритмической реализации Л. Г. Хачияном в ВЦ АН СССР.

Описание алгоритма

В начале выбирается большой шар, содержащий пересечение выпуклых множеств. Способ построения этого шара зависит от задачи. Далее на каждом шаге имеется эллипсоид, заданный центром ${\displaystyle v}$ и векторами ${\displaystyle v_{1},v_{2},\dots ,v_{n}\in \mathbb {R} ^{n}}$. Эллипсоиду принадлежат точки ${\displaystyle v+c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}}$ для которых ${\displaystyle c_{1}^{2}+c_{2}^{2}+\cdots +c_{n}^{2}\leqslant 1}$. Отметим, что один и тот же эллипсоид можно задать несколькими способами. Если центр этого эллипсоида принадлежит всем выпуклым множествам, то искомая точка найдена. Иначе существует гиперплоскость ${\displaystyle \pi }$, проходящая через точку ${\displaystyle v}$, такая, что одно из множеств целиком лежит по одну сторону от неё. Тогда можно перейти от исходного базиса ${\displaystyle v_{i}}$ к другому базису ${\displaystyle \tau ,w_{2},\dots w_{n}}$ такому, что ${\displaystyle w_{i}}$ параллельны ${\displaystyle \pi }$, а ${\displaystyle \tau }$ направлен в сторону множества. Положим теперь ${\displaystyle v'=v+{\frac {\tau }{n+1}}}$, ${\displaystyle v'_{1}={\frac {n\tau }{n+1}}}$, ${\displaystyle v'_{i}=w_{i}{\frac {n}{\sqrt {n^{2}-1}}}}$ при ${\displaystyle i\geq 2}$. Этот новый эллипсоид содержит половину старого и имеет меньший объём. Таким образом, объём эллипсоида уменьшается экспоненциально с ростом числа шагов и искомая точка будет найдена за ${\displaystyle O(n^{2}\log(V_{1}/V_{2}))}$ шагов, где ${\displaystyle V_{1}}$ — объем исходного шара, а ${\displaystyle V_{2}}$ — объем области пересечения. Общее время работы алгоритма получается равным ${\displaystyle O(Ntn^{2}\log(V_{1}/V_{2}))}$, где ${\displaystyle N}$ — число множеств, ${\displaystyle t}$ — время проверки принадлежности точки множеству.

Применение к задаче линейного программирования

Если в задаче линейного программирования удалось построить шар, содержащий искомое решение, то она может быть решена методом эллипсоидов. Для этого вначале находим какую-нибудь точку ${\displaystyle u}$ внутри шара, удовлетворяющую ограничениям задачи. Проводим через неё гиперплоскость ${\displaystyle f(x)<f(u)}$, где ${\displaystyle f}$ — целевая функция, и находим точку в пересечении исходных и новой гиперплоскостей (начиная с текущего эллипсоида). С новой найденной точкой проделываем то же самое. Процесс сходится к оптимальному решению с экспоненциальной скоростью (поскольку с этой скоростью убывает объём эллипсоида).

Эффективность метода

Полиномиальный алгоритм теоретически мог бы стать новым стандартом, однако, на практике алгоритм Хачияна применять следует с осторожностью: существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, количество же существенно более простых итераций симплекс-метода в таких случаях исчисляется сотнями или даже десятками [1][2]. Однако есть примеры задач, для которых алгоритмы этого класса работают в сотни раз эффективнее стандартных реализаций симплекс-метода.

Примечания

1. Николенко, 2005.
2. Схрейвер, 1991, с. 264.

Литература

• С.А. Ашманов. Линейное программирование. — М.: Главная редакция физико-математической литературы, 1981. — С. 288-289.
• А. Схрейвер. Теория линейного и целочисленного программирования, т1. — М.: «Мир», 1991. — ISBN 5-03-002754-8.
• С. Николенко. Теория и практика сложности // Компьютерра. — М.: ООО Журнал «Компьютерра», 2005. — Вып. 31.