Legendre functions and the method of random Bregman projections

Bauschke, Heinz H. and Borwein, Jonathan M. (1997) Legendre functions and the method of random Bregman projections. Journal of Convex Analysis, 4 (1). pp. 27-67. ISSN 0944-6532

Download (520Kb) | Preview
    Download (400Kb) | Preview


      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, now days 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.

      Item Type: Article
      Additional Information: pubdom FALSE
      Uncontrolled Keywords: Bregman function, Bregman projection, convex feasibility problem, convex function, convex set, essentially smooth function, essentially strictly convex function, Hermitian matrix, Legendre function, projection
      Subjects: 49-xx Calculus of variations and optimal control; optimization > 49Mxx Methods of successive approximations
      65-xx Numerical analysis > 65Kxx Mathematical programming, optimization and variational techniques
      52-xx Convex and discrete geometry > 52Axx General convexity
      65-xx Numerical analysis > 65Fxx Numerical linear algebra
      90-xx Economics, operations research, programming, games > 90Cxx Mathematical programming
      47-xx Operator theory > 47Hxx Nonlinear operators and their properties
      Faculty: UNSPECIFIED
      Depositing User: Users 1 not found.
      Date Deposited: 17 Nov 2003
      Last Modified: 13 Sep 2014 21:29

      Actions (login required)

      View Item