# Speeding up the non-negativity algorithm for multilinear function with interval probabilities?

The algorithm is a branch-and-bound algorithm that calculates the non-negativity of a multilinear function with interval probabilities. The lines 9-11 has an optimization that is explained on the 10-14 lines of Table 1 in publication here.

what kind of methods would you use to speed up this kind of recursive algorithm?

Algorithm

Algo[f0_, lb0_, ub0_] :=
Module[{f = f0, lb = lb0, ub = ub0, monomials, fp, fm, bvar, blb,
bub}, If[f == 0 || f == 0.0, Return[True]];
monomials = f // MonomialList;
fp = Select[monomials*1.0*D, (First[#] >= 0) &] /. {D -> 1};
fm = Select[monomials*1.0*D, (First[#] < 0) &] /. {D -> 1};
If[Plus @@ (fp /. lb) + Plus @@ (fm /. ub) >= 0, Return[True]];
If[Plus @@ (fp /. ub) + Plus @@ (fm /. lb) < 0, Return[False]];
bvar = Variables[f] // First;
blb = Select[lb, ((# // First) == bvar) &];
bub = Select[ub, ((# // First) == bvar) &];
Algo[(f /. blb), lb, ub] \[And] Algo[(f /. bub), lb, ub]];


Simple example: non-negativity check for $p_1+p_2-p_1p_2$ with bounds $p_i\in[0.01,0.04]$

Algo[Subscript[p, 1] + Subscript[p, 2] - Subscript[p, 1] Subscript[p, 2],
Table[Subscript[p, i] -> 0.01, {i, 7}], Table[Subscript[p, i] -> 0.04, {i, 7}]]

• It would help if you give some example where the function is noticably slow (perhaps a larger one than the one you gave). Apr 9 '13 at 20:49
• Any answers to this one? I cannot open bounty here because no reputation here. I shared this question to my colleques in Twitter. Oct 26 '14 at 10:10
• Between explanation and example, I still have no idea what it is this algorithm is intended to do. Oct 27 '14 at 4:02
• Voted to close your own question? Strange remark; you could have deleted it any time you wanted. Oct 27 '14 at 6:44
• Thank you for your precious comments, I added applied references (not just pure mathematical investigation) and explained the simple demo and made it simpler. You only need to understand multilinearity and non-negativity to understand the question.
– hhh
Oct 28 '14 at 2:56