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

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

1. Reset Counters

Set the counters for basins and threshold to 0.

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

3. Update Basin Radius and Threshold

If the exit flag of the current `fmincon` run is positive:

1. Set threshold to the score value at start point `p`.

2. Set basin radius for `xp` equal to the maximum of the existing radius (if any) and the distance between `p` and `xp`.

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

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

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

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

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.

#### 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 as follows:

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

2. Loop over the local solutions `j` beginning with the lowest (best) `Fval`.

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

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

 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.

 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.

 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.

Watch now