• documentation
main content

minimizing an expensive optimization problem using parallel computing toolbox -凯发k8网页登录

this example uses:

this example shows how to speed up the minimization of an expensive optimization problem using functions in optimization toolbox™ and global optimization toolbox. in the first part of the example we solve the optimization problem by evaluating functions in a serial fashion, and in the second part of the example we solve the same problem using the parallel for loop (parfor) feature by evaluating functions in parallel. we compare the time taken by the optimization function in both cases.

expensive optimization problem

for the purpose of this example, we solve a problem in four variables, where the objective and constraint functions are made artificially expensive by pausing.

function f = expensive_objfun(x)
%expensive_objfun an expensive objective function used in optimparfor example.
%   凯发官网入口首页 copyright 2007-2013 the mathworks, inc.
% simulate an expensive function by pausing
pause(0.1)
% evaluate objective function
f = exp(x(1)) * (4*x(3)^2   2*x(4)^2   4*x(1)*x(2)   2*x(2)   1);

function [c,ceq] = expensive_confun(x)
%expensive_confun an expensive constraint function used in optimparfor example.
%   凯发官网入口首页 copyright 2007-2013 the mathworks, inc.
% simulate an expensive function by pausing
pause(0.1);
% evaluate constraints
c = [1.5   x(1)*x(2)*x(3) - x(1) - x(2) - x(4); 
     -x(1)*x(2)   x(4) - 10];
% no nonlinear equality constraints:
ceq = [];

minimizing using fmincon

we are interested in measuring the time taken by fmincon in serial so that we can compare it to the parallel time.

startpoint = [-1 1 1 -1];
options = optimoptions('fmincon','display','iter','algorithm','interior-point');
starttime = tic;
xsol = fmincon(@expensive_objfun,startpoint,[],[],[],[],[],[],@expensive_confun,options);
time_fmincon_sequential = toc(starttime);
fprintf('serial fmincon optimization takes %g seconds.\n',time_fmincon_sequential);

                                            first-order      norm of
 iter f-count            f(x)  feasibility   optimality         step
    0       5    1.839397e 00    1.500e 00    3.211e 00
    1      11   -9.760099e-01    3.708e 00    7.902e-01    2.362e 00
    2      16   -1.480976e 00    0.000e 00    8.344e-01    1.069e 00
    3      21   -2.601599e 00    0.000e 00    8.390e-01    1.218e 00
    4      29   -2.823630e 00    0.000e 00    2.598e 00    1.118e 00
    5      34   -3.905338e 00    0.000e 00    1.210e 00    7.302e-01
    6      39   -6.212992e 00    3.934e-01    7.372e-01    2.405e 00
    7      44   -5.948761e 00    0.000e 00    1.784e 00    1.905e 00
    8      49   -6.940062e 00    1.233e-02    7.668e-01    7.553e-01
    9      54   -6.973887e 00    0.000e 00    2.549e-01    3.920e-01
   10      59   -7.142993e 00    0.000e 00    1.903e-01    4.735e-01
   11      64   -7.155325e 00    0.000e 00    1.365e-01    2.626e-01
   12      69   -7.179122e 00    0.000e 00    6.336e-02    9.115e-02
   13      74   -7.180116e 00    0.000e 00    1.069e-03    4.670e-02
   14      79   -7.180409e 00    0.000e 00    7.797e-04    2.815e-03
   15      84   -7.180410e 00    0.000e 00    6.368e-06    3.120e-04
local minimum found that satisfies the constraints.
optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
serial fmincon optimization takes 18.2876 seconds.

minimizing using genetic algorithm

since ga usually takes many more function evaluations than fmincon, we remove the expensive constraint from this problem and perform unconstrained optimization instead. pass empty matrices [] for constraints. in addition, we limit the maximum number of generations to 15 for ga so that ga can terminate in a reasonable amount of time. we are interested in measuring the time taken by ga so that we can compare it to the parallel ga evaluation. note that running ga requires global optimization toolbox.

