Просмотр кода страницы Метод эллипсоидов

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

[[Файл:Ellipsoid-method.png|thumb]]

== Описание алгоритма ==
В начале выбирается большой шар, содержащий пересечение выпуклых множеств. Способ построения этого шара зависит от задачи. Далее на каждом шаге имеется эллипсоид, заданный центром <math>v</math> и векторами <math>v_1, v_2, \dots, v_n \in \mathbb{R}^n</math>. Эллипсоиду принадлежат точки <math>v+c_1v_1+c_2v_2+\cdots+c_nv_n</math> для которых <math>c_1^2+c_2^2+\cdots+c_n^2\leqslant 1</math>. Отметим, что один и тот же эллипсоид можно задать несколькими способами. Если центр этого эллипсоида принадлежит всем выпуклым множествам, то искомая точка найдена. Иначе существует гиперплоскость <math>\pi</math>, проходящая через точку <math>v</math>, такая, что одно из множеств целиком лежит по одну сторону от неё. Тогда можно перейти от исходного базиса <math>v_i</math> к другому базису <math>\tau, w_2, \dots w_n</math> такому, что <math>w_i</math> параллельны <math>\pi</math>, а <math>\tau</math> направлен в сторону множества. Положим теперь <math>v'=v+\frac{\tau}{n+1}</math>, <math>v'_1=\frac{n\tau}{n+1}</math>, <math>v'_i=w_i\frac{n}{\sqrt{n^2-1}}</math> при <math>i\ge 2</math>. Этот новый эллипсоид содержит половину старого и имеет меньший объём. Таким образом, объём эллипсоида уменьшается экспоненциально с ростом числа шагов и искомая точка будет найдена за <math>O(n^2\log(V_1/V_2))</math> шагов, где <math>V_1</math> — объем исходного шара, а <math>V_2</math> — объем области пересечения. Общее время работы алгоритма получается равным <math>O(Ntn^2\log(V_1/V_2))</math>, где <math>N</math> — число множеств, <math>t</math> — время проверки принадлежности точки множеству.

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

==Эффективность метода==
Полиномиальный алгоритм теоретически мог бы стать новым стандартом, однако, на практике алгоритм Хачияна применять следует с осторожностью: существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, количество же существенно более простых итераций симплекс-метода в таких случаях исчисляется сотнями или даже десятками {{sfn|Николенко|2005}}{{sfn|Схрейвер|1991|с=264}}. Однако, есть примеры задач, для которых алгоритмы этого класса работают в сотни раз эффективнее стандартных реализаций симплекс-метода.

==Примечания==
{{примечания|2}}
==Литература==
{{refbegin|colwidth=30em}}
*{{книга
|автор=С.А. Ашманов
|заглавие=Линейное программирование
|год=1981
|место=М.
|издательство=Главная редакция физико-математической литературы
|страницы=288-289
}}
*{{книга
|автор=А. Схрейвер
|ref=Схрейвер
|заглавие=Теория линейного и целочисленного программирования, т1
|издательство=«Мир»
|год=1991
|isbn=5-03-002754-8
|место=М.
}}
*{{статья
|автор=С. Николенко
|ref=Николенко
|заглавие=Теория и практика сложности
|издание=Компьютерра
|выпуск=31 
|место=М.
|издательство=ООО Журнал «Компьютерра»
|год=2005
}}
{{refend}}

{{нет источников|дата=2015-01-20}}
{{Методы оптимизации}}

[[Категория:Геометрические алгоритмы]]
[[Категория:Выпуклая геометрия]]
[[Категория:алгоритмы оптимизации | методы оптимизации]]
[[Категория:Линейное программирование]]