Journal of Convex Analysis 06 (1999), No. 2, 319--334
Copyright Heldermann Verlag 1999
Dykstra's Algorithm as the Nonlinear Extension of Bregman's Optimization Method
Lev M. Bregman
Inst. for Industrial Mathematics, Ben-Gurion-University, 4 Yehuda Hanakhtom Street, 84311 Beer-Sheva, Israel
Yair Censor
Dept. of Mathematics, University of Haifa, Mount Carmel, 31905 Haifa, Israel
Simeon Reich
Dept. of Mathematics, Technion - Israel Inst. of Technology, Technion City, 32000 Haifa, Israel
We show that Dykstra's algorithm with Bregman projections, which finds the Bregman projection of a point onto the nonempty intersection of finitely many closed convex sets, is actually the nonlinear extension of Bregman's primal-dual, dual coordinate ascent, row-action minimization algorithm. Based on this observation we give an alternative convergence analysis and a new geometric interpretation of Dykstra's algorithm with Bregman projections which complements recent work of Censor and Reich, Bauschke and Lewis, and Tseng.
Keywords: Bregman projection, convex programming, Dykstra's algorithm.
MSC: 47N10; 49M30, 90C20.
[ Fulltext-pdf (221 KB)]