## How GlobalSearch and MultiStart Work

### Multiple Runs of a Local Solver

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

### Differences Between the Solver Objects

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.

#### Deciding Which Solver to Use

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.

### GlobalSearch Algorithm

For a description of the algorithm, see Ugray et al. [1].

When you `run`

a `GlobalSearch`

object,
the algorithm performs the following steps:

#### Run fmincon from x0

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

#### Generate Trial Points

`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`

.

#### Obtain Stage 1 Start Point, Run

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

#### Initialize Basins, Counters, Threshold

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.

#### Begin Main Loop

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

#### Examine Stage 2 Trial Point to See if fmincon Runs

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'`

.

#### When fmincon Runs

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

#### When fmincon Does Not Run

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

#### Create GlobalOptimSolution

After reaching `MaxTime`

seconds or running out of trial points, `GlobalSearch`

creates a vector of `GlobalOptimSolution`

objects. (These points
correspond to positive `fmincon`

exit flags.) `GlobalSearch`

orders the vector by objective
function value, from lowest (best) to highest (worst). This concludes the
algorithm.

### MultiStart Algorithm

When you `run`

a `MultiStart`

object,
the algorithm performs the following steps:

#### Validate Inputs

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

#### Generate Start Points

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.

#### Filter Start Points (Optional)

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.

#### Run Local Solver

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

At each of its iterations, the local solver checks whether `MaxTime`

seconds
have elapsed since `MultiStart`

began
calculating. If so, `MultiStart`

exits that
iteration without reporting a solution.

When the local solver stops, `MultiStart`

stores the results
that correspond to positive local solver exit flags 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.

#### Check Stopping Conditions

`MultiStart`

stops when it runs out of start
points. It also stops when it exceeds a total run time of `MaxTime`

seconds.

#### Create GlobalOptimSolution Object

After `MultiStart`

reaches a stopping condition, the algorithm
creates a vector of `GlobalOptimSolution`

objects (all of which correspond to positive local solver exit flags) 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.

### Bibliography

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