Abstract

The convex feasibility problem, that is, finding a point in the intersection of finitely many closed convex sets in Euclidean space, arises in various areas of mathematics and physical sciences. It can be solved by the classical method of cyclic orthogonal projections, where, by projecting cyclically onto the sets, a sequence is generated that converges to a point in the intersection. In 1967, Bregman extended this method to non-orthogonal projections based on a new notion of distance, nowadays called “Bregman distance”. The Bregman distance is induced by a convex function. If this function is a so-called “zone consistent Bregman function”, then Bregman’s method works; however, deciding on this can be difficult. In this paper, Bregman’s method is studied within the powerful framework of Convex Analysis. New insights are obtained and the rich class of “Bregman/Legendre functions” is introduced. Bregman’s method still works, if the underlying function is Bregman/Legendre or more generally if it is Legendre but some constraint qualification holds additionally. The key advantage is the broad applicability and verifiability of these concepts. The results presented here are complementary to recent work by Censor and Reich on the method of random Bregman projections (where the sets are projected onto infinitely often – not necessarily cyclically). Special attention is given to examples, some of which connect to Pythagorean means and to Convex Analysis on the Hermitian or symmetric matrices.

Author information

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

Heinz H. Bauschke

Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario N2L 3G1, Canada.

Jonathan M. Borwein

Centre for Experimental & Constructive Mathematics, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6.

Keywords

  • Bregman function
  • Bregman projection
  • convex feasibility problem
  • convex function
  • convex set
  • essentially smooth function
  • essentially strictly convex function
  • Hermitian matrix
  • Legendre function
  • projection

