How to Optimize with GlobalSearch and MultiStart

Problems You Can Solve with GlobalSearch and MultiStart

The GlobalSearch and MultiStart solvers apply to problems with smooth objective and constraint functions. The solvers search for a global minimum, or for a set of local minima. For more information on which solver to use, see Choosing a Solver.

GlobalSearch and MultiStart work by starting a local solver, such as fmincon, from a variety of start points. Generally the start points are random. However, for MultiStart you can provide a set of start points. For more information, see How GlobalSearch and MultiStart Work.

To find out how to use these solvers, see Outline of Steps. For examples using these solvers, see the example index.

Back to Top

Outline of Steps

To find a global or multiple local solutions:

1. Create a Problem Structure

2. Create a Solver Object

3. (Optional, MultiStart only) Set Start Points for MultiStart

4. Run the Solver

The following figure illustrates these steps.

Back to Top

Determining Inputs for the Problem

A problem structure defines a local optimization problem using a local solver, such as fmincon. Therefore, most of the documentation on choosing a solver or preparing the inputs is in the Optimization Toolbox documentation.

Required Inputs

Optional Inputs

Back to Top

Create a Problem Structure

To use the GlobalSearch or MultiStart solvers, you must first create a problem structure. There are two ways to create a problem structure:

• Using the createOptimProblem Function

• Exporting from the Optimization Tool

Using the createOptimProblem Function

Follow these steps to create a problem structure using the createOptimProblem function.

1. Define your objective function as a file or anonymous function. For details, see Computing Objective Functions. If your solver is lsqcurvefit or lsqnonlin, ensure the objective function returns a vector, not scalar.

2. If relevant, create your constraints, such as bounds and nonlinear constraint functions. For details, see Constraints.

3. Create a start point. For example, to create a three-dimensional random start point xstart:

   xstart = randn(3,1);

4. (Optional) Create an options structure using optimset. For example,

   options = optimset('Algorithm','interior-point');

