Namespaces
Variants
Actions

Bregman function

From Encyclopedia of Mathematics
Revision as of 17:18, 7 February 2011 by 127.0.0.1 (talk) (Importing text file)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Let be a closed convex subset of and its interior. Consider a real-valued convex function (cf. also convex function (of a real variable)) whose effective domain contains and let be defined as

is said to be a Bregman function with zone (and the Bregman distance induced by ) if the following conditions hold:

B1) is continuously differentiable on ;

B2) is strictly convex and continuous on ;

B3) for all the partial level sets are bounded for all ;

B4) if converges to , then converges to ;

B5) if and are sequences such that is bounded, and , then .

Bregman functions were introduced in [a1]. B4) and B5) hold automatically when are in , as a consequence of B1), B2) and B3), and so they need to be checked only at points on the boundary of . When , a sufficient condition for a strictly convex differentiable function to be a Bregman function is

(see [a2]).

A Bregman function is said to be boundary coercive if for all such that one has for all , and zone coercive if the image of under is equal to . Zone coerciveness implies boundary coerciveness (see [a3]). These notions are closely related to essential smoothness, as defined in [a5]. For a boundary-coercive Bregman function the zone is uniquely determined from , i.e. cannot be finitely extended outside . This property is essential in most applications of Bregman functions.

Examples.

denotes the non-negative orthant of .

i) , . In this case . More generally, , with symmetric and positive definite, in which case .

ii) , , extended by continuity to with the convention that . In this case

which is the Kullback–Leibler information divergence, widely used in statistics (see Kullback–Leibler-type distance measures; [a4]).

iii) , with , . For , one has

and for , one has

iv) is a box (i.e., with , ),

In this case

v) is a polyhedron with non-empty interior (i.e., with , and (so that )), , where () are the rows of . In this case

All the Bregman functions in the above examples are zone coercive, except for iii) with , which is only boundary coercive.

Bregman functions are used in algorithms for convex feasibility problems and linearly constrained convex optimization (cf. Bregman distance), as well as for generalizations of the proximal point method for convex optimization (cf. Proximal point methods in mathematical programming).

References

[a1] L.M. Bregman, "The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming" USSR Comput. Math. Math. Phys. , 7 : 3 (1967) pp. 200–217 (In Russian)
[a2] A.R. de Pierro, A.N. Iusem, "A relaxed version of Bregman's method for convex programming" J. Optimization Th. Appl. , 51 (1986) pp. 421–440
[a3] A.N. Iusem, "On some properties of generalized proximal point methods for quadratic and linear programming" J. Optimization Th. Appl. , 85 (1995) pp. 593–612
[a4] F. Liese, I. Vajda, "Convex statistical distances" , Teubner (1987)
[a5] R.T. Rockafellar, "Convex analysis" , Princeton Univ. Press (1970)
How to Cite This Entry:
Bregman function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bregman_function&oldid=16823
This article was adapted from an original article by A.N. Iusem (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article