References

  1. Y. Alber and D. Butnariu: Convergence of Bregman-projection methods for solving consistent convex feasibility problems in reflexive Banach spaces. Journal of Optimization Theory and Applications (1994) Accepted for Publication.Google Scholar
  2. H.H. Bauschke: A norm convergence result on random products of relaxed projections in Hilbert space. Transactions of the American Mathematical Society, 347(4) (1995) 1365–1374.https://doi.org/10.1090/S0002-9947-1995-1257097-1Google Scholar
  3. H.H. Bauschke and J.M. Borwein: On projection algorithms for solving convex feasibility problems. SIAM Review 38(3) (1996) 367–426.https://doi.org/10.1137/S0036144593251710Google Scholar
  4. L.M. Bregman: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. U.S.S.R. Computational Mathematics and Mathematical Physics 7(3) (1967) 200–217.https://doi.org/10.1016/0041-5553(67)90040-7Google Scholar
  5. R.S. Burachik: Generalized Proximal Point Methods of the Variational Inequality Problem. PhD thesis, Rio de Janeiro, 1995.Google Scholar
  6. Y. Censor and 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
  7. Y. Censor and A. Lent: An iterative row-action method for interval convex programming. Journal of Optimization Theory and Applications 34(3) (1981) 321–353.https://doi.org/10.1007/BF00934676Google Scholar
  8. Y. Censor and A. Lent: Optimization of “log x” entropy over linear equality constraints. SIAM Journal on Control and Optimization 25(4) (1987) 921–933.https://doi.org/10.1137/0325050Google Scholar
  9. Y. Censor, A.R. de Pierro, T. Elfving, G.T. Herman, and A.N. Iusem: On iterative methods for linearly constrained entropy maximization. In A. Wakulicz, editor, Numerical Analysis and Mathematical Modelling, pages 145–163, Warsaw, 1990. Polish Scientific Publishers. Banach Center Publications Volume 24.https://doi.org/10.4064/-24-1-145-163Google Scholar
  10. Y. Censor, A.R. de Pierro, and A.N. Iusem: On maximization of entropies and a generalization of Bregman’s method for convex programming. Technical Report MIPG 113, Medical Image Processing Group, Department of Radiology, University of Pennsylvania, Philadelphia, U.S.A., 1986.Google Scholar
  11. Y. Censor, A.R. de Pierro, and A.N. Iusem: Optimization of Burg’s entropy over linear constraints. Applied Numerical Mathematics 7 (1991) 151–165.https://doi.org/10.1016/0168-9274(91)90059-9Google Scholar
  12. Y. Censor and S. Reich: Iterations of paracontractions and firmly nonexpansive operators with applications to feasibility and optimization. Optimization 37(4) (1996) 323–339.https://doi.org/10.1080/02331939608844225Google Scholar
  13. G. Chen and M. Teboulle: Convergence analysis of a proximal-like minimization algorithm using Bregman functions. SIAM Journal on Optimization 3(3) (1993) 538–543.https://doi.org/10.1137/0803026Google Scholar
  14. J. Eckstein: Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Mathematics of Operations Research 18(1) (1993) 202–226.https://doi.org/10.1287/moor.18.1.202Google Scholar
  15. L. Elsner, I. Koltracht, and M. Neumann: Convergence of sequential and asynchronous nonlinear paracontractions. Numerische Mathematik 62 (1992) 305–319.https://doi.org/10.1007/BF01396232Google Scholar
  16. S.D. Flåm and J. Zowe: Relaxed outer projections, weighted averages and convex feasibility. BIT 30 (1990) 289–300.https://doi.org/10.1007/BF02017349Google Scholar
  17. J.-B. Hiriart-Urruty and C. Lemaréchal: Convex Analysis and Minimization Algorithms II, volume 306 of Grundlehren der mathematischen Wissenschaften. Springer-Verlag, 1993.https://doi.org/10.1007/978-3-662-02796-7Google Scholar
  18. A.N. Iusem, 1994: Personal communication.Google Scholar
  19. A.N. Iusem: Proximal point methods in optimization, May 1994. Unpublished manuscript.Google Scholar
  20. K.C. Kiwiel: conference talk in Ann Arbor, Michigan, August 1994.Google Scholar
  21. K.C. Kiwiel: Free-steering relaxation methods for problems with strictly convex costs and linear constraints. WP-94-89, International Institute for Applied Systems Analysis, Laxenburg, Austria, September 1994. Revised July 1995.Google Scholar
  22. A.S. Lewis: Convex analysis on the Hermitian matrices. SIAM Journal on Optimization 6(1) (1996) 164–177.https://doi.org/10.1137/0806009Google Scholar
  23. A.S. Lewis, 1994: Personal communication.Google Scholar
  24. A.S. Lewis: The convex analysis of unitarily invariant matrix norms. Journal of Convex Analysis 2 (1995) 173–183.https://doi.org/10.68381/jca02012Google Scholar
  25. A.S. Lewis: Derivatives of spectral functions. Mathematics of Operations Research 21(3) (1996) 576–588.https://doi.org/10.1287/moor.21.3.576Google Scholar
  26. A.S. Lewis: Group invariance and convex matrix analysis. SIAM Journal on Matrix Analysis 17(4) (1996) 927–949.https://doi.org/10.1137/S0895479895283173Google Scholar
  27. A.W. Marshall and I. Olkin: Inequalities: Theory of Majorization and Its Applications, volume 143 of Mathematics in Science and Engineering. Academic Press, New York, 1979.Google Scholar
  28. G. Pierra: Decomposition through formalization in a product space. Mathematical Programming 28 (1984) 96–115.https://doi.org/10.1007/BF02612715Google Scholar
  29. A.R. de Pierro and A.N. Iusem: A relaxed version of Bregman’s method for convex programming. Journal of Optimization Theory and Applications 51(3) (1986) 421–440.https://doi.org/10.1007/BF00940283Google Scholar
  30. R.T. Rockafellar: Convex Analysis. Princeton University Press, Princeton, NJ, 1970.Google Scholar
  31. M. Teboulle: Entropic proximal mappings with applications to nonlinear programming. Mathematics of Operations Research 17(3) (1992) 670–690.https://doi.org/10.1287/moor.17.3.670Google Scholar
  32. P. Tseng: On the convergence of the products of firmly nonexpansive mappings. SIAM Journal on Optimization 2(3) (1992) 425–434.https://doi.org/10.1137/0802021Google Scholar

Suggested citation

H. H. Bauschke, J. M. Borwein. “Legendre Functions and the Method of Random Bregman Projections.” Journal of Convex Analysis 4 (1997), No. 1, 27–67. https://doi.org/10.68381/jca04002

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 1997. Rights now held by Banach Press LLC.