GlobalSearch

Find global minimum

Description

A GlobalSearch object contains properties (options) that affect how run repeatedly runs a local solver to generate a GlobalOptimSolution object. 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

gs = GlobalSearch creates gs, a GlobalSearch solver with its properties set to the defaults.

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

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

gs = GlobalSearch(ms) creates gs, a GlobalSearch solver, with common property values from the ms MultiStart solver.

Properties

BasinRadiusFactor — Basin radius decrease factor

0.2 (default) | scalar from 0 through 1

Basin radius decrease factor, specified as a scalar from 0 through 1. A basin radius decreases after MaxWaitCycle consecutive start points are within the basin. The basin radius decreases by a factor of 1 – BasinRadiusFactor.

Set BasinRadiusFactor to 0 to disable updates of the basin radius.

Example: 0.5

Data Types: double

Display — Level of display to the Command Window

'final' (default) | 'iter' | 'off'

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

• 'final' – Report summary results after run finishes.

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

• 'off' – No display.

Example: 'iter'

Data Types: char | string

DistanceThresholdFactor — Multiplier for determining trial point is in existing basin

0.75 (default) | nonnegative scalar

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

Example: 0.5

Data Types: double

FunctionTolerance — Tolerance on function values for considering solutions equal

1e-6 (default) | nonnegative scalar

Tolerance on function values for considering solutions equal, specified as a nonnegative scalar. Solvers consider two solutions identical if they are within XTolerance relative distance of each other and have objective function values within FunctionTolerance relative difference of each other. If both conditions are not met, solvers report the solutions as distinct. Set FunctionTolerance to 0 to obtain the results of every local solver run. Set FunctionTolerance to a larger value to have fewer results. For GlobalSearch details, see Update Solution Set in When fmincon Runs. For MultiStart details, see Create GlobalOptimSolution Object.

Example: 1e-4

Data Types: double

MaxTime — Maximum time in seconds that GlobalSearch runs

Inf (default) | positive scalar

Maximum time in seconds that GlobalSearch runs, specified as a positive scalar. GlobalSearch and its local solvers halt when MaxTime seconds have passed since the beginning of the run, as measured by tic and toc.

MaxTime does not interrupt local solvers during a run, so the total time can exceed MaxTime.

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

Data Types: double

MaxWaitCycle — Algorithm control parameter

20 (default) | positive integer

Algorithm control parameter, specified as a positive integer.

• If the observed penalty function of MaxWaitCycle consecutive trial points is at least the penalty threshold, then raise the penalty threshold (see PenaltyThresholdFactor).

• If MaxWaitCycle consecutive trial points are in a basin, then update that basin's radius (see BasinRadiusFactor).

Example: 40

Data Types: double

NumStageOnePoints — Number of Stage 1 points

200 (default) | positive integer

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

Example: 1000

Data Types: double

NumTrialPoints — Number of potential start points

1000 (default) | positive integer

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

Example: 3e4

Data Types: double

OutputFcn — Report on solver progress or halt solver

[] (default) | function handle | cell array of function handles

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 in OutputFcn. See GlobalSearch Output Function.

Data Types: cell | function_handle

PenaltyThresholdFactor — Increase in penalty threshold

0.2 (default) | positive scalar

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

Example: 0.4

Data Types: double

PlotFcn — Plot solver progress

[] (default) | function handle | cell array of function handles

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 in OutputFcn.

There are two built-in plot functions:

• @gsplotbestf plots the best objective function value.

• @gsplotfunccount plots the number of function evaluations.

See MultiStart Plot Function.

Example: @gsplotbestf

Data Types: cell | function_handle

StartPointsToRun — Start points to run

'all' (default) | 'bounds' | 'bounds-ineqs'

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.

GlobalSearch checks the StartPointsToRun property only during Stage 2 of the GlobalSearch algorithm (the main loop). For more information, see GlobalSearch Algorithm.

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

Data Types: char | string

XTolerance — Tolerance on distance for considering solutions equal

1e-6 (default) | nonnegative scalar

Tolerance on distance for considering solutions equal, specified as a nonnegative scalar. Solvers consider two solutions identical if they are within XTolerance relative distance of each other and have objective function values within FunctionTolerance relative difference of each other. If both conditions are not met, solvers report the solutions as distinct. Set XTolerance to 0 to obtain the results of every local solver run. Set XTolerance to a larger value to have fewer results. For GlobalSearch details, see Update Solution Set in When fmincon Runs. For MultiStart details, see Create GlobalOptimSolution Object.

Example: 2e-4

Data Types: double

Object Functions

run	Run multiple-start solver

Examples

Run GlobalSearch on Multidimensional Problem

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

rng default % For reproducibility
gs = 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 at x when you call run by using the following syntax:

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

However, if you neglected to request fval, you can still compute the objective function value at x.

fval = sixmin(x)

fval = -1.0316

Run GlobalSearch on 1-D Problem

Consider a function with several local minima.

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

To search for the global minimum, run GlobalSearch using the fmincon 'sqp' algorithm.

rng default % For reproducibility
opts = 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

GlobalSearch Using Common Properties from MultiStart

Create a nondefault MultiStart object.

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 a GlobalSearch object that uses the available properties from ms.

gs = GlobalSearch(ms)

gs = 
  GlobalSearch with properties:

             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

gs has the same nondefault value of FunctionTolerance as ms. But gs does not use the UseParallel property.

Update GlobalSearch Properties

Create a GlobalSearch object with a FunctionTolerance of 1e-4.

gs = GlobalSearch('FunctionTolerance',1e-4)

gs = 
  GlobalSearch with properties:

             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 the XTolerance property to 1e-3 and the StartPointsToRun property to 'bounds'.

gs = GlobalSearch(gs,'XTolerance',1e-3,'StartPointsToRun','bounds')

gs = 
  GlobalSearch with properties:

             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 with properties:

             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, see GlobalSearch 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.