rng default % for reproducibility
try
    gaavailable = false;
    nvar = 4;
    gaoptions = optimoptions('ga','maxgenerations',15,'display','iter');
    starttime = tic;
    gasol = ga(@expensive_objfun,nvar,[],[],[],[],[],[],[],gaoptions);
    time_ga_sequential = toc(starttime);
    fprintf('serial ga optimization takes %g seconds.\n',time_ga_sequential);
    gaavailable = true;
catch me
    warning(message('optim:optimdemos:optimparfor:ganotfound'));
end

single objective optimization:
4 variable(s)
options:
creationfcn:       @gacreationuniform
crossoverfcn:      @crossoverscattered
selectionfcn:      @selectionstochunif
mutationfcn:       @mutationgaussian
                                  best           mean      stall
generation      func-count        f(x)           f(x)    generations
    1              100      -5.546e 05       1.483e 15        0
    2              147      -5.581e 17      -1.116e 16        0
    3              194      -7.556e 17       6.679e 22        0
    4              241      -7.556e 17      -7.195e 16        1
    5              288      -9.381e 27      -1.876e 26        0
    6              335      -9.673e 27      -7.497e 26        0
    7              382      -4.511e 36      -9.403e 34        0
    8              429      -5.111e 36      -3.011e 35        0
    9              476      -7.671e 36       9.346e 37        0
   10              523       -1.52e 43      -3.113e 41        0
   11              570      -2.273e 45       -4.67e 43        0
   12              617      -2.589e 47      -6.281e 45        0
   13              664      -2.589e 47      -1.015e 46        1
   14              711      -8.149e 47      -5.855e 46        0
   15              758      -9.503e 47       -1.29e 47        0
optimization terminated: maximum number of generations exceeded.
serial ga optimization takes 81.5878 seconds.

setting parallel computing toolbox

the finite differencing used by the functions in optimization toolbox to approximate derivatives is done in parallel using the parfor feature if parallel computing toolbox™ is available and there is a parallel pool of workers. similarly, ga, gamultiobj, and patternsearch solvers in global optimization toolbox evaluate functions in parallel. to use the parfor feature, we use the parpool function to set up the parallel environment. the computer on which this example is published has four cores, so parpool starts four matlab® workers. if there is already a parallel pool when you run this example, we use that pool; see the documentation for parpool for more information.

if max(size(gcp)) == 0 % parallel pool needed
    parpool % create the parallel pool
end

minimizing using parallel fmincon

to minimize our expensive optimization problem using the parallel fmincon function, we need to explicitly indicate that our objective and constraint functions can be evaluated in parallel and that we want fmincon to use its parallel functionality wherever possible. currently, finite differencing can be done in parallel. we are interested in measuring the time taken by fmincon so that we can compare it to the serial fmincon run.

options = optimoptions(options,'useparallel',true);
starttime = tic;
xsol = fmincon(@expensive_objfun,startpoint,[],[],[],[],[],[],@expensive_confun,options);
time_fmincon_parallel = toc(starttime);
fprintf('parallel fmincon optimization takes %g seconds.\n',time_fmincon_parallel);

                                            first-order      norm of
 iter f-count            f(x)  feasibility   optimality         step
    0       5    1.839397e 00    1.500e 00    3.211e 00
    1      11   -9.760099e-01    3.708e 00    7.902e-01    2.362e 00
    2      16   -1.480976e 00    0.000e 00    8.344e-01    1.069e 00
    3      21   -2.601599e 00    0.000e 00    8.390e-01    1.218e 00
    4      29   -2.823630e 00    0.000e 00    2.598e 00    1.118e 00
    5      34   -3.905338e 00    0.000e 00    1.210e 00    7.302e-01
    6      39   -6.212992e 00    3.934e-01    7.372e-01    2.405e 00
    7      44   -5.948761e 00    0.000e 00    1.784e 00    1.905e 00
    8      49   -6.940062e 00    1.233e-02    7.668e-01    7.553e-01
    9      54   -6.973887e 00    0.000e 00    2.549e-01    3.920e-01
   10      59   -7.142993e 00    0.000e 00    1.903e-01    4.735e-01
   11      64   -7.155325e 00    0.000e 00    1.365e-01    2.626e-01
   12      69   -7.179122e 00    0.000e 00    6.336e-02    9.115e-02
   13      74   -7.180116e 00    0.000e 00    1.069e-03    4.670e-02
   14      79   -7.180409e 00    0.000e 00    7.797e-04    2.815e-03
   15      84   -7.180410e 00    0.000e 00    6.368e-06    3.120e-04
