# 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). – Leonid Shifrin 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. – Léo Léopold Hertz 준영 Oct 26 '14 at 10:10
• Between explanation and example, I still have no idea what it is this algorithm is intended to do. – Daniel Lichtblau Oct 27 '14 at 4:02
• Voted to close your own question? Strange remark; you could have deleted it any time you wanted. – Sjoerd C. de Vries 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

I wrote my thesis "Implementation of an algorithm for verifying the non-negativity of a multilinear function in a hypercube" about this here (password is "sal" and username "sal"). The key algorithm is not specified in the publication, focusing only on the key implementation idea with the hypercubes -- this was a requirement by my instructor.

Shortly

I showed that the nature of data (nature of the multilinear function) is an important decision variable in choosing the optimization! This is a fascinating concept -- it basically mean: you need to specify your multilinear function more specifically: whatever method you choose it needs to be specific, I like graph-theoretical/polytopical way of characterising the multilinear functions because then you are simply considering polytopical problems. You transform the earlier messy multilinear problem into a new domain where you can use their tools making it easy to deal with.

Optimization on the Lines 9-11

This optimization strategy (invented by my instructor) is not optimal with all kind of data. I showed this in my thesis by finding cases where they did not work, multilinear functions in Table 4 on the page 20. The way I found the multilinear functions is not specified and is an intriguing research topic because MLFs have many applications over different industries. You can find more about the research here, not hard stuff or let say you need to be very careful :)