Institute for Industrial Mathematics, 4 Yehuda Hanakhtom Street, 84311 Beer-Sheva, Israel, bregman@math.bgu.ac.il and Department of Mathematics, University of Haifa, Mt. Carmel, 31905 Haifa, Israel, yair@mathcs2.haifa.ac.il and Department of Mathematics, The Technion - Israel Institute of Technology, Technion City, 32000 Haifa, Israel, sreich@techunix.technion.ac.il
Abstract: 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
Classification (MSC2000): 47N10, 49M30, 90C25
Full text of the article: