Метод эллипсоидов | это... Что такое Метод эллипсоидов? (original) (raw)
Метод эллипсоидов — алгоритм нахождения точки, лежащей в пересечении выпуклых множеств.
Описание алгоритма
В начале выбирается большой шар, содержащий пересечение выпуклых множеств. Способ построения этого шара зависит от задачи. Далее на каждом шаге имеется эллипсоид, заданный центром и векторами
. Эллипсоиду принадлежат точки
для которых
. Отметим, что один и тот же эллипсоид можно задать несколькими способами. Если центр этого эллипсоида принадлежит всем выпуклым множествам, то искомая точка найдена. Иначе существует гиперплоскость
, проходящая через точку
, такая, что одно из множеств целиком лежит по одну сторону от нее. Тогда можно перейти от исходного базиса
к другому базису
такому, что
параллельны
, а
направлен в сторону множества. Положим теперь
,
,
при
. Этот новый эллипсоид содержит половину старого и имеет меньший объем. Таким образом, объем эллипсоида уменьшается экспоненциально с ростом числа шагов и искомая точка будет найдена за
шагов, где
— объем исходного шара, а
— объем области пересечения. Общее время работы алгоритма получается равным
, где
— число множеств,
— время проверки принадлежности точки множеству.
Применение к задаче линейного программирования
Если в задаче линейного программирования удалось построить шар, содержащий искомое решение, то она может быть решена методом эллипсоидов. Для этого вначале находим какую-нибудь точку внутри шара, удовлетворяющую ограничениям задачи. Проводим через нее гиперплоскость
, где
— целевая функция, и находим точку в пересечении исходных и новой гиперплоскостей (начиная с текущего эллипсоида). С новой найденной точкой проделываем то же самое. Процесс сходится к оптимальному решению с экспоненциальной скоростью (поскольку с этой скоростью убывает объем эллипсоида).