ParallelEvaluate for function minimization

Question

Is there a parallelized version of a minimization routine available in Mathematica?

The objective function is non-linear and the gradients have to be numerically computed. Every function evaluation is compute-intensive and hence parallelization of numerical gradient computation will be beneficial.

Simple attempts to wrap Parallelize around FindMinimum or NMinimize says it:

cannot be parallelized; proceeding with sequential evaluation. >>

Edit : 1

Here is an toy example

objFn[coeff_, xMin_, xMax_, n_] := (
   Pause[5]; 
   Total[(Cos[#] - 
         Sum[coeff[[i]] #^(i - 1), {i, 1, Length@coeff}]) & /@ 
      Range[xMin, xMax, (xMax - xMin)/n]]^2);

NMinimize[
 N@objFn[{x1, x2, x3, x4}, \[Pi]/3, 2 \[Pi]/3, 10], {x1, x2, x3, x4}, 
 EvaluationMonitor -> Print[{x1, x2, x3, x4}]]

The Pause[5] is a placeholder for a long computation. This attempts to find a polynomial fit for the function using the coefficients list {x1,x2,x3,x4}.

Parallelize@Nminimize resorts to sequential evaluation in this case.

Edit : 2

This question is inspired from an analogous possibility in Matlab as described here and here.

Answer 1

One route to parallelism would be to consider so called MultiStart routines. MultiStart routines try to find a global minimum by launching lots of local minimisation routines where each local minimiser is given a different starting point. This will result in a set of local minima and you choose the best one as your estimate for the global minimum.

It is easy to code up a crude MultiStart routine in Mathematica by making use of the FindMinimum function. Using the objective function you provided but with a shorter Pause because life is short:

(*Define Objective function*)    
objFn[coeff_, xMin_, xMax_, n_] := (Pause[0.5];
       Total[(Cos[#] - 
             Sum[coeff[[i]] #^(i - 1), {i, 1, Length@coeff}]) & /@ 
          Range[xMin, xMax, (xMax - xMin)/n]]^2);

(*Find a local minimum given 4 start values*)
localmin[{x1Start_, x2Start_, x3Start_, x4Start_}] := 
  FindMinimum[
   N@objFn[{x1, x2, x3, x4}, \[Pi]/3, 2 \[Pi]/3, 10], {{x1, 
     x1Start}, {x2, x1Start}, {x3, x1Start}, {x4, x1Start}}];

(*Makes these results reproducible*)
SeedRandom[1]
(*Get a set of random starting values*)
startValues = RandomReal[{-1, 1}, {10, 4}];
(*Run the local minimiser sequentially and time*)
solutions = Map[localmin, startValues]; // AbsoluteTiming

{5.020638, Null}

(*We want the global minimum so pick out the best solution from the \
ones found above*)
sortedsols = Sort[solutions, #1[[1]] < #2[[1]] &]

{{0., {x1 -> 0.0253651, x2 -> 0.0184109, x3 -> 0.00615132, 
   x4 -> -0.0159673}}, {0., {x1 -> -0.147831, x2 -> -0.107301, 
   x3 -> -0.0358506, 
   x4 -> 0.0930593}}, {7.88861*10^-31, {x1 -> -0.146892, 
   x2 -> -0.10662, x3 -> -0.0356231, 
   x4 -> 0.0924686}}, {1.77494*10^-30, {x1 -> 0.108726, 
   x2 -> 0.0789175, x3 -> 0.0263673, 
   x4 -> -0.068443}}, {1.77494*10^-30, {x1 -> -0.104234, 
   x2 -> -0.0756567, x3 -> -0.0252778, 
   x4 -> 0.065615}}, {3.15544*10^-30, {x1 -> -0.140502, 
   x2 -> -0.101982, x3 -> -0.0340734, 
   x4 -> 0.0884461}}, {3.15544*10^-30, {x1 -> 0.428813, 
   x2 -> 0.311249, x3 -> 0.103992, 
   x4 -> -0.269937}}, {2.55591*10^-28, {x1 -> -0.349438, 
   x2 -> -0.253635, x3 -> -0.0847425, 
   x4 -> 0.219971}}, {1.26218*10^-27, {x1 -> 0.574574, x2 -> 0.417047,
    x3 -> 0.139341, 
   x4 -> -0.361693}}, {1.81754*10^-27, {x1 -> -0.659541, 
   x2 -> -0.478719, x3 -> -0.159946, x4 -> 0.41518}}}

(*Pull out the best solution*)
bestsol = sortedsols[[1]]

{0., {x1 -> 0.0253651, x2 -> 0.0184109, x3 -> 0.00615132, 
  x4 -> -0.0159673}}

Doing it in parallel is easy:

(*Let's do that in parallel with the same set of startValues*)
LaunchKernels[4];
parsolutions = ParallelMap[localmin, startValues]; // AbsoluteTiming

{1.006628, Null}

I get a very nice speed up on my quadcore. The best solution is, of course, the same as the sequential version

In[33]:= sortedparsols = Sort[parsolutions, #1[[1]] < #2[[1]] &];

In[34]:= bestsol = sortedparsols[[1]]

Out[34]= {0., {x1 -> 0.0253651, x2 -> 0.0184109, x3 -> 0.00615132, 
  x4 -> -0.0159673}}

This method is also used by The Mathworks in their global optimisation toolbox

http://www.mathworks.co.uk/help/gads/how-globalsearch-and-multistart-work.html