Loren on the Art of MATLAB

Turn ideas into MATLAB

Note

Loren on the Art of MATLAB has been archived and will not be updated.

Selecting the Granularity You Want in GlobalSearch or MultiStart

I'd like to introduce this week's guest blogger Alan Weiss. Alan writes documentation for mathematical toolboxes here at MathWorks.

Do you use GlobalSearch or MultiStart for finding multiple local solutions to your optimization problems? Both of these solvers can report the locations and objective function values of the local solutions they find, as well as the starting points that led to each local solution.

Sometimes, though, the solvers report too many local solutions. Their definition of what constitutes "distinct" solutions can differ from yours. This article shows the problem, and two solutions. One solution involves setting GlobalSearch or MultiStart tolerances. But this can be difficult if you don't know beforehand how close solutions can be. The other involves the clumpthem function; download it here.

Contents

A Function with Six Local Minima

For example, look at the six-hump camelback function described in the documentation. Get the sixhumps code.

sixmin = sixhumps
sixmin = 
    @(x)(4*x(:,1).^2-2.1*x(:,1).^4+x(:,1).^6/3+x(:,1).*x(:,2)-4*x(:,2).^2+4*x(:,2).^4)

You can see in the contour plot that there are six local minima. The colored asterisks mark the minima.

MultiStart Finds 50 Local Minima

Take a look at the number of local minima reported by running MultiStart with the fmincon local solver and active-set algorithm.

ms = MultiStart;
opts = optimoptions(@fmincon,'Algorithm','active-set');
problem = createOptimProblem('fmincon','x0',[-1,2],...
'objective',sixmin,'lb',[-3,-3],'ub',[3,3],...
'options',opts);
rng default % for reproducibility
[xminm,fminm,flagm,outptm,manyminsm] = run(ms,problem,50); % run fmincon 50 times
size(manyminsm)
MultiStart completed the runs from all start points.

All 50 local solver runs converged with a positive local solver exit flag.
ans =
     1    50

How could there be 50 separate minima reported when you know that there are only six points that are local minima? The answer is that many of these minima are close to each other. For example, the first three points look the same.

manyminsm(1).X
manyminsm(2).X
manyminsm(3).X
ans =
    -0.089843      0.71266
ans =
    -0.089844      0.71265
ans =
    -0.089834      0.71265

Of course, these reported minima aren't really the same.

norm(manyminsm(1).X - manyminsm(2).X)
ans =
   7.6691e-06

The point is, its default tolerances cause MultiStart to report different minima if they differ by more than 1e-6 in value or position. And these minima are more than 1e-6 apart.

Clump the Minima with MultiStart

You can loosen the default MultiStart tolerances to have MultiStart automatically combine similar minima.

rng default % for reproducibility
ms.TolX = 1e-3;
ms.TolFun = 1e-4;
[xminloose,fminloose,flagloose,outptloose,manyminsloose] = run(ms,problem,50);
size(manyminsloose)
MultiStart completed the runs from all start points.

All 50 local solver runs converged with a positive local solver exit flag.
ans =
     1     6

Loosening the tolerances caused MultiStart to give just the six truly different local minima. But this process involved rerunning the solver.

Clump the Minima Programmatically

Wouldn't it be better to clump the minima without running the solver again? That is the point of the clumpthem function. It takes MultiStart or GlobalSearch solutions and clumps them to the tolerances you want. For example

clumped = clumpthem(manyminsm,1e-3,1e-4); % the first tolerance is TolX, then TolFun
size(clumped)
ans =
     1     6

The answers you get either way are identical.

isequal(manyminsloose(1).X, clumped(1).X)
ans =
     1

How does clumpthem work? It uses the fact that MultiStart and GlobalSearch return solutions in order, from best (lowest objective function value) to worst. It takes the first solution and compares it to the second, both in terms of objective function values and distance between the solutions. If both comparisons are below the tolerances, clumpthem removes the second solution, adding its starting point to the list of X0 starting points. If the objective function value of the second solution is too high, then clumpthem starts a new clump. If the objective function difference is small enough, but the distance between solutions is too large, clumpthem proceeds to compare the first solution with the third. It continues in this way until it runs out of solutions to clump.

This procedure is quite speedy, as you will see in the next section.

Performance

Check the speed of clumpthem.

tic;
clumped = clumpthem(manyminsm,1e-3,1e-4);
toc
Elapsed time is 0.006322 seconds.

MultiStart is much slower, even with this fairly simple function:

rng default % for reproducibility
tic;
[xminloose,fminloose,flagloose,outptloose,manyminsloose] = run(ms,problem,50);
toc
MultiStart completed the runs from all start points.

All 50 local solver runs converged with a positive local solver exit flag.
Elapsed time is 0.863509 seconds.

Feedback

Do you use MultiStart or GlobalSearch to search for multiple local solutions? Have you been annoyed by finding spurious differences in solutions? Tell us about it here.




Published with MATLAB® R2014a


  • print

Comments

To leave a comment, please click here to sign in to your MathWorks Account or create a new one.