optimization, reduction variables, and MATLAB parfor

Question

I'm trying to write a simple generic parallel code for minimizing a function in MATLAB. The idea is very simple, essentially:

parfor k = 1:N
    (...find a good solution xcurrent with cost fcurrent ... )
    % keep best current value
    fmin = min(fmin,fxcurrent)
end

This works fine, because fmin is a reduction variable, and thus I can use this construction to update the current best value.

However, I couldn't find a nice elegant way of keeping (or storing) the best current solution ("xcurrent").

How do I keep track of the best solution found so far?

In other words, if the current value is strictly smaller than fmin, how can I save xcurrent (subject to the constraints that parallel loops impose in MATLAB)?

[Of course, the serial version is trivial, just prepend

if fxcurrent < fmin;
xbest = xcurrent;
end;

but this does not work on a parfor loop.]

A few approaches that come to mind:

I could just store all solutions and costs (using sliced variables), but this is hugely memory inefficient (the number of iterations N is very large, and the solutions themselves are very big).
Similarly, I could use a (set or matrix) reduction variable and do:
```
solutionset = [solutionset,xcurrent]
```

but this is almost as bad in terms of memory requirement.

I could also save xcurrent to disk every time the solution is improved.

I tried to look around for a simpler solution, but nothing was very useful.

The question seems to be well-defined (so it's not like in other problems, where the output could depend on iteration order), but I couldn't find an elegant way of doing this.

Apologies in advance if I'm missing something obvious, and thanks a lot in advance!

It depends on what you understand by "keeping track". Do you just want a display of some kind, just the current value - or do you require the whole development? Please clarify. — bdecaf
Thanks. I just want to save it, or store it for later use. I'll edit the original post to clarify. — user1245359
At first I'd suggest to keep all the xcurrent and afterwards do the search for minimum. But you wrote something about memory - is N so large? — bdecaf
Yes, N is really large. This is a combinatorial optimization problem, and I cannot afford to store all the "xcurrent" that are being generated. — user1245359
Just an idea- what if you write your own reduction function - basically just containing the if block and a save or output? — bdecaf

bdecaf bdecaf · Accepted Answer · 2012-03-03T07:24:21

Thanks so I copy the suggestion down here.

Just an idea- what if you write your own reduction function - basically just containing the if block and a save or output?

optimization, reduction variables, and MATLAB parfor

2 Answers