Estrategias para reducir el tiempo de ejecución del algoritmo de Dykstra en ciertos casos poliedrales

MORILLAS PATRICIA MARIELA

Río Cuero, Córdoba, Argentina

Otro; LIII Reunión Anual de Comunicaciones Científicas; 2003

Unión Matemática Argentina

El algoritmo de la proyección alternante de Dykstra [4] permite encontrar en forma aproximada la proyección de un vector sobre una intersección de un número finito de conjuntos convexos cerrados. Es una técnica iterativa simple que se ha aplicado a una variada gama de problemas y resulta generalmente fácil de programar (para más detalles se puede consultar, por ejemplo, el trabajo de Deutsch [2] y el libro de Escalante y Raydán [5]). Una desventaja que tiene el algoritmo de Dykstra es la rapidez con que converge. En el caso poliedral, es decir, cuando se usa para proyectar sobre una intersección de un número finito de semiespacios cerrados, se ha podido demostrar que es lineal [1]. Esto ha motivado el interés por considerar diferentes técnicas para acelerar su convergencia. En este trabajo se estudia el algoritmo de Dykstra cuando se lo usa para proyectar sobre una intersección de semiespacios cerrados de la forma Si = { x Î IRd : nit x £ 0 } para i = 1, ..., n con nit nj > 0 para i, j = 1, ..., n. Se proponen diferentes implementaciones del mismo y se incorporan técnicas con el objetivo de reducir el tiempo de ejecución. El análisis del comportamiento de los métodos propuestos se hace en base a diferentes experimentos numéricos. Estos experimentos se realizaron tomando como vectores ni las semimétricas de corte vectorizadas [3] y usando para proyectar vectores con distintas características. Los resultados obtenidos en estos experimentos nos muestran que, efectivamente, las implementaciones y estrategias propuestas logran disminuir el tiempo de ejecución. Referencias Deutsch and Hundal H. ( 1994 ). The rate of convergence of Dykstra's cyclic projections algorithm: the polyhedral case. Numer. Funct. Anal. and Optimiz., 15: 537- 565. Deutsch F. ( 1992 ). The method of alternating orthogonal projections. In S. P. Singth, editor, Approximation Theory, Spline Functions and Applications, pages 105- 121. Kluwer Academic Publishers, Netherlands. Deza M. M., Laurent M. ( 1997 ). Geometric of Cuts and Metrics. Springer Dykstra R. L. ( 1983 ). An algorithm for restricted least-squares regression. J. Amer. Stat. Assoc., 78: 837- 842. Deutsch and Hundal H. ( 1994 ). The rate of convergence of Dykstra's cyclic projections algorithm: the polyhedral case. Numer. Funct. Anal. and Optimiz., 15: 537- 565. Deutsch F. ( 1992 ). The method of alternating orthogonal projections. In S. P. Singth, editor, Approximation Theory, Spline Functions and Applications, pages 105- 121. Kluwer Academic Publishers, Netherlands. Deza M. M., Laurent M. ( 1997 ). Geometric of Cuts and Metrics. Springer Dykstra R. L. ( 1983 ). An algorithm for restricted least-squares regression. J. Amer. Stat. Assoc., 78: 837- 842. 5. Ecalante R., Raydán M.. (2000) Alternating Projection Methods: Theory and Applications. ( Preliminary draft ).