Main Content

GlobalSearch

Find global minimum

expand all in page

Description

AGlobalSearchobject contains properties (options) that affect howrunrepeatedly runs a local solver to generate aGlobalOptimSolutionobject. When run, the solver attempts to locate a solution that has the lowest objective function value.

Creation

Syntax

gs = GlobalSearch
gs = GlobalSearch(Name,Value)
gs = GlobalSearch(oldGS,Name,Value)
gs = GlobalSearch(ms)

Description

example

gs = GlobalSearchcreatesgs, aGlobalSearchsolver with its properties set to the defaults.

example

gs = GlobalSearch(Name,Value)sets properties using name-value pairs.

example

gs = GlobalSearch(oldGS,Name,Value)creates a copy of theoldGSGlobalSearchsolver, and sets properties using name-value pairs.

example

gs = GlobalSearch(ms)createsgs, aGlobalSearchsolver, with common property values from themsMultiStartsolver.

Properties

expand all

Basin radius decrease factor, specified as a scalar from0through1. A basin radius decreases afterMaxWaitCycleconsecutive start points are within the basin. The basin radius decreases by a factor of 1 –BasinRadiusFactor.

SetBasinRadiusFactorto0to disable updates of the basin radius.

Example:0.5

Data Types:double

Level of display to the Command Window, specified as one of the following character vectors or strings:

  • 'final'– Report summary results afterrunfinishes.

  • 'iter'– Report results after the initialfminconrun, after Stage 1, after every 200 start points, and after every run offmincon, in addition to the final summary.

  • 'off'– No display.

Example:'iter'

Data Types:char|string

Multiplier for determining whether a trial point is in an existing basin of attraction, specified as a nonnegative scalar. For details, seeExamine Stage 2 Trial Point to See if fmincon Runs.

Example:0.5

Data Types:double

Tolerance on function values for considering solutions equal, specified as a nonnegative scalar. Solvers consider two solutions identical if they are withinXTolerancerelative distance of each other and have objective function values withinFunctionTolerancerelative difference of each other. If both conditions are not met, solvers report the solutions as distinct. SetFunctionToleranceto0to obtain the results of every local solver run. SetFunctionToleranceto a larger value to have fewer results. ForGlobalSearchdetails, seeUpdate Solution SetinWhen fmincon Runs. ForMultiStartdetails, seeCreate GlobalOptimSolution Object.

Example:1e-4

Data Types:double

Maximum time in seconds that GlobalSearch runs, specified as a positive scalar. GlobalSearch and its local solvers halt whenMaxTimeseconds have passed since the beginning of the run, as measured byticandtoc.

MaxTimedoes not interrupt local solvers during a run, so the total time can exceedMaxTime.

Example:180stops the solver the first time a local solver call finishes after 180 seconds.

Data Types:double

Algorithm control parameter, specified as a positive integer.

  • If the observed penalty function ofMaxWaitCycleconsecutive trial points is at least the penalty threshold, then raise the penalty threshold (seePenaltyThresholdFactor).

  • IfMaxWaitCycleconsecutive trial points are in a basin, then update that basin's radius (seeBasinRadiusFactor).

Example:40

Data Types:double

Number of Stage 1 points, specified as a positive integer. For details, seeObtain Stage 1 Start Point, Run.

Example:1000

Data Types:double

Number of potential start points, specified as a positive integer.

Example:3e4

Data Types:double

Report on solver progress or halt solver, specified as a function handle or cell array of function handles. Output functions run after each local solver call. They also run when the global solver starts and ends. Write output functions using the syntax described inOutputFcn. SeeGlobalSearch Output Function.

Data Types:cell|function_handle

Increase in the penalty threshold, specified as a positive scalar. For details, seeReact to Large Counter Values.

Example:0.4

Data Types:double

Plot solver progress, specified as a function handle or cell array of function handles. Plot functions run after each local solver call. They also run when the global solver starts and ends. Write plot functions using the syntax described inOutputFcn.

There are two built-in plot functions:

  • @gsplotbestfplots the best objective function value.

  • @gsplotfunccountplots the number of function evaluations.

SeeMultiStart Plot Function.

Example:@gsplotbestf

Data Types:cell|function_handle

Start points to run, specified as:

  • 'all'— Run all start points.

  • 'bounds'— Run only start points that satisfy bounds.

  • 'bounds-ineqs'— Run only start points that satisfy bounds and inequality constraints.

GlobalSearchchecks theStartPointsToRunproperty only during Stage 2 of theGlobalSearchalgorithm (the main loop). For more information, seeGlobalSearch Algorithm.

Example:'bounds'runs only points that satisfy all bounds.

Data Types:char|string

Tolerance on distance for considering solutions equal, specified as a nonnegative scalar. Solvers consider two solutions identical if they are withinXTolerancerelative distance of each other and have objective function values withinFunctionTolerancerelative difference of each other. If both conditions are not met, solvers report the solutions as distinct. SetXToleranceto0to obtain the results of every local solver run. SetXToleranceto a larger value to have fewer results. ForGlobalSearchdetails, seeUpdate Solution SetinWhen fmincon Runs. ForMultiStartdetails, seeCreate GlobalOptimSolution Object.

