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

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

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

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

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

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

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

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