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.

Author information

Contact details are reproduced from the original publication and may be historical.

Lev M. Bregman

Institute for Industrial Mathematics, 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

Keywords

  • Bregman projection
  • convex programming
  • Dykstra's algorithm

Mathematics Subject Classification

47N10; 49M30, 90C20

References

  1. H. H. Bauschke, J. M. Borwein: Dykstra's alternating projection algorithm for two sets, Journal of Approximation Theory 79 (1994) 418-443.https://doi.org/10.1006/jath.1994.1136Google Scholar
  2. H. H. Bauschke, J. M. Borwein: On projection algorithms for solving convex feasibility problems, SIAM Review 38 (1996) 367-426.https://doi.org/10.1137/S0036144593251710Google Scholar
  3. J. P. Boyle, R. L. Dykstra: A method for finding projections onto the intersection of convex sets in Hilbert spaces, In: Advances in Order Restricted Statistical Inference, Lecture Notes in Statistics, Springer-Verlag, Berlin, Germany, Volume 37 (1986) 28-47.https://doi.org/10.1007/978-1-4613-9940-7_3Google Scholar
  4. Y. Censor, T. Elfving: A multiprojection algorithm using Bregman projections in a product space, Numerical Algorithms 8 (1994) 221-239.https://doi.org/10.1007/BF02142692Google Scholar
  5. Y. Censor, A. N. Iusem, S. A. Zenios: An interior point method with Bregman functions for the variational inequality problem with paramonotone operators, Mathematical Programming 81 (1998) 373-400.https://doi.org/10.1007/BF01580089Google Scholar
  6. Y. Censor, A. Lent: An iterative row-action method for interval convex programming, Journal of Optimization Theory and Applications 34 (1981) 321-353.https://doi.org/10.1007/BF00934676Google Scholar
  7. Y. Censor, S. Reich: Iterations of paracontractions and firmly nonexpansive operators with applications to feasibility and optimization, Optimization 37 (1996) 323-339.https://doi.org/10.1080/02331939608844225Google Scholar
  8. Y. Censor, S. Reich: The Dykstra algorithm with Bregman projections, Communications in Applied Analysis 2 (1998) 407-419.Google Scholar
  9. Y. Censor, S. A. Zenios: Proximal minimization algorithm with D-functions, Journal of Optimization Theory and Applications 73 (1992) 451-464.https://doi.org/10.1007/BF00940051Google Scholar
  10. Y. Censor, S. A. Zenios: Parallel Optimization: Theory, Algorithms and Applications, Oxford University Press, New York, 1997.Google Scholar
  11. P. L. Combettes: The foundations of set theoretic estimation, Proceedings of the IEEE 81 (1993) 182-208.https://doi.org/10.1109/5.214546Google Scholar
  12. P. L. Combettes: The convex feasibility problem in image recovery, Advances in Imaging and Electron Physics 95 (1996) 155-270.https://doi.org/10.1016/S1076-5670(08)70157-5Google Scholar
  13. G. Crombez: Finding projections onto the intersection of convex sets in Hilbert spaces, Numerical Functional Analysis and Optimization 16 (1995) 637-652.https://doi.org/10.1080/01630569508816636Google Scholar
  14. I. Csiszár: Why least squares and maximum entropy? An axiomatic approach to inference for linear inverse problems, The Annals of Statistics 19 (1991) 2032-2066.https://doi.org/10.1214/aos/1176348385Google Scholar
  15. G. B. Dantzig: Linear Programming and Extensions, Princeton University Press, Princeton, NJ, USA, 1963.https://doi.org/10.1515/9781400884179Google Scholar
  16. A. R. De Pierro, A. N. Iusem: A relaxed version of Bregman's method for convex programming, Journal of Optimization Theory and Applications 51 (1986) 421-440.https://doi.org/10.1007/BF00940283Google Scholar
  17. D. A. D'Esopo: A convex programming procedure, Naval Research Logistics Quarterly 6 (1959) 33-42.https://doi.org/10.1002/nav.3800060105Google Scholar
  18. F. Deutsch, H. Hundal: The rate of convergence of Dykstra's cyclic projections algorithm: The polyhedral case, Numerical Functional Analysis and Optimization 15 (1994) 537-565.https://doi.org/10.1080/01630569408816580Google Scholar
  19. R. L. Dykstra: An algorithm for restricted least squares regression, Journal of the American Statistical Association 78 (1983) 837-842.https://doi.org/10.1080/01621459.1983.10477029Google Scholar
  20. J. Eckstein: Nonlinear proximal point algorithms using Bregman functions with applications to convex programming, Mathematics of Operations Research 18 (1993) 202-226.https://doi.org/10.1287/moor.18.1.202Google Scholar
  21. R. Escalante, M. Raydan: Dykstra's algorithm for a constrained least-squares matrix problem, Numerical Linear Algebra with Applications 3 (1996) 459-471.https://doi.org/10.1002/(SICI)1099-1506(199611/12)3:6<459::AID-NLA82>3.0.CO;2-SGoogle Scholar
  22. N. Gaffke, R. Mathar: A cyclic projection algorithm via duality, Metrika 36 (1989) 29-54.https://doi.org/10.1007/BF02614077Google Scholar
  23. S. -P. Han: A successive projection method, Mathematical Programming 40 (1988) 1-14.https://doi.org/10.1007/BF01580719Google Scholar
  24. H. Hundal, F. Deutsch: Two generalizations of Dykstra's cyclic projection algorithm, Mathematical Programming 77 (1997) 335-355.https://doi.org/10.1007/BF02614621Google Scholar
  25. S. -P. Han, G. Lou: A parallel algorithm for a class of convex programs, SIAM Journal on Control and Optimization 26 (1988) 345-355.https://doi.org/10.1137/0326019Google Scholar
  26. G. T. Herman, A Lent: A family of iterative quadratic optimization algorithms for pairs of inequalities with application in diagnostic radiology, Mathematical Programming Study 9 (1978) 15-29.https://doi.org/10.1007/BFb0120823Google Scholar
  27. C. Hildreth: A quadratic programming procedure, Naval Research Logistics Quarterly 4 (1957) 79-85. Erratum, ibid., p. 361.https://doi.org/10.1002/nav.3800040113Google Scholar
  28. A. N. Iusem: On dual convergence and the rate of primal convergence of Bregman's convex programming method, SIAM Journal on Optimization 1 (1991) 401-423.https://doi.org/10.1137/0801025Google Scholar
  29. A. N. Iusem, A. R. De Pierro: On the convergence of Han's method for convex programming with quadratic objective, Mathematical Programming 52 (1991) 265-284.https://doi.org/10.1007/BF01582891Google Scholar
  30. A. N. Iusem, S. A. Zenios: Interval underrelaxed Bregman's method with an application, Optimization 35 (1995) 227-250.https://doi.org/10.1080/02331939508844144Google Scholar
  31. K. C. Kiwiel: Free-steering relaxation methods for problems with strictly convex sets and linear constraints, Mathematics of Operations Research 22 (1997) 326-349.https://doi.org/10.1287/moor.22.2.326Google Scholar
  32. K. C. Kiwiel: Proximal minimization methods with generalized Bregman functions, SIAM Journal on Control and Optimization 35 (1997) 1142-1168.https://doi.org/10.1137/S0363012995281742Google Scholar
  33. A. Lent, Y. Censor: Extensions of Hildreth's row-action method for quadratic programming, SIAM Journal on Control and Optimization 18 (1980) 444-454.https://doi.org/10.1137/0318033Google Scholar
  34. A. L. Peressini, F. E. Sullivan, J. J. Uhl jun.: The Mathematics of Nonlinear Programming, Springer-Verlag, New York etc., 1988.https://doi.org/10.1007/978-1-4612-1025-2Google Scholar
  35. T. Robertson, F. T. Wright, R. L. Dykstra: Order Restricted Statistical Inference, John Wiley & Sons, Chichester, UK, 1988.Google Scholar
  36. R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, NJ, USA, 1970.Google Scholar
  37. M. Teboulle: Entropic proximal mappings with applications to nonlinear programming, Mathematics of Operations Research 17 (1992) 670-690.https://doi.org/10.1287/moor.17.3.670Google Scholar
  38. P. Tseng: Dual coordinate ascent methods for non-strictly convex minimization, Mathematical Programming 59 (1993) 231-247.https://doi.org/10.1007/BF01581245Google Scholar

Suggested citation

L. M. Bregman, Y. Censor, S. Reich. “Dykstra's Algorithm as the Nonlinear Extension of Bregman's Optimization Method.” Journal of Convex Analysis 6 (1999), No. 2, 319–333. https://doi.org/10.68381/jca06018

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1999. Rights now held by Banach Press.