Proyecciones sobre conjuntos convexos

En matemáticas, las proyecciones sobre conjuntos convexos ( POCS ), a veces conocidas como el método de proyección alternada , es un método para encontrar un punto en la intersección de dos conjuntos convexos cerrados . Es un algoritmo muy simple y ha sido redescubierto muchas veces. ^[1] El caso más simple, cuando los conjuntos son espacios afines , fue analizado por John von Neumann . ^{[2] [3]} El caso cuando los conjuntos son espacios afines es especial, ya que las iteraciones no solo convergen a un punto en la intersección (asumiendo que la intersección no está vacía) sino a la proyección ortogonal del punto sobre la intersección. Para conjuntos convexos cerrados generales, el punto límite no necesita ser la proyección. El trabajo clásico sobre el caso de dos conjuntos convexos cerrados muestra que la tasa de convergencia de las iteraciones es lineal. ^{[4] [5]} Ahora hay extensiones que consideran casos cuando hay más de dos conjuntos, o cuando los conjuntos no son convexos , ^[6] o que dan tasas de convergencia más rápidas. El análisis de POCS y métodos relacionados intenta demostrar que el algoritmo converge (y, de ser así, encontrar la tasa de convergencia ), y si converge a la proyección del punto original. Estas preguntas son ampliamente conocidas para casos simples, pero un tema de investigación activa para las extensiones. También existen variantes del algoritmo, como el algoritmo de proyección de Dykstra . Consulte las referencias en la sección de lectura adicional para obtener una descripción general de las variantes, extensiones y aplicaciones del método POCS; se puede encontrar una buena base histórica en la sección III de. ^[7]

Algoritmo

Ejemplo sobre dos círculos

El algoritmo POCS resuelve el siguiente problema:

${\displaystyle {\text{find}}\;x\in \mathbb {R} ^{n}\quad {\text{such that}}\;x\in C\cap D}$

donde C y D son conjuntos convexos cerrados .

Para utilizar el algoritmo POCS es necesario saber cómo proyectar sobre los conjuntos C y D por separado, a través de las proyecciones . ${\displaystyle {\mathcal {P}}_{i}}$

El algoritmo comienza con un valor arbitrario para y luego genera la secuencia ${\displaystyle x_{0}}$

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

La simplicidad del algoritmo explica en parte su popularidad. Si la intersección de C y D no está vacía, la secuencia generada por el algoritmo convergerá a algún punto de esta intersección.

A diferencia del algoritmo de proyección de Dykstra , la solución no necesita ser una proyección sobre la intersección C y D.

Algoritmos relacionados

Ejemplo de variante de proyecciones promediadas

El método de las proyecciones promediadas es bastante similar. Para el caso de dos conjuntos convexos cerrados C y D , se procede de la siguiente manera:

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

Se sabe desde hace mucho tiempo que converge globalmente. ^[8] Además, el método es fácil de generalizar a más de dos conjuntos; algunos resultados de convergencia para este caso se encuentran en. ^[9]

El método de proyecciones promediadas se puede reformular como método de proyecciones alternas utilizando un truco estándar. Considere el conjunto

${\displaystyle E=\{(x,y):x\in C,\;y\in D\}}$

que se define en el espacio del producto . Luego defina otro conjunto, también en el espacio del producto: ${\displaystyle \mathbb {R} ^{n}\times \mathbb {R} ^{n}}$

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

Por lo tanto, encontrar es equivalente a encontrar . ${\displaystyle C\cap D}$ ${\displaystyle E\cap F}$

Para hallar un punto en , se utiliza el método de proyección alternada. La proyección de un vector sobre el conjunto F está dada por . Por lo tanto ${\displaystyle E\cap F}$ ${\displaystyle (x,y)}$ ${\displaystyle (x+y,x+y)/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})).}$

Dado que y suponiendo , entonces para todos , y por lo tanto podemos simplificar la iteración a . ${\displaystyle x_{k+1}=y_{k+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}))}$

Referencias

1. Bauschke, HH; Borwein, JM (1996). "Sobre algoritmos de proyección para resolver problemas de viabilidad convexa". SIAM Review . 38 (3): 367–426. CiteSeerX  10.1.1.49.4940 . doi :10.1137/S0036144593251710.
2. J. von Neumann, Neumann, John Von (1949). "Sobre anillos de operadores. Teoría de la reducción". Ann. of Math . 50 (2): 401–485. doi :10.2307/1969463. JSTOR  1969463.(una reimpresión de notas de conferencias distribuidas por primera vez en 1933)
3. J. von Neumann. Operadores funcionales, volumen II. Princeton University Press, Princeton, NJ, 1950. Reimpresión de notas de clase mimeografiadas distribuidas por primera vez en 1933.
4. Gubin, LG; Polyak, BT; Raik, EV (1967). "El método de proyecciones para encontrar el punto común de conjuntos convexos". Matemáticas computacionales y física matemática de la URSS . 7 (6): 1–24. doi :10.1016/0041-5553(67)90113-9.
5. Bauschke, HH; Borwein, JM (1993). "Sobre la convergencia del algoritmo de proyección alternada de von Neumann para dos conjuntos". Set-Valued Analysis . 1 (2): 185–212. doi :10.1007/bf01027691. S2CID  121602545.
6. Lewis, Adrian S.; Malick, Jérôme (2008). "Proyecciones alternas sobre variedades". Matemáticas de la investigación de operaciones . 33 : 216–234. CiteSeerX 10.1.1.416.6182 . doi :10.1287/moor.1070.0291. 
7. Combettes, PL (1993). "Los fundamentos de la estimación teórica de conjuntos" (PDF) . Actas del IEEE . 81 (2): 182–208. doi :10.1109/5.214546. Archivado desde el original (PDF) el 2015-06-14 . Consultado el 2012-10-09 .
8. A. Auslender. Métodos numéricos para la resolución de problemas de optimización con restricciones. Tesis doctoral, Facultad de Ciencias, Grenoble, 1969
9. Lewis, AS; Luke, DR; Malick, J. (2009). "Convergencia local para proyecciones no convexas alternadas y promediadas". Fundamentos de las matemáticas computacionales . 9 (4): 485–513. arXiv : 0709.0109 . doi :10.1007/s10208-008-9036-y.

Lectura adicional

• Libro de 2011: Métodos de Proyección Alternada de René Escalante y Marcos Raydan (2011), publicado por SIAM.