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

  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. (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:

  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

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

See Also

Topics