How GlobalSearch and MultiStart Work - MATLAB & Simulink - MathWorks (2024)

Deciding Which Solver to Use

The differences between these solver objects boil down to thefollowing decision on which to use:

Run fmincon from x0

GlobalSearch runs fmincon fromthe start point you give in the problem structure.If this run converges, GlobalSearch records the startpoint and end point for an initial estimate on the radius of a basinof attraction. Furthermore, GlobalSearch recordsthe 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 valueat 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 updatesthe multiple during the run.

Generate Trial Points

GlobalSearch uses the scatter search algorithmto generate a set of NumTrialPoints trial points.Trial points are potential start points. For a description of thescatter search algorithm, see Glover [2]. GlobalSearch generatestrial points within any finite bounds you set (lb and ub).Unbounded components have artificial bounds imposed: lb =-1e4+1, ub= 1e4+1. This rangeis not symmetric about the origin so that the origin is not in thescatter search. Components with one-sided bounds have artificial boundsimposed on the unbounded side, shifted by the finite bounds to keep lb<ub.

Obtain Stage 1 Start Point, Run

GlobalSearch evaluates the score function ofa set of NumStageOnePoints trial points. It thentakes the point with the best score and runs fmincon fromthat point. GlobalSearch removes the set of NumStageOnePoints trialpoints from its list of points to examine.

Initialize Basins, Counters, Threshold

The localSolverThreshold is initially thesmaller of the two objective function values at the solution points.The solution points are the fmincon solutionsstarting from x0 and from the Stage 1 start point.If both of these solution points do not exist or are infeasible, localSolverThreshold isinitially the penalty function value of the Stage 1 start point.

The GlobalSearch heuristic assumption is thatbasins of attraction are spherical. The initial estimate of basinsof attraction for the solution point from x0 andthe solution point from Stage 1 are spheres centered at the solutionpoints. The radius of each sphere is the distance from the initialpoint 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:

All counters are initially 0.

Begin Main Loop

GlobalSearch repeatedly examines a remainingtrial point from the list, and performs the following steps. It continuallymonitors 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 ifthe following conditions hold:

When fmincon Runs

When fmincon Does Not Run

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.

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 asif you used a RandomStartPointSet object. The algorithmalso 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 doesnot generate start points, but uses the points in the object.

Filter Start Points (Optional)

If you set the StartPointsToRun propertyof the MultiStart object to 'bounds' or 'bounds-ineqs', MultiStart doesnot run the local solver from infeasible start points. In this context,“infeasible” means start points that do not satisfybounds, or start points that do not satisfy both bounds and inequalityconstraints.

The default setting of StartPointsToRun is 'all'.In this case, MultiStart does not discard infeasiblestart points.

Run Local Solver

MultiStart runs the local solver specifiedin problem.solver, starting at the points thatpass the StartPointsToRun filter. If MultiStart isrunning in parallel, it sends start points to worker processors oneat 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 propertyis 'iter', every point that the local solver runscreates one line in the MultiStart iterative display.

Check Stopping Conditions

MultiStart stops when it runs out of startpoints. 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:

The resulting vector of GlobalOptimSolution objectsis in order by Fval, from lowest (best) to highest(worst).

Report to Iterative Display.After examining all the local solutions, MultiStart givesa summary to the iterative display. This summary includes the numberof local solver runs that converged, the number that failed to converge,and the number that had errors.