The upper and lower bounds for individual conditional probability distributions that form the basis of our variational method are based on the ``dual'' or ``conjugate'' representations of convex functions. We present a brief description of convex duality in this appendix, and refer the reader to Rockafellar (1970) for a more extensive treatment.
Let f(x) be a real-valued, convex function defined on a convex set X (for example, ). For simplicity of exposition, we assume that f is a well-behaved (differentiable) function. Consider the graph of f, i.e., the points (x,f(x)) in an n+1 dimensional space. The fact that the function f is convex translates into convexity of the set called the epigraph of f and denoted by epi(f) (Figure 13).
Figure 13: Half-spaces containing the convex set epi(f). The conjugate function defines the critical half-spaces whose intersection is epi(f), or, equivalently, it defines the tangent planes of f(x).
It is an elementary property of convex sets that they can be represented as the intersection of all the half-spaces that contain them (see Figure 13). Through parameterizing these half-spaces we obtain the dual representations of convex functions. To this end, we define a half-space by the condition:
where and parameterize all (non-vertical) half-spaces. We are interested in characterizing the half-spaces that contain the epigraph of f. We require therefore that the points in the epigraph must satisfy the half-space condition: for , we must have . This holds whenever as the points in the epigraph have the property that . Since the condition must be satisfied by all , it follows that
as well. Equivalently,
where the right-hand side of this equation defines a function of , which is known as the ``dual'' or ``conjugate'' function . This function, which is also a convex function, defines the critical half-spaces which are needed for the representation of epi(f) as an intersection of half-spaces (Figure 13).
To clarify the duality between f(x) and , let us drop the maximum and rewrite the inequality as:
In this equation, the roles of the two functions are interchangeable and we may suspect that also f(x) can obtained from the dual function by an optimization procedure. This is in fact the case and we have:
This equality states that the dual of the dual gives back the original function. It provides the computational tool for calculating dual functions.
For concave (convex down) functions the results are analogous; we replace with , and lower bounds with upper bounds.