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

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

В начале выбирается большой шар, содержащий пересечение выпуклых множеств. Способ построения этого шара зависит от задачи. Далее на каждом шаге имеется эллипсоид, заданный центром v и векторами . Эллипсоиду принадлежат точки для которых . Отметим, что один и тот же эллипсоид можно задать несколькими способами. Если центр этого эллипсоида принадлежит всем выпуклым множествам, то искомая точка найдена. Иначе существует гиперплоскость π, проходящая через точку v, такая, что одно из множеств целиком лежит по одну сторону от нее. Тогда можно перейти от исходного базиса v_i к другому базису такому, что w_i параллельны π, а τ направлен в сторону множества. Положим теперь , , при . Этот новый эллипсоид содержит половину старого и имеет меньший объем. Таким образом, объем эллипсоида уменьшается экспоненциально с ростом числа шагов и искомая точка будет найдена за O) шагов, где V₁ — объем исходного шара, а V₂ — объем области пересечения. Общее время работы алгоритма получается равным O), где N — число множеств, t — время проверки принадлежности точки множеству.