Интернет магазин китайских планшетных компьютеров



Компьютеры - Метод эллипсоидов

23 января 2011


Оглавление:
1. Метод эллипсоидов
2. Применение к задаче линейного программирования



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

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



Просмотров: 1265


<<< Линейное программирование
Ограничивающая сфера >>>