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

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

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

В начале выбирается большой шар, содержащий пересечение выпуклых множеств. Способ построения этого шара зависит от задачи. Далее на каждом шаге имеется эллипсоид, заданный центром $v$ и векторами $v_1,v_2,\dots ,v_n\in {ℝ}^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⩽1$. Отметим, что один и тот же эллипсоид можно задать несколькими способами. Если центр этого эллипсоида принадлежит всем выпуклым множествам, то искомая точка найдена. Иначе существует гиперплоскость $\pi$, проходящая через точку $v$, такая, что одно из множеств целиком лежит по одну сторону от неё. Тогда можно перейти от исходного базиса $v_i$ к другому базису $\tau ,w_2,\dots w_n$ такому, что $w_i$ параллельны $\pi$, а $\tau$ направлен в сторону множества. Положим теперь $v^{\prime }=v+\frac{\tau }{n+1}$, $v{\text{'}}_1=\frac{n\tau }{n+1}$, $v{\text{'}}_i=w_i\frac{n}{\sqrt{n^2-1}}$ при $i\ge 2$. Этот новый эллипсоид содержит половину старого и имеет меньший объём. Таким образом, объём эллипсоида уменьшается экспоненциально с ростом числа шагов и искомая точка будет найдена за $O(n^2\log (V_1/V_2))$ шагов, где $V_1$ — объем исходного шара, а $V_2$ — объем области пересечения. Общее время работы алгоритма получается равным $O(Nt{n}^2\log (V_1/V_2))$, где $N$ — число множеств, $t$ — время проверки принадлежности точки множеству.

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

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

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

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

Литература

• Шаблон:Книга
• Шаблон:Книга
• Шаблон:Статья