Bregman function
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) |
Bregman function. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Bregman_function&oldid=16823