Example:2e-4

Data Types:double

Object Functions

run Run multiple-start solver

Examples

collapse all

Open Live Script

Create an optimization problem that has several local minima, and try to find the global minimum usingGlobalSearch. The objective is the six-hump camel back problem (seeRun the Solver).

rngdefault% For reproducibilitygs = GlobalSearch; sixmin = @(x)(4*x(1)^2 - 2.1*x(1)^4 + x(1)^6/3...+ x(1)*x(2) - 4*x(2)^2 + 4*x(2)^4); problem = createOptimProblem('fmincon','x0',[-1,2],...'objective',sixmin,'lb',[-3,-3],'ub',[3,3]); x = run(gs,problem)
GlobalSearch stopped because it analyzed all the trial points. All 8 local solver runs converged with a positive local solver exit flag.
x =1×2-0.0898 0.7127

You can request the objective function value atxwhen you callrunby using the following syntax:

[x,fval] = run(gs,problem)

However, if you neglected to requestfval, you can still compute the objective function value atx.

fval = sixmin(x)
fval = -1.0316
Open Live Script

Consider a function with several local minima.

fun = @(x) x.^2 + 4*sin(5*x); fplot(fun,[-5,5])

Figure contains an axes object. The axes object contains an object of type functionline.

To search for the global minimum, runGlobalSearchusing thefmincon'sqp'algorithm.

rngdefault% For reproducibilityopts = optimoptions(@fmincon,'Algorithm','sqp'); problem = createOptimProblem('fmincon','objective',...fun,'x0',3,'lb',-5,'ub',5,'options',opts); gs = GlobalSearch; [x,f] = run(gs,problem)
GlobalSearch stopped because it analyzed all the trial points. All 23 local solver runs converged with a positive local solver exit flag.
x = -0.3080
f = -3.9032
Open Live Script

Create a nondefaultMultiStartobject.

ms = MultiStart('FunctionTolerance',2e-4,'UseParallel',true)
ms = MultiStart with properties: UseParallel: 1 Display: 'final' FunctionTolerance: 2.0000e-04 MaxTime: Inf OutputFcn: [] PlotFcn: [] StartPointsToRun: 'all' XTolerance: 1.0000e-06

Create aGlobalSearchobject that uses the available properties fromms.

gs = GlobalSearch(ms)
gs = GlobalSearch属性:NumTrialPoints:1000 BasinRadiusFactor: 0.2000 DistanceThresholdFactor: 0.7500 MaxWaitCycle: 20 NumStageOnePoints: 200 PenaltyThresholdFactor: 0.2000 Display: 'final' FunctionTolerance: 2.0000e-04 MaxTime: Inf OutputFcn: [] PlotFcn: [] StartPointsToRun: 'all' XTolerance: 1.0000e-06

gshas the same nondefault value ofFunctionToleranceasms. Butgsdoes not use theUseParallelproperty.

Open Live Script

Create aGlobalSearchobject with aFunctionToleranceof1e-4.

gs = GlobalSearch('FunctionTolerance',1e-4)
gs = GlobalSearch属性:NumTrialPoints:1000 BasinRadiusFactor: 0.2000 DistanceThresholdFactor: 0.7500 MaxWaitCycle: 20 NumStageOnePoints: 200 PenaltyThresholdFactor: 0.2000 Display: 'final' FunctionTolerance: 1.0000e-04 MaxTime: Inf OutputFcn: [] PlotFcn: [] StartPointsToRun: 'all' XTolerance: 1.0000e-06

Update theXToleranceproperty to1e-3and theStartPointsToRunproperty to'bounds'.

gs = GlobalSearch(gs,'XTolerance',1e-3,'StartPointsToRun','bounds')
gs = GlobalSearch属性:NumTrialPoints:1000 BasinRadiusFactor: 0.2000 DistanceThresholdFactor: 0.7500 MaxWaitCycle: 20 NumStageOnePoints: 200 PenaltyThresholdFactor: 0.2000 Display: 'final' FunctionTolerance: 1.0000e-04 MaxTime: Inf OutputFcn: [] PlotFcn: [] StartPointsToRun: 'bounds' XTolerance: 1.0000e-03

You can also update properties one at a time by using dot notation.

gs.MaxTime = 1800
gs = GlobalSearch属性:NumTrialPoints:1000 BasinRadiusFactor: 0.2000 DistanceThresholdFactor: 0.7500 MaxWaitCycle: 20 NumStageOnePoints: 200 PenaltyThresholdFactor: 0.2000 Display: 'final' FunctionTolerance: 1.0000e-04 MaxTime: 1800 OutputFcn: [] PlotFcn: [] StartPointsToRun: 'bounds' XTolerance: 1.0000e-03

Algorithms

For a detailed description of the algorithm, seeGlobalSearch Algorithm. Ugray et al.[1]describe both the algorithm and the scatter-search method of generating trial points.

References

[1] Ugray, Zsolt, Leon Lasdon, John 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.

Version History

Introduced in R2010a

See Also

||

Topics