GlobalSearch
and MultiStart
have
similar approaches to finding global or multiple minima. Both algorithms
start a local solver (such as fmincon
) from multiple
start points. The algorithms use multiple start points to sample multiple
basins of attraction. For more information, see Basins of Attraction.
GlobalSearch and MultiStart Algorithm Overview contains a
sketch of the GlobalSearch
and MultiStart
algorithms.
GlobalSearch and MultiStart Algorithm Overview
The main differences between GlobalSearch
and MultiStart
are:
GlobalSearch
uses a scatter-search
mechanism for generating start points. MultiStart
uses
uniformly distributed start points within bounds, or user-supplied
start points.
GlobalSearch
analyzes start points
and rejects those points that are unlikely to improve the best local
minimum found so far. MultiStart
runs all start points
(or, optionally, all start points that are feasible with respect to
bounds or inequality constraints).
MultiStart
gives a choice of local
solver: fmincon
, fminunc
, lsqcurvefit
,
or lsqnonlin
. The GlobalSearch
algorithm
uses fmincon
.
MultiStart
can run in parallel, distributing
start points to multiple processors for local solution. To run MultiStart
in
parallel, see How to Use Parallel Processing in Global Optimization Toolbox.
The differences between these solver objects boil down to the following decision on which to use:
Use GlobalSearch
to find a single
global minimum most efficiently on a single processor.
Use MultiStart
to:
Find multiple local minima.
Run in parallel.
Use a solver other than fmincon
.
Search thoroughly for a global minimum.
Explore your own start points.
For a description of the algorithm, see Ugray et al. [1].
When you run
a GlobalSearch
object,
the algorithm performs the following steps:
GlobalSearch
runs fmincon
from
the start point you give in the problem
structure.
If this run converges, GlobalSearch
records the start
point and end point for an initial estimate on the radius of a basin
of attraction. Furthermore, GlobalSearch
records
the final objective function value for use in the score function
(see Obtain Stage 1 Start Point, Run).
The score function is the sum of the objective function value
at a point and a multiple of the sum of the constraint violations.
So a feasible point has score equal to its objective function value.
The multiple for constraint violations is initially 1000. GlobalSearch
updates
the multiple during the run.
GlobalSearch
uses the scatter search algorithm
to generate a set of NumTrialPoints
trial points.
Trial points are potential start points. For a description of the
scatter search algorithm, see Glover [2]. GlobalSearch
generates
trial points within any finite bounds you set (lb
and ub
).
Unbounded components have artificial bounds imposed: lb =
-1e4 + 1
, ub
= 1e4 + 1
. This range
is not symmetric about the origin so that the origin is not in the
scatter search. Components with one-sided bounds have artificial bounds
imposed on the unbounded side, shifted by the finite bounds to keep lb < ub
.
GlobalSearch
evaluates the score function of
a set of NumStageOnePoints
trial points. It then
takes the point with the best score and runs fmincon
from
that point. GlobalSearch
removes the set of NumStageOnePoints
trial
points from its list of points to examine.
The localSolverThreshold
is initially the
smaller of the two objective function values at the solution points.
The solution points are the fmincon
solutions
starting from x0
and from the Stage 1 start point.
If both of these solution points do not exist or are infeasible, localSolverThreshold
is
initially the penalty function value of the Stage 1 start point.
The GlobalSearch
heuristic assumption is that
basins of attraction are spherical. The initial estimate of basins
of attraction for the solution point from x0
and
the solution point from Stage 1 are spheres centered at the solution
points. The radius of each sphere is the distance from the initial
point to the solution point. These estimated basins can overlap.
There are two sets of counters associated with the algorithm. Each counter is the number of consecutive trial points that:
Lie within a basin of attraction. There is one counter for each basin.
Have score function greater than localSolverThreshold
.
For a definition of the score, see Run fmincon from x0.
All counters are initially 0.
GlobalSearch
repeatedly examines a remaining
trial point from the list, and performs the following steps. It continually
monitors the time, and stops the search if elapsed time exceeds MaxTime
seconds.
Call the trial point p
. Run fmincon
from p
if
the following conditions hold:
p
is not in any existing basin.
The criterion for every basin i
is:
|p - center(i)| > DistanceThresholdFactor * radius(i).
DistanceThresholdFactor
is an option (default
value 0.75
).
radius
is an estimated radius that updates
in Update
Basin Radius and Threshold and React to Large Counter Values.
score(p
) < localSolverThreshold
.
(optional) p
satisfies bound and/or
inequality constraints. This test occurs if you set the StartPointsToRun
property
of the GlobalSearch
object to 'bounds'
or 'bounds-ineqs'
.
Reset Counters
Set the counters for basins and threshold to 0.
Update Solution Set
If fmincon
runs starting from p
,
it can yield a positive exit flag, which indicates convergence. In
that case, GlobalSearch
updates the vector of GlobalOptimSolution
objects.
Call the solution point xp
and the objective function
value fp
. There are two cases:
For every other solution point xq
with
objective function value fq
,
|xq - xp| > XTolerance * max(1,|xp|)
or
|fq - fp| > FunctionTolerance * max(1,|fp|)
.
In this case, GlobalSearch
creates a new element in the
vector of GlobalOptimSolution
objects. For details of the information contained in each
object, see GlobalOptimSolution
.
For some other solution point xq
with
objective function value fq
,
|xq - xp| <= XTolerance * max(1,|xp|)
and
|fq - fp| <= FunctionTolerance * max(1,|fp|)
.
In this case, GlobalSearch
regards xp
as
equivalent to xq
. The GlobalSearch
algorithm
modifies the GlobalOptimSolution
of xq
by
adding p
to the cell array of X0
points.
There is one minor tweak that can happen to this update. If
the exit flag for xq
is greater than 1
,
and the exit flag for xp
is 1
,
then xp
replaces xq
. This replacement
can lead to some points in the same basin being more than a distance
of XTolerance
from xp
.
Update Basin Radius and Threshold
If the exit flag of the current fmincon
run
is positive:
Set threshold to the score value at start point p
.
Set basin radius for xp
equal to the
maximum of the existing radius (if any) and the distance between p
and xp
.
Report to Iterative Display
When the GlobalSearch
Display
property
is 'iter'
, every point that fmincon
runs
creates one line in the GlobalSearch
iterative display.
Update Counters
Increment the counter for every basin containing p
.
Reset the counter of every other basin to 0
.
Increment the threshold counter if score(p
) >= localSolverThreshold
.
Otherwise, reset the counter to 0
.
React to Large Counter Values
For each basin with counter equal to MaxWaitCycle
,
multiply the basin radius by 1
– BasinRadiusFactor
. Reset the counter
to 0
. (Both MaxWaitCycle
and BasinRadiusFactor
are
settable properties of the GlobalSearch
object.)
If the threshold counter equals MaxWaitCycle
,
increase the threshold:
new threshold = threshold + PenaltyThresholdFactor
*(1
+
abs(threshold)).
Reset the counter to 0
.
Report to Iterative Display
Every 200th trial point creates one line in the GlobalSearch
iterative
display.
After reaching MaxTime
seconds or running
out of trial points, GlobalSearch
creates a vector
of GlobalOptimSolution
objects. GlobalSearch
orders
the vector by objective function value, from lowest (best) to highest
(worst). This concludes the algorithm.
When you run
a MultiStart
object,
the algorithm performs the following steps:
MultiStart
checks input arguments for
validity. Checks include running the local solver once on problem inputs. Even
when run in parallel, MultiStart
performs
these checks serially.
If you call MultiStart
with the syntax
[x,fval] = run(ms,problem,k)
for an integer k
, MultiStart
generates k - 1
start points exactly as
if you used a RandomStartPointSet
object. The algorithm
also uses the x0
start point from the problem
structure,
for a total of k
start points.
A RandomStartPointSet
object does not have any points stored
inside the object. Instead, MultiStart
calls
list
,
which generates random points within the bounds given by the
problem
structure. If an unbounded component exists,
list
uses an artificial bound given by the
ArtificialBound
property of the RandomStartPointSet
object.
If you provide a CustomStartPointSet
object, MultiStart
does
not generate start points, but uses the points in the object.
If you set the StartPointsToRun
property
of the MultiStart
object to 'bounds'
or 'bounds-ineqs'
, MultiStart
does
not run the local solver from infeasible start points. In this context,
“infeasible” means start points that do not satisfy
bounds, or start points that do not satisfy both bounds and inequality
constraints.
The default setting of StartPointsToRun
is 'all'
.
In this case, MultiStart
does not discard infeasible
start points.
MultiStart
runs the local solver specified
in problem.solver
, starting at the points that
pass the StartPointsToRun
filter. If MultiStart
is
running in parallel, it sends start points to worker processors one
at a time, and the worker processors run the local solver.
The local solver checks whether MaxTime
seconds
have elapsed at each of its iterations. If so, it exits that iteration
without reporting a solution.
When the local solver stops, MultiStart
stores
the results and continues to the next step.
Report to Iterative Display. When the MultiStart
Display
property
is 'iter'
, every point that the local solver runs
creates one line in the MultiStart
iterative display.
MultiStart
stops when it runs out of start
points. It also stops when it exceeds a total run time of MaxTime
seconds.
After MultiStart
reaches a stopping condition,
the algorithm creates a vector of GlobalOptimSolution
objects
as follows:
Sort the local solutions by objective function value
(Fval
) from lowest to highest. For the lsqnonlin
and lsqcurvefit
local
solvers, the objective function is the norm of the residual.
Loop over the local solutions j
beginning
with the lowest (best) Fval
.
Find all the solutions k
satisfying
both:
|Fval(k) - Fval(j)| <= FunctionTolerance*max(1,|Fval(j)|)
|x(k) - x(j)| <= XTolerance*max(1,|x(j)|)
Record j
, Fval(j)
,
the local solver output
structure for j
,
and a cell array of the start points for j
and
all the k
. Remove those points k
from
the list of local solutions. This point is one entry in the vector
of GlobalOptimSolution
objects.
The resulting vector of GlobalOptimSolution
objects
is in order by Fval
, from lowest (best) to highest
(worst).
Report to Iterative Display. After examining all the local solutions, MultiStart
gives
a summary to the iterative display. This summary includes the number
of local solver runs that converged, the number that failed to converge,
and the number that had errors.
[1] Ugray, Zsolt, Leon Lasdon, John C. Plummer, Fred Glover, James Kelly, and Rafael Martí. Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization. INFORMS Journal on Computing, Vol. 19, No. 3, 2007, pp. 328–340.
[2] Glover, F. “A template for scatter search and path relinking.” Artificial Evolution (J.-K. Hao, E.Lutton, E.Ronald, M.Schoenauer, D.Snyers, eds.). Lecture Notes in Computer Science, 1363, Springer, Berlin/Heidelberg, 1998, pp. 13–54.
[3] Dixon, L. and G. P. Szegö. “The Global Optimization Problem: an Introduction.” Towards Global Optimisation 2 (Dixon, L. C. W. and G. P. Szegö, eds.). Amsterdam, The Netherlands: North Holland, 1978.