5. Enter

   problem = createOptimProblem(solver,

   where solver is the name of your local solver:

   • For GlobalSearch: 'fmincon'

   • For MultiStart the choices are:

     • 'fmincon'

     • 'fminunc'

     • 'lsqcurvefit'

     • 'lsqnonlin'

     For help choosing, see Optimization Decision Table.

6. Set an initial point using the 'x0' parameter. If your initial point is xstart, and your solver is fmincon, your entry is now

   problem = createOptimProblem('fmincon','x0',xstart,

7. Include the function handle for your objective function in objective:

   problem = createOptimProblem('fmincon','x0',xstart, ...
       'objective',@objfun,

8. Set bounds and other constraints as applicable.

   Constraint	Name
   lower bounds	'lb'
   upper bounds	'ub'
   matrix Aineq for linear inequalities Aineq x ≤ bineq	'Aineq'
   vector bineq for linear inequalities Aineq x ≤ bineq	'bineq'
   matrix Aeq for linear equalities Aeq x = beq	'Aeq'
   vector beq for linear equalities Aeq x = beq	'beq'
   nonlinear constraint function	'nonlcon'

9. If using the lsqcurvefit local solver, include vectors of input data and response data, named 'xdata' and 'ydata' respectively.

10. Best practice: validate the problem structure by running your solver on the structure. For example, if your local solver is fmincon:

    [x fval eflag output] = fmincon(problem);

    Note   Specify fmincon as the solver for GlobalSearch, even if you have no constraints. However, you cannot run fmincon on a problem without constraints. Add an artificial constraint to the problem to validate the structure: problem.lb = -Inf;

Example: Creating a Problem Structure with createOptimProblem.  This example minimizes the function from Run the Solver, subject to the constraint x₁ + 2x₂ ≥ 4. The objective is

sixmin = 4x² – 2.1x⁴ + x⁶/3 + xy – 4y² + 4y⁴.

Use the interior-point algorithm of fmincon, and set the start point to [2;3].

1. Write a function handle for the objective function.

   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);

2. Write the linear constraint matrices. Change the constraint to "less than" form:

   A = [-1,-2];
   b = -4;

3. Create the local options structure to use the interior-point algorithm:

   opts = optimset('Algorithm','interior-point');

4. Create the problem structure with createOptimProblem:

   problem = createOptimProblem('fmincon', ...
       'x0',[2;3],'objective',sixmin, ...
       'Aineq',A,'bineq',b,'options',opts)

5. The resulting structure:

   problem = 
       objective: @(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)
              x0: [2x1 double]
           Aineq: [-1 -2]
           bineq: -4
             Aeq: []
             beq: []
              lb: []
              ub: []
         nonlcon: []
          solver: 'fmincon'
         options: [1x1 struct]

6. Best practice: validate the problem structure by running your solver on the structure:

   [x fval eflag output] = fmincon(problem);

   Note   Specify fmincon as the solver for GlobalSearch, even if you have no constraints. However, you cannot run fmincon on a problem without constraints. Add an artificial constraint to the problem to validate the structure: problem.lb = -Inf;

Exporting from the Optimization Tool

Follow these steps to create a problem structure using the Optimization Tool.

1. Define your objective function as a file or anonymous function. For details, see Computing Objective Functions. If your solver is lsqcurvefit or lsqnonlin, ensure the objective function returns a vector, not scalar.

2. If relevant, create nonlinear constraint functions. For details, see Nonlinear Constraints.

3. Create a start point. For example, to create a three-dimensional random start point xstart:

   xstart = randn(3,1);

4. Open the Optimization Tool by entering optimtool at the command line, or by choosing Start > Toolboxes > Optimization > Optimization Tool.

5. Choose the local Solver.

   

   • For GlobalSearch: fmincon (default).

   • For MultiStart:

     • fmincon (default)

     • fminunc

     • lsqcurvefit

     • lsqnonlin

     For help choosing, see Optimization Decision Table.

6. Choose an appropriate Algorithm. For help choosing, see Choosing the Algorithm.

   

7. Set an initial point (Start point).

8. Include the function handle for your objective function in Objective function, and, if applicable, include your Nonlinear constraint function. For example,

   

9. Set bounds, linear constraints, or local Options. For details on constraints, see Writing Constraints.

10. Best practice: run the problem to verify the setup.

    

    Note   You must specify fmincon as the solver for GlobalSearch, even if you have no constraints. However, you cannot run fmincon on a problem without constraints. Add an artificial constraint to the problem to verify the setup.

11. Choose File > Export to Workspace and select Export problem and options to a MATLAB structure named

    

Example: Creating a Problem Structure with the Optimization Tool.  This example minimizes the function from Run the Solver, subject to the constraint x₁ + 2x₂ ≥ 4. The objective is

sixmin = 4x² – 2.1x⁴ + x⁶/3 + xy – 4y² + 4y⁴.

Use the interior-point algorithm of fmincon, and set the start point to [2;3].

1. Write a function handle for the objective function.

   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);

2. Write the linear constraint matrices. Change the constraint to "less than" form:

   A = [-1,-2];
   b = -4;

3. Launch the Optimization Tool by entering optimtool at the MATLAB command line.

4. Set the solver, algorithm, objective, start point, and constraints.

   

5. Best practice: run the problem to verify the setup.

   

   The problem runs successfully.

   

6. Choose File > Export to Workspace and select Export problem and options to a MATLAB structure named

   

Back to Top

Create a Solver Object

A solver object contains your preferences for the global portion of the optimization.

You do not need to set any preferences. Create a GlobalSearch object named gs with default settings as follows:

gs = GlobalSearch;

Similarly, create a MultiStart object named ms with default settings as follows:

ms = MultiStart;

Properties (Global Options) of Solver Objects

Global options are properties of a GlobalSearch or MultiStart object.

Properties for both GlobalSearch and MultiStart

Properties for GlobalSearch

Properties for MultiStart

Example: Creating a Nondefault GlobalSearch Object

Suppose you want to solve a problem and:

• Consider local solutions identical if they are within 0.01 of each other and the function values are within the default TolFun tolerance.

• Spend no more than 2000 seconds on the computation.

To solve the problem, create a GlobalSearch object gs as follows:

gs = GlobalSearch('TolX',0.01,'MaxTime',2000);

Example: Creating a Nondefault MultiStart Object

Suppose you want to solve a problem such that:

• You consider local solutions identical if they are within 0.01 of each other and the function values are within the default TolFun tolerance.

• You spend no more than 2000 seconds on the computation.

To solve the problem, create a MultiStart object ms as follows:

ms = MultiStart('TolX',0.01,'MaxTime',2000);

Back to Top

Set Start Points for MultiStart

There are four ways you tell MultiStart which start points to use for the local solver:

• Pass a positive integer k. MultiStart generates k - 1 start points as if using a RandomStartPointSet object and the problem structure. MultiStart also uses the x0 start point from the problem structure, for a total of k start points.

• Pass a RandomStartPointSet object.

• Pass a CustomStartPointSet object.

• Pass a cell array of RandomStartPointSet and CustomStartPointSet objects. Pass a cell array if you have some specific points you want to run, but also want MultiStart to use other random start points.

Note   You can control whether MultiStart uses all start points, or only those points that satisfy bounds or other inequality constraints. For more information, see Filter Start Points (Optional).

Positive Integer for Start Points

The syntax for running MultiStart for k start points is

[xmin,fmin,flag,outpt,allmins] = run(ms,problem,k);

The positive integer k specifies the number of start points MultiStart uses. MultiStart generates random start points using the dimension of the problem and bounds from the problem structure. MultiStart generates k - 1 random start points, and also uses the x0 start point from the problem structure.

RandomStartPointSet Object for Start Points

Create a RandomStartPointSet object as follows:

stpoints = RandomStartPointSet;

By default a RandomStartPointSet object generates 10 start points. Control the number of start points with the NumStartPoints property. For example, to generate 40 start points:

stpoints = RandomStartPointSet('NumStartPoints',40);

You can set an ArtificialBound for a RandomStartPointSet.

• If a component has no bounds, RandomStartPointSet uses a lower bound of -ArtificialBound, and an upper bound of ArtificialBound.

• If a component has a lower bound lb but no upper bound, RandomStartPointSet uses an upper bound of lb + 2*ArtificialBound.

• Similarly, if a component has an upper bound ub but no lower bound, RandomStartPointSet uses a lower bound of ub - 2*ArtificialBound.

For example, to generate 100 start points with an ArtificialBound of 50:

stpoints = RandomStartPointSet('NumStartPoints',100, ...
    'ArtificialBound',50);

CustomStartPointSet Object for Start Points

To use a specific set of starting points, package them in a CustomStartPointSet as follows:

1. Place the starting points in a matrix. Each row of the matrix represents one starting point. MultiStart runs all the rows of the matrix, subject to filtering with the StartPointsToRun property. For more information, see MultiStart Algorithm.

2. Create a CustomStartPointSet object from the matrix:

   tpoints = CustomStartPointSet(ptmatrix);

For example, create a set of 40 five-dimensional points, with each component of a point equal to 10 plus an exponentially distributed variable with mean 25:

pts = -25*log(rand(40,5)) + 10;
tpoints = CustomStartPointSet(pts);

To get the original matrix of points from a CustomStartPointSet object, use the list method:

pts = list(tpoints); % Assumes tpoints is a CustomStartPointSet

A CustomStartPointSet has two properties: DimStartPoints and NumStartPoints. You can use these properties to query a CustomStartPointSet object. For example, the tpoints object in the example has the following properties:

tpoints.DimStartPoints
ans =
     5

tpoints.NumStartPoints
ans =
    40

Cell Array of Objects for Start Points

To use a specific set of starting points along with some randomly generated points, pass a cell array of RandomStartPointSet or CustomStartPointSet objects.

For example, to use both the 40 specific five-dimensional points of CustomStartPointSet Object for Start Points and 40 additional five-dimensional points from RandomStartPointSet:

pts = -25*log(rand(40,5)) + 10;
tpoints = CustomStartPointSet(pts);
rpts = RandomStartPointSet('NumStartPoints',40);
allpts = {tpoints,rpts};

Run MultiStart with the allpts cell array:

% Assume ms and problem exist
[xmin,fmin,flag,outpt,allmins] = run(ms,problem,allpts);

Back to Top

Run the Solver

Running a solver is nearly identical for GlobalSearch and MultiStart. The only difference in syntax is MultiStart takes an additional input describing the start points.

For example, suppose you want to find several local minima of the sixmin function

sixmin = 4x² – 2.1x⁴ + x⁶/3 + xy – 4y² + 4y⁴.

 Code for generating the figure

[X Y] = meshgrid(-2:.1:2,-1:.05:1);
Z = 4*X.^2 - 2.1*X.^4 + X.^6./3 + X.*Y - 4*Y.^2 + 4*Y.^4;
surf(X,Y,Z);view(-44,14)
xlabel('x');ylabel('y')
title('sixmin(x,y)')

This function is also called the six-hump camel back function [3]. All the local minima lie in the region –3 ≤ x,y ≤ 3.

Example of Run with GlobalSearch

To find several local minima of the problem described in Run the Solver using GlobalSearch, enter:

gs = GlobalSearch;
opts = optimset('Algorithm','interior-point');
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],...
    'options',opts);
