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.

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.

share|improve this question
2  
This kind of questions are too generic and shows little effort from your side. At least some toy example with code will help others to consider helping you right away. It can be a good question if you put some more relevant details and highlight what you have tried. –  PlatoManiac Sep 16 '13 at 11:54
    
Minimization involves recursion-based algorithms. Parallelizing them might be challenging (I'm no IT expert though). –  Gregory Rut Sep 16 '13 at 12:32
    
@PlatoManiac : Have included an example. Also included the source (Matlab's possibility) which inspired this question. –  my account_ram Sep 18 '13 at 9:46
    
@myaccount_ram Good that you came up with some code as a result your question is much concrete now. But I personally think in Mathematica all optimization routines are serial in nature by their design. It will be not at all easy if not completely impossible to adapt some of the gradient algorithms to use parallel function evaluation on multi-core architectures while building the run-time gradients or the Jacobians..We need some expert comment here! I am not one of them :( –  PlatoManiac Sep 19 '13 at 8:55

1 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

share|improve this answer
    
WOW! a good compilation of resources. & a nice blog u have there! –  my account_ram Sep 24 '13 at 22:19
    
Thanks. I'll be blogging about this solution soon too :) –  WalkingRandomly Sep 25 '13 at 8:22

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.