# ParallelEvaluate for function minimization

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;
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 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.

• 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

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
(*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[] < #2[] &]

{{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[]

{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;
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:= sortedparsols = Sort[parsolutions, #1[] < #2[] &];

In:= bestsol = sortedparsols[]

Out= {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

• 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.63134164,"math_prob":0.96313715,"size":3003,"snap":"2021-04-2021-17","text_gpt3_token_len":1134,"char_repetition_ratio":0.16305435,"word_repetition_ratio":0.056818184,"special_character_ratio":0.5221445,"punctuation_ratio":0.26785713,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.96881086,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-13T13:35:03Z\",\"WARC-Record-ID\":\"<urn:uuid:bde4a7ce-a8cf-489d-86ee-d2647803bb12>\",\"Content-Length\":\"177525\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:1298d230-cd78-4b8d-b9e2-abec387f9209>\",\"WARC-Concurrent-To\":\"<urn:uuid:636f4924-91f9-4b4e-ab5a-68329befd76d>\",\"WARC-IP-Address\":\"151.101.129.69\",\"WARC-Target-URI\":\"https://mathematica.stackexchange.com/questions/32438/parallelevaluate-for-function-minimization\",\"WARC-Payload-Digest\":\"sha1:HRDHZGIZP3WOGPEYA56XYZK7YWNZE3RZ\",\"WARC-Block-Digest\":\"sha1:6TKYYCL76MB3RULHJPPWFU6VEAW2RB5W\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618038072366.31_warc_CC-MAIN-20210413122252-20210413152252-00148.warc.gz\"}"}