Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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}]]
share|improve this question
2  
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. –  Masi Oct 26 at 10:10
2  
Between explanation and example, I still have no idea what it is this algorithm is intended to do. –  Daniel Lichtblau Oct 27 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 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 at 2:56

1 Answer 1

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.

enter image description here

You can find more about the research here, not hard stuff or let say you need to be very careful :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.