Journal of Convex Analysis, Vol. 6, No. 2, pp. 319-333 (1999)

Dykstra's Algorithm as the Nonlinear Extension of Bregman's Optimization Method

Lev M. Bregman and Yair Censor and Simeon Reich

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:


[Previous Article] [Next Article] [Contents of this Number]
© 1999--2000 ELibM for the EMIS Electronic Edition