Русская Википедия:Проецирование в выпуклые множества
Проецирование в выпуклые множества (Шаблон:Lang-en, POCS), которое иногда упоминается как метод попеременного проецирования, является методом поиска точки в пересечении двух замкнутых выпуклых множеств. Это очень простой алгоритм и был переоткрыт много разШаблон:Sfn. Простой случай, когда множествами являются аффинные пространства, проанализировал Джон фон НейманШаблон:SfnШаблон:Sfn. Случай аффинных пространств является частным, поскольку итерации сходятся не просто к точке в пересечении (в предположении, что пересечение не пустое), а к ортогональной проекции (исходной) точки на пересечение множеств. Для случая общих замкнутых выпуклых множеств предельная точка не обязательно будет проекцией. Классическая работа для случая двух замкнутых выпуклых множеств показывает, что скорость сходимости итераций линейнаШаблон:SfnШаблон:Sfn. Имеются расширения, в которых рассматриваются случаи более одного множества, или когда множества не выпуклыШаблон:Sfn, или варианты, дающие более быструю сходимость. При анализе POCS и связанных методов пытаются показать, что алгоритм сходится (и если тaк, пытаются найти скорость сходимости), и выяснить, сходится ли метод к проекции исходной точки. Ответы, в основном, известны для простых случаев, но эта область активно исследуется в направлении обобщений. Есть два варианта алгоритма, таких как алгоритм Дикстры[1]. См. ссылки в разделе «Литература для дальнейшего чтения» с обзором вариантов, обобщений и приложений метода POCS. Хорошее изложение истории метода можно найти в разделе III книги КомбетаШаблон:Sfn.
Алгоритм
Алгоритм POCS решает следующую задачу:
- найти <math>\; x \in \mathbb{R}^n \quad</math>, такой, что <math>\; x \in C \cap D </math>
где C и D два замкнутых выпуклых множества.
Чтобы использовать алгоритм POCS, нужно знать, как проецировать в множества C и D по отдельности. Алгоритм начинается с произвольного значения <math>x_0</math> и генерирует последовательность
- <math>x_{k+1} = \mathcal{P}_C \left( \mathcal{P}_D ( x_k ) \right). </math>
Простота алгоритма объясняет его популярность. Если пересечение множеств C и D не пусто, то последовательность, порождённая алгоритмом, будет сходиться к некоторой точке в их пересечении.
В отличие от алгоритма проектирования Дикстры, решение не обязательно окажется проекцией в пересечение множеств C и D.
Связанные алгоритмы
Метод усреднённого проецирования аналогичен. Для случая двух замкнутых выпуклых множеств C и D он работает по формуле
- <math> x_{k+1} = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(x_k) ) </math>
Давно известно, что он сходится глобальноШаблон:Sfn. Более того, метод просто обобщить на более чем два множества. Некоторые результаты сходимости для этого случая можно найти в статье Льюиса, Люка и МаликаШаблон:R.
Метод усреднённого проецирования можно переформулировать как метод поочерёдного проецирования с помощью стандартного приёма. Рассмотрим множество
- <math> E = \{ (x,y) : x \in C, \; y \in D \}</math>,
которое определено в произведении пространств <math> \mathbb{R}^n \times \mathbb{R}^n </math>. Определим теперь другое множество, также в произведении пространств:
- <math> F = \{ (x,y) : x \in \mathbb{R}^n,\, y \in \mathbb{R}^n,\; x=y \}.</math>
Тогда нахождение <math> C \cap D </math> эквивалентно нахождению <math> E \cap F</math>.
Чтобы найти точку в <math> E \cap F</math>, используем метод поочерёдного проецирования. Проекция вектора <math>(x,y)</math> в множество F задаётся выражением <math>(x+y,x+y)/2</math>, следовательно,
- <math>(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) ). </math>
Поскольку <math> x_{k+1} = y_{k+1} </math>, в предположении, что <math> x_0 = y_0 </math>, будем иметь <math>x_j=y_j</math> для всех <math> j \geqslant 0</math>, а следовательно, мы можем упростить итерацию до <math> x_{k+1} = \frac{1}{2}( \mathcal{P}_C(x_k) + \mathcal{P}_D(x_k) ) </math>.
Примечания
Литература
- Шаблон:Книга
- Шаблон:Статья
- Шаблон:Статья (Репринт лекционных заметок, выпущенных в 1933)
- Шаблон:Книга Reprint of mimeographed lecture notes first distributed in 1933
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
- Шаблон:Статья
Литература для дальнейшего чтения
- ↑ Обратите внимание, Дикстры, а не Дейкстры, это разные люди.
