Algoritmo de proyección de Dykstra

El algoritmo de Dykstra es un método para calcular 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 proyectando iterativamente sobre cada uno de ellos; se diferencia del método de proyección alternada en que incluye pasos intermedios. Gaffke y Mathar desarrollaron una versión paralela del algoritmo.

El método recibe su 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 alternada estándar surge cuando hay más de un punto en la intersección de los dos conjuntos. En este caso, el método de proyección alternada proporciona un punto arbitrario en dicha intersección, mientras que el algoritmo de Dykstra proporciona un punto específico: la proyección de r sobre la intersección, donde r es el punto inicial utilizado en el algoritmo.

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

${\displaystyle \|{\bar {x}}-r\|^{2}\leq \|xr\|^{2},{\text{para todo }}x\in C\cap D,}$

dónde${\displaystyle C,D}$son conjuntos convexos . Este problema es equivalente a encontrar la proyección de${\displaystyle r}$en el plató${\displaystyle C\cap D}$, que denotamos por${\displaystyle {\mathcal {P}}_{C\cap D}}$.

Para utilizar el algoritmo de Dykstra, hay que saber cómo proyectar sobre los conjuntos.${\displaystyle C}$y${\displaystyle D}$por separado.

Primero, consideremos 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${\displaystyle C,D}$eran subespacios lineales, por John von Neumann ^{[ 1 ]} ), que inicializa${\displaystyle x_{0}=r}$y luego genera la secuencia

${\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. Comience con${\displaystyle x_{0}=r,p_{0}=q_{0}=0}$y actualización por

${\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${\displaystyle (x_{k})}$converge a la solución del problema original. Para resultados de convergencia y una perspectiva moderna de la literatura, véase ^{[ 2 ] .}

• Boyle, JP; Dykstr, RL (1986). «Un método para encontrar proyecciones sobre la intersección de conjuntos convexos en espacios de Hilbert». Avances en inferencia estadística con restricciones de orden . Notas 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 mediante dualidad". Metrika . 36 : 29–54 . doi : 10.1007/bf02614077 . S2CID 120944669 .