LAVINE'S BRACKETING ALGORITHM

 

The previous numerical approaches produced algorithms that converge to optimizers of the posterior distribution, without guarantees about global optimality. In this subsection we sketch an approach to obtain convergence to the global minimum of the posterior distribution. Empirical tests are due to study the practical applicability of this approach.

Lavine's bracketing algorithm is a method to obtain the posterior quantity p(x_q = a) = min( p(x_q = a, e)/p(e) ). The idea is to settle for deciding whether or not p(x_q = a) is larger than a given value k. When we obtain this result, we can construct an algorithm by bracketing the interval [0,1] with k. This algorithm is convergent and improves monotonically.

Notice that p(x_q = a) = min( p(x_q = a, e)/p(e) ) is larger than k if and only if min( p(x_q = a, e) - k p(e) ) is larger than zero. The point of Lavine's algorithm is that minimization of the latter quantity may be simpler than minimization of the former, since there are no ratios involved. This is in fact true for type-1 combinations in Quasi-Bayesian networks. Consider the expression that must be minimized:

sum_{x is in (xq, e)} prod_i p_i^e - k sum_{x is in e} prod_i p_i^e.

This expression is a summation of polynomial terms with arbitrary coefficients subject to linear constraints. This type of problem is termed a signomial program, for which there are algorithms that can determine the global minimum [2]. The combination of Lavine's algorithm and signomial programming leads to an algorithm that surely converges to the correct lower bound of the posterior distribution.