Proyecciones sobre conjuntos convexos

En matemáticas, las proyecciones sobre conjuntos convexos ( POCS ), a veces conocidas como el método de proyección alternada , son 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 (suponiendo que la intersección no es vacía) sino a la proyección ortogonal del punto sobre la intersección. Para conjuntos convexos cerrados generales, el punto límite no tiene por qué ser la proyección. Trabajos clásicos sobre el caso de dos conjuntos convexos cerrados muestran que la tasa de convergencia de las iteraciones es lineal. ^{[ 4 ] [ 5 ]} Ahora existen 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 busca demostrar la convergencia del algoritmo (y, de ser así, determinar su tasa de convergencia ) y si converge a la proyección del punto original. Estas cuestiones son bien conocidas para casos sencillos, pero constituyen un tema de investigación activa para sus extensiones. Existen también variantes del algoritmo, como el algoritmo de proyección de Dykstra . Consulte las referencias en la sección de lecturas adicionales para obtener una visión general de las variantes, extensiones y aplicaciones del método POCS; un buen contexto histórico se encuentra en la sección III de ^{[ 7 ] .}

El algoritmo POCS resuelve el siguiente problema:

${\displaystyle {\text{encontrar}}\;x\in \mathbb {R} ^{n}\quad {\text{tal que}}\;x\in C\cap D}$

donde C y D son conjuntos convexos cerrados .

Para utilizar el algoritmo POCS, uno debe 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${\displaystyle x_{0}}$y luego genera la secuencia

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

La sencillez 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 dicha intersección.

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

El método de proyecciones promediadas es bastante similar. Para el caso de dos conjuntos convexos cerrados C y D , 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 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 puede reformularse como un método de proyecciones alternas utilizando un truco estándar. Consideremos el conjunto

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

que se define en el espacio de productos${\displaystyle \mathbb {R} ^{n}\times \mathbb {R} ^{n}}$. A continuación, definimos otro conjunto, también en el espacio producto:

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

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

Para encontrar un punto en${\displaystyle E\cap F}$, utilice el método de proyección alternada. La proyección de un vector${\displaystyle (x,y)}$sobre el conjunto F está dado por${\displaystyle (x+y,x+y)/2}$. Por eso

${\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})).}$

Desde${\displaystyle x_{k+1}=y_{k+1}}$y suponiendo${\displaystyle x_{0}=y_{0}}$, entonces${\displaystyle x_{j}=y_{j}}$a pesar de${\displaystyle j\geq 0}$y por lo tanto podemos simplificar la iteración a${\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}$.

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