[xming,fming,flagg,outptg,manyminsg] = run(gs,problem);

The output of the run (which varies, based on the random seed):

xming,fming,flagg,outptg,manyminsg
xming =
   -0.0898    0.7127

fming =
   -1.0316

flagg =
     1

outptg = 
                funcCount: 2245
         localSolverTotal: 8
       localSolverSuccess: 8
    localSolverIncomplete: 0
    localSolverNoSolution: 0
                  message: [1x137 char]

manyminsg = 
  1x4 GlobalOptimSolution

  Properties:
    X
    Fval
    Exitflag
    Output
    X0

Example of Run with MultiStart

To find several local minima of the problem described in Run the Solver using 50 runs of fmincon with MultiStart, enter:

% % Set the default stream to get exactly the same output
% s = RandStream('mt19937ar','Seed',14);
% RandStream.setDefaultStream(s);
ms = MultiStart;
opts = optimset('Algorithm','interior-point');
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],...
    'options',opts);
[xminm,fminm,flagm,outptm,manyminsm] = run(ms,problem,50);

The output of the run (which varies based on the random seed):

xminm,fminm,flagm,outptm

xminm =
   -0.0898    0.7127

fminm =
   -1.0316

flagm =
     1

outptm = 
                funcCount: 2035
         localSolverTotal: 50
       localSolverSuccess: 50
    localSolverIncomplete: 0
    localSolverNoSolution: 0
                  message: [1x128 char]

In this case, MultiStart located all six local minima, while GlobalSearch located four. For pictures of the MultiStart solutions, see Example: Visualizing the Basins of Attraction.

Back to Top

Using GlobalSearch and MultiStart

Examining Results

Free Optimization Interactive Kit

Learn how to use optimization to solve systems of equations, fit models to data, or optimize system performance.

Get free kit

Trials Available

Try the latest version of optimization products.

Get trial software