Algoritmo de Dykstra

Abstract

Consideremos dos rectas r1 y r2 del plano que se cortan en el punto P. Si partiendo de un punto P0 formamos la sucesión de puntos que se obtiene proyectando ortogonalmente de forma alternada sobre las rectas r1 y r2 los puntos que se van obteniendo se recae en una sucesión que converge al punto P. El algoritmo de Dykstra es la generalización de este resultado cuando r1 y r2 se reemplazan por dos conjuntos convexos y cerrados K1 y K2 de un espacio de Hilbert, con intersección no vacía K, y a partir de un punto P0 se construye la aproximación óptima a P0 en K = K1 \ K2 resolviendo sucesivamente y de forma alternada problemas de aproximación óptima en K1 y K2. En muchas situaciones prácticas la computación de estas aproximaciones óptimas son relativamente fáciles de obtener: por ejemplo, cuando los Ki son semiespacios, hiperplanos, subespacios de dimensión finita (algoritmo de Von Neumann) o algunas clases de conos. El trabajo tiene como objetivo presentar el análisis de este algoritmo e ilustrar su convergencia en algún problema de aproximación óptima relevante.