WikiDer > Проекции на выпуклые множества

Эта статья может быть сбивает с толку или неясно читателям. Пожалуйста, помоги нам прояснить статью. Возможно обсуждение этого вопроса на страница обсуждения. (Апрель 2018 г.) (Узнайте, как и когда удалить этот шаблон сообщения)

В математике проекции на выпуклые множества (POCS), иногда называемый переменная проекция метод, это метод поиска точки на пересечении двух закрыто выпуклый наборы. Это очень простой алгоритм, который переоткрывался много раз.^[1] Самый простой случай, когда наборы аффинные пространства, был проанализирован Джон фон Нейман.^[2][3] Случай, когда множества являются аффинными пространствами, является особым, поскольку итерации не только сходятся к точке на пересечении (при условии, что пересечение непусто), но и к ортогональной проекции точки на пересечение. Для общих замкнутых выпуклых множеств предельная точка не обязательно должна быть проекцией. Классическая работа над случаем двух замкнутых выпуклых множеств показывает, что скорость сходимости итераций линейно.^[4][5]Теперь есть расширения, которые рассматривают случаи, когда существует более одного набора, или когда наборы не выпуклый,^[6] или которые обеспечивают более высокую скорость сходимости. Анализ POCS и связанных методов пытается показать, что алгоритм сходится (и если да, найти скорость сходимости) и сходится ли она к проекция исходной точки. Эти вопросы в основном известны для простых случаев, но являются предметом активных исследований для расширений. Также существуют варианты алгоритма, такие как Алгоритм проектирования Дикстры. См. Ссылки в дальнейшее чтение раздел для обзора вариантов, расширений и приложений метода POCS; хороший исторический фон можно найти в разделе III.^[7]

Алгоритм

Пример на двух кругах

Алгоритм POCS решает следующую проблему:

${ displaystyle { text {find}} ; x in mathbb {R} ^ {n} quad { text {такой, что}} ; x in C cap D}$

куда C и D находятся закрыто выпуклые множества.

Чтобы использовать алгоритм POCS, нужно знать, как проецировать на наборы C и D отдельно.Алгоритм начинается с произвольного значения для ${ displaystyle x_ {0}}$ а затем генерирует последовательность

${ displaystyle x_ {k + 1} = { mathcal {P}} _ {C} left ({ mathcal {P}} _ {D} (x_ {k}) right).}$

Простота алгоритма частично объясняет его популярность. Если пересечение из C и D непусто, то последовательность сгенерированный алгоритмом будет сходиться в какой-то момент на этом перекрестке.

В отличие от Алгоритм проектирования Дикстры, решение не обязательно должно быть проекцией на пересечение C и D.

Связанные алгоритмы

Пример усредненные прогнозы вариант

Методика усредненные прогнозы очень похоже. Для случая двух замкнутых выпуклых множеств C и D, он продолжается

${ displaystyle x_ {k + 1} = { frac {1} {2}} ({ mathcal {P}} _ {C} (x_ {k}) + { mathcal {P}} _ {D} (x_ {k}))}$

Давно известно о глобальном сближении.^[8] Более того, этот метод легко обобщить более чем на два набора; некоторые результаты сходимости для этого случая есть.^[9]

В усредненный метод прогнозов можно переформулировать как чередование метод проекций с использованием стандартного приема. Рассмотрим множество

${ Displaystyle Е = {(х, у): х в С, ; у в D }}$

который определен в пространство продукта ${ Displaystyle mathbb {R} ^ {n} times mathbb {R} ^ {n}}$. Затем определите другой набор, также в области продукта:

${ displaystyle F = {(x, y): x in mathbb {R} ^ {n}, , y in mathbb {R} ^ {n}, ; x = y }.}$

Таким образом, находя ${ Displaystyle C cap D}$ эквивалентно поиску ${ displaystyle E cap F}$.

Чтобы найти точку в ${ displaystyle E cap F}$используйте метод попеременного проецирования. Проекция вектора ${ Displaystyle (х, у)}$ на съемочную площадку F дан кем-то ${ Displaystyle (х + у, х + у) / 2}$. Следовательно

${ displaystyle (x_ {k + 1}, y_ {k + 1}) = { mathcal {P}} _ {F} ({ mathcal {P}} _ {E} ((x_ {k}, y_ {k}))) = { mathcal {P}} _ {F} (({ mathcal {P}} _ {C} x_ {k}, { mathcal {P}} _ {D} y_ {k })) = { frac {1} {2}} ({ mathcal {P}} _ {C} (x_ {k}) + { mathcal {P}} _ {D} (y_ {k}) , ({ mathcal {P}} _ {C} (x_ {k}) + { mathcal {P}} _ {D} (y_ {k})).}$

С ${ Displaystyle х_ {к + 1} = у_ {к + 1}}$ и предполагая ${ displaystyle x_ {0} = y_ {0}}$, тогда ${ displaystyle x_ {j} = y_ {j}}$ для всех ${ displaystyle j geq 0}$, и, следовательно, мы можем упростить итерацию до ${ displaystyle x_ {k + 1} = { frac {1} {2}} ({ mathcal {P}} _ {C} (x_ {k}) + { mathcal {P}} _ {D} (x_ {k}))}$.

Рекомендации

дальнейшее чтение

• Книга с 2011 года: Альтернативные методы проецирования Рене Эскаланте и Маркос Райдан (2011), опубликовано SIAM.