local minimum found that satisfies the constraints.
optimization completed because the objective function is non-decreasing in 
feasible directions, to within the value of the optimality tolerance,
and constraints are satisfied to within the value of the constraint tolerance.
parallel fmincon optimization takes 8.79291 seconds.

minimizing using parallel genetic algorithm

to minimize our expensive optimization problem using the ga function, we need to explicitly indicate that our objective function can be evaluated in parallel and that we want ga to use its parallel functionality wherever possible. to use the parallel ga we also require that the 'vectorized' option be set to the default (i.e., 'off'). we are again interested in measuring the time taken by ga so that we can compare it to the serial ga run. though this run may be different from the serial one because ga uses a random number generator, the number of expensive function evaluations is the same in both runs. note that running ga requires global optimization toolbox.

rng default % to get the same evaluations as the previous run
if gaavailable
    gaoptions = optimoptions(gaoptions,'useparallel',true);
    starttime = tic;
    gasol = ga(@expensive_objfun,nvar,[],[],[],[],[],[],[],gaoptions);
    time_ga_parallel = toc(starttime);
    fprintf('parallel ga optimization takes %g seconds.\n',time_ga_parallel);
end

single objective optimization:
4 variable(s)
options:
creationfcn:       @gacreationuniform
crossoverfcn:      @crossoverscattered
selectionfcn:      @selectionstochunif
mutationfcn:       @mutationgaussian
                                  best           mean      stall
generation      func-count        f(x)           f(x)    generations
    1              100      -5.546e 05       1.483e 15        0
    2              147      -5.581e 17      -1.116e 16        0
    3              194      -7.556e 17       6.679e 22        0
    4              241      -7.556e 17      -7.195e 16        1
    5              288      -9.381e 27      -1.876e 26        0
    6              335      -9.673e 27      -7.497e 26        0
    7              382      -4.511e 36      -9.403e 34        0
    8              429      -5.111e 36      -3.011e 35        0
    9              476      -7.671e 36       9.346e 37        0
   10              523       -1.52e 43      -3.113e 41        0
   11              570      -2.273e 45       -4.67e 43        0
   12              617      -2.589e 47      -6.281e 45        0
   13              664      -2.589e 47      -1.015e 46        1
   14              711      -8.149e 47      -5.855e 46        0
   15              758      -9.503e 47       -1.29e 47        0
optimization terminated: maximum number of generations exceeded.
parallel ga optimization takes 15.2253 seconds.

compare serial and parallel time

x = [time_fmincon_sequential time_fmincon_parallel];
y = [time_ga_sequential time_ga_parallel];
t = [0 1];
plot(t,x,'r--',t,y,'k-')
ylabel('time in seconds')
legend('fmincon','ga')
ax = gca;
ax.xtick = [0 1];
ax.xticklabel = {'serial' 'parallel'};
axis([0 1 0 ceil(max([x y]))])
title('serial vs. parallel times')

utilizing parallel function evaluation via parfor improved the efficiency of both fmincon and ga. the improvement is typically better for expensive objective and constraint functions.

related topics

    网站地图