Algoritmo de proyección de Dykstra

El algoritmo de Dykstra es un método que calcula un punto en la intersección de conjuntos convexos y es una variante del método de proyección alternada (también llamado método de proyecciones sobre conjuntos convexos ). En su forma más simple, el método encuentra un punto en la intersección de dos conjuntos convexos mediante la proyección iterativa sobre cada uno de los conjuntos convexos; se diferencia del método de proyección alternada en que existen pasos intermedios. Gaffke y Mathar desarrollaron una versión paralela del algoritmo.

El método lleva el nombre de Richard L. Dykstra, quien lo propuso en la década de 1980.

Una diferencia clave entre el algoritmo de Dykstra y el método de proyección alternante estándar se produce cuando hay más de un punto en la intersección de los dos conjuntos. En este caso, el método de proyección alternante da un punto arbitrario en esta intersección, mientras que el algoritmo de Dykstra da un punto específico: la proyección de r sobre la intersección, donde r es el punto inicial utilizado en el algoritmo.

Algoritmo

El algoritmo de Dykstra encuentra para cada uno el único tal que: ${\displaystyle r}$ ${\displaystyle {\bar {x}}\in C\cap D}$

${\displaystyle \|{\bar {x}}-r\|^{2}\leq \|x-r\|^{2},{\text{for all }}x\in C\cap D,}$

donde son conjuntos convexos . Este problema es equivalente a hallar la proyección de sobre el conjunto , que denotamos por . ${\displaystyle C,D}$ ${\displaystyle r}$ ${\displaystyle C\cap D}$ ${\displaystyle {\mathcal {P}}_{C\cap D}}$

Para utilizar el algoritmo de Dykstra es necesario saber proyectar sobre los conjuntos y por separado. ${\displaystyle C}$ ${\displaystyle D}$

En primer lugar, considere el método básico de proyección alternada (también conocido como POCS) (estudiado por primera vez, en el caso en que los conjuntos eran subespacios lineales, por John von Neumann ^[1] ), que inicializa y luego genera la secuencia ${\displaystyle C,D}$ ${\displaystyle x_{0}=r}$

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

El algoritmo de Dykstra tiene una forma similar, pero utiliza variables auxiliares adicionales. Comienza con y actualiza con ${\displaystyle x_{0}=r,p_{0}=q_{0}=0}$

${\displaystyle y_{k}={\mathcal {P}}_{D}(x_{k}+p_{k})}$

${\displaystyle p_{k+1}=x_{k}+p_{k}-y_{k}}$

${\displaystyle x_{k+1}={\mathcal {P}}_{C}(y_{k}+q_{k})}$

${\displaystyle q_{k+1}=y_{k}+q_{k}-x_{k+1}.}$

Luego la secuencia converge a la solución del problema original. Para conocer los resultados de convergencia y una perspectiva moderna de la literatura, consulte ^{[2] .} ${\displaystyle (x_{k})}$

Citas

1. J. von Neumann, On rings of operatores. Reduction theory, Ann. of Math. 50 (1949) 401–485 (una reimpresión de notas de clase distribuidas por primera vez en 1933).
2. PL Combettes y J.-C. Pesquet, "Métodos de división proximal en el procesamiento de señales", en: Fixed-Point Algorithms for Inverse Problems in Science and Engineering, (HH Bauschke, RS Burachik , PL Combettes, V. Elser, DR Luke y H. Wolkowicz, editores), págs. 185-212. Springer, Nueva York, 2011 [1]

Referencias

• Boyle, JP; Dykstr, RL (1986). "Un método para hallar proyecciones sobre la intersección de conjuntos convexos en espacios de Hilbert". Avances en inferencia estadística con orden restringido . Apuntes de clase en estadística. Vol. 37. págs. 28–47. doi :10.1007/978-1-4613-9940-7_3. ISBN 978-0-387-96419-5.
• Gaffke, N.; Mathar, R. (1989). "Un algoritmo de proyección cíclica a través de la dualidad". Metrika . 36 : 29–54. doi :10.1007/bf02614077. S2CID  120944669.