MultiStart

Find multiple local minima

Description

A MultiStart object contains properties (options) that affect how run repeatedly runs a local solver to generate a GlobalOptimSolution object. When run, the solver attempts to find multiple local solutions to a problem by starting from various points.

Creation

Syntax

ms = MultiStart

ms = MultiStart(Name,Value)

ms = MultiStart(oldMS,Name,Value)

ms = MultiStart(gs)

Description

ms = MultiStart creates ms, a MultiStart solver with its properties set to the defaults.

ms = MultiStart(Name,Value) sets properties using name-value pairs.

ms = MultiStart(oldMS,Name,Value) creates a copy of the oldMS MultiStart solver, and sets properties using name-value pairs.

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

Properties

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

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 MultiStart runs

Inf (default) | positive scalar

Maximum time in seconds that MultiStart runs, specified as a positive scalar. MultiStart 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

OutputFcn — Report on solver progress or halt solver

[] (default) | @savelocalsolutions | 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 Custom GlobalSearch Output Function.

The built-in @savelocalsolutions output function saves all local solutions to the localSolTable variable in the base workspace. This output function saves the infeasible local solutions as well as the feasible local solutions. For an example, see Collect All Local Solutions.

Data Types: cell | function_handle

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.

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

Data Types: char | string

UseParallel — Distribute local solver calls to multiple processors

false (default) | true

Distribute local solver calls to multiple processors, specified as false or true.

• false — Do not run in parallel.

• true — Distribute the local solver calls to multiple processors.

Example: true

Data Types: logical

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 MultiStart

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 MultiStart on 20 instances of the problem 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);
ms = MultiStart;
[x,f] = run(ms,problem,20)

MultiStart completed the runs from all start points. 

All 20 local solver runs converged with a positive local solver exitflag.

x = 
-0.3080

f = 
-3.9032

Default MultiStart Object

Create a MultiStart object with default properties.

ms = MultiStart

ms = 
  MultiStart with properties:

          UseParallel: 0
              Display: 'final'
    FunctionTolerance: 1.0000e-06
              MaxTime: Inf
            OutputFcn: []
              PlotFcn: []
     StartPointsToRun: 'all'
           XTolerance: 1.0000e-06

Nondefault MultiStart Object

Create a MultiStart object with looser tolerances than default, so the solver returns fewer solutions that are close to each other. Also, have MultiStart run only initial points that are feasible with respect to bounds and inequality constraints.

ms = MultiStart('FunctionTolerance',2e-4,'XTolerance',5e-3,...
    'StartPointsToRun','bounds-ineqs')

ms = 
  MultiStart with properties:

          UseParallel: 0
              Display: 'final'
    FunctionTolerance: 2.0000e-04
              MaxTime: Inf
            OutputFcn: []
              PlotFcn: []
     StartPointsToRun: 'bounds-ineqs'
           XTolerance: 0.0050

MultiStart Using Common Properties from GlobalSearch

Create a nondefault GlobalSearch object.

gs = GlobalSearch('FunctionTolerance',2e-4,'NumTrialPoints',2000)

gs = 
  GlobalSearch with properties:

             NumTrialPoints: 2000
          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

Create a MultiStart object that uses the available properties from gs.

ms = MultiStart(gs)

ms = 
  MultiStart with properties:

          UseParallel: 0
              Display: 'final'
    FunctionTolerance: 2.0000e-04
              MaxTime: Inf
            OutputFcn: []
              PlotFcn: []
     StartPointsToRun: 'all'
           XTolerance: 1.0000e-06

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

Update MultiStart Properties

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

ms = MultiStart('FunctionTolerance',1e-4)

ms = 
  MultiStart with properties:

          UseParallel: 0
              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'.

ms = MultiStart(ms,'XTolerance',1e-3,'StartPointsToRun','bounds')

ms = 
  MultiStart with properties:

          UseParallel: 0
              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.

ms.MaxTime = 1800

ms = 
  MultiStart with properties:

          UseParallel: 0
              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 MultiStart Algorithm.

Extended Capabilities

Automatic Parallel Support

Accelerate code by automatically running computation in parallel using Parallel Computing Toolbox™.

To run in parallel, set the 'UseParallel' option to true.

options = optimoptions('solvername','UseParallel',true)

For more information, see How to Use Parallel Processing in Global Optimization Toolbox.

Version History

Introduced in R2010a

R2024a: Output Function: Built-in output function and updated optimValues structure

The built-in @savelocalsolutions output function saves all local solutions to the localSolTable variable in the base workspace. This output function saves the infeasible local solutions as well as the feasible local solutions.

The optimValues Structure in output functions and plot functions now contains the constrviolation field, which has the maximum constraint violation. This value is 0 for no constraint violations.