surrogateopt

Surrogate optimization for global minimization of time-consuming objective functions

The surrogateopt function is a global solver for time-consuming objective functions.

The solver searches for the global minimum of a real-valued objective function in multiple dimensions, subject to bound constraints. surrogateopt is best suited to objective functions that take a long time to evaluate. The objective function can be nonsmooth. The solver requires finite bounds on all variables. The solver can optionally maintain a checkpoint file to enable recovery from crashes or partial execution, or optimization continuation after meeting a stopping condition.

Syntax

x = surrogateopt(fun,lb,ub)

x = surrogateopt(fun,lb,ub,options)

x = surrogateopt(problem)

x = surrogateopt(checkpointFile)

x = surrogateopt(checkpointFile,opts)

[x,fval] = surrogateopt(___)

[x,fval,exitflag,output] = surrogateopt(___)

[x,fval,exitflag,output,trials] = surrogateopt(___)

Description

x = surrogateopt(fun,lb,ub) searches for a global minimum of fun(x) in the region lb <= x <= ub.

Note

Passing Extra Parameters (Optimization Toolbox) explains how to pass extra parameters to the objective function, if necessary.

x = surrogateopt(fun,lb,ub,options) modifies the search procedure using the options in options.

x = surrogateopt(problem) searches for a minimum for problem, a structure described in problem.

x = surrogateopt(checkpointFile) continues running the optimization from the state in a saved checkpoint file. See Work with Checkpoint Files.

x = surrogateopt(checkpointFile,opts) continues running the optimization from the state in a saved checkpoint file, and replaces options in checkpointFile with those in opts. See Checkpoint File.

[x,fval] = surrogateopt(___) also returns the best (smallest) value of the objective function found by the solver, using any of the input argument combinations in the previous syntaxes.

[x,fval,exitflag,output] = surrogateopt(___) also returns exitflag, an integer describing the reason the solver stopped, and output, a structure describing the optimization procedure.

[x,fval,exitflag,output,trials] = surrogateopt(___) also returns a structure containing all of the evaluated points and the objective function values at those points.

Examples

Search for Global Minimum

Search for a minimum of the six-hump camel back function in the region -2.1 <= x(i) <= 2.1. This function has two global minima with the objective function value -1.0316284... and four local minima with higher objective function values.

rng default % For reproducibility
fun = @(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);
lb = [-2.1,-2.1];
ub = -lb;
x = surrogateopt(fun,lb,ub)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

x = 1×2

   -0.0900    0.7129

Surrogate Optimization Using Nondefault Options

Minimize the six-hump camel back function in the region -2.1 <= x(i) <= 2.1. This function has two global minima with the objective function value -1.0316284... and four local minima with higher objective function values.

To search the region systematically, use a regular grid of starting points. Set 120 as the maximum number of function evaluations. Use the 'surrogateoptplot' plot function. To understand the 'surrogateoptplot' plot, see Interpret surrogateoptplot.

rng default % For reproducibility
fun = @(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);
lb = [-2.1,-2.1];
ub = -lb;
[Xpts,Ypts] = meshgrid(-3:3);
startpts = [Xpts(:),Ypts(:)];
options = optimoptions('surrogateopt','PlotFcn','surrogateoptplot',...
    'InitialPoints',startpts,'MaxFunctionEvaluations',120);
x = surrogateopt(fun,lb,ub,options)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

x = 1×2

   -0.0899    0.7132

Surrogate Optimization of Problem Structure

Create a problem structure representing the six-hump camel back function in the region -2.1 <= x(i) <= 2.1. Set 120 as the maximum number of function evaluations.

rng default % For reproducibility
fun = @(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);
options = optimoptions('surrogateopt','MaxFunctionEvaluations',120);
problem = struct('objective',fun,...
    'lb',[-2.1,-2.1],...
    'ub',[2.1,2.1],...
    'options',options,...
    'solver','surrogateopt');
x = surrogateopt(problem)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

x = 1×2

   -0.0930    0.7155

Return Surrogate Optimization Objective Function Value

Minimize the six-hump camel back function and return both the minimizing point and the objective function value. Set options to suppress all other display.

rng default % For reproducibility
fun = @(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);
lb = [-2.1,-2.1];
ub = -lb;
options = optimoptions('surrogateopt','Display','off','PlotFcn',[]);
[x,fval] = surrogateopt(fun,lb,ub,options)

x = 1×2

   -0.0900    0.7129

fval = -1.0316

Monitor Surrogate Optimization Process

Monitor the surrogate optimization process by requesting that surrogateopt return more outputs. Use the 'surrogateoptplot' plot function. To understand the 'surrogateoptplot' plot, see Interpret surrogateoptplot.

rng default % For reproducibility
fun = @(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);
lb = [-2.1,-2.1];
ub = -lb;
options = optimoptions('surrogateopt','PlotFcn','surrogateoptplot');
[x,fval,exitflag,output] = surrogateopt(fun,lb,ub,options)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

x = 1×2

   -0.0900    0.7129

fval = -1.0316

exitflag = 0

output = struct with fields:
       rngstate: [1x1 struct]
      funccount: 200
    elapsedtime: 103.1249
        message: 'Surrogateopt stopped because it exceeded the function evaluation limit set by ...'

Restart Surrogate Optimization

Conclude a surrogate optimization quickly by setting a small maximum number of function evaluations. To prepare for the possibility of restarting the optimization, request all solver outputs.

rng default % For reproducibility
fun = @(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);
lb = [-2.1,-2.1];
ub = -lb;
options = optimoptions('surrogateopt','MaxFunctionEvaluations',20);
[x,fval,exitflag,output,trials] = surrogateopt(fun,lb,ub,options);

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

Optimize for another 20 function evaluations, starting from the previously evaluated points.

options.InitialPoints = trials;
[x,fval,exitflag,output,trials] = surrogateopt(fun,lb,ub,options);

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

By comparing the plots of these 40 function evaluations to those in Search for Global Minimum, you see that restarting surrogate optimization is not the same as having the solver run continuously.

Restart Surrogate Optimization from Checkpoint File

To enable restarting surrogate optimization due to a crash or any other reason, set a checkpoint file name.

opts = optimoptions('surrogateopt','CheckpointFile','checkfile');

Create an optimization problem and set a small number of function evaluations.

rng default % For reproducibility
fun = @(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);
lb = [-2.1,-2.1];
ub = -lb;
opts.MaxFunctionEvaluations = 30;
[x,fval,exitflag,output] = surrogateopt(fun,lb,ub,opts)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

x = 1×2

    0.2575   -0.7963

fval = -0.8771

exitflag = 0

output = struct with fields:
       rngstate: [1×1 struct]
      funccount: 30
    elapsedtime: 8.6254
        message: 'Surrogateopt stopped because it exceeded the function evaluation limit set by ↵'options.MaxFunctionEvaluations'.'

Set options to use 100 function evaluations (which means 70 more than already done) and restart the optimization.

opts.MaxFunctionEvaluations = 100;
[x2,fval2,exitflag2,output2] = surrogateopt('checkfile',opts)

Surrogateopt stopped because it exceeded the function evaluation limit set by 
'options.MaxFunctionEvaluations'.

x2 = 1×2

    0.0900   -0.7130

fval2 = -1.0316

exitflag2 = 0

output2 = struct with fields:
       rngstate: [1×1 struct]
      funccount: 100
    elapsedtime: 41.1504
        message: 'Surrogateopt stopped because it exceeded the function evaluation limit set by ↵'options.MaxFunctionEvaluations'.'

Input Arguments

fun — Objective function

function handle | function name

Objective function, specified as a function handle or function name. fun accepts a single argument x, where x is a row vector, and returns a real scalar fval = fun(x).

Data Types: function_handle | char | string

lb — Lower bounds

finite real vector

Lower bounds, specified as a finite real vector. lb represents the lower bounds element-wise in lb ≤ x ≤ ub. The lengths of lb and ub must be equal to the number of variables that fun accepts.

Caution

Although lb is optional for most solvers, lb is a required input for surrogateopt.

Note

All entries in lb must be strictly less than the corresponding entries in ub.

Example: lb = [0;-20;4] means x(1) ≥ 0, x(2) ≥ -20, x(3) ≥ 4.

Data Types: double

ub — Upper bounds

finite real vector

Upper bounds, specified as a finite real vector. ub represents the upper bounds element-wise in lb ≤ x ≤ ub. The lengths of lb and ub must be equal to the number of variables that fun accepts.

Caution

Although ub is optional for most solvers, ub is a required input for surrogateopt.

Note

All entries in lb must be strictly less than the corresponding entries in ub.

Example: ub = [10;-20;4] means x(1) ≤ 10, x(2) ≤ -20, x(3) ≤ 4.

Data Types: double

options — Options

output of optimoptions

Options, specified as the output of optimoptions.

For more information, see Surrogate Optimization Options.

Option	Description	Values
CheckpointFile	File name for checkpointing and restarting optimization. The file has the .mat data type. See Work with Checkpoint Files. Checkpointing takes time. This overhead is especially noticeable for functions that otherwise take little time to evaluate.	File name or file path, given as a string or character array. The .mat extension is optional. If you specify a file name without a path, surrogateopt saves the checkpoint file in the current folder.
Display	Level of display returned at the command line.	'final' (default) — Exit message at the end of the iterations. 'off' or the equivalent 'none' — No display. 'iter' — Iterative display; see Command-Line Display.
InitialPoints	Initial points for solver.	Matrix of initial points, where each row is one point. Or, a structure with field X, whose value is a matrix of initial points, and optionally the field Fval, whose value is a vector containing the values of the objective function at the initial points. See Algorithm Control. Default: [].
MaxFunctionEvaluations	Maximum number of objective function evaluations, a stopping criterion.	Positive integer. Default is max(200,50*nvar), where nvar is the number of problem variables.
MaxTime	Maximum running time in seconds. The actual running time can exceed MaxTime because of the time required to evaluate an objective function or because of parallel processing delays.	Positive scalar. Default is Inf.
MinSampleDistance	Minimum distance between trial points generated by the adaptive sampler. See Surrogate Optimization Algorithm.	Positive scalar. Default is 1e-3.
MinSurrogatePoints	Minimum number of random sample points to create at the start of a surrogate creation phase. See Surrogate Optimization Algorithm.	Integer at least nvar + 1. Default is max(20,2*nvar), where nvar is the number of problem variables.
ObjectiveLimit	Tolerance on the objective function value. If a calculated objective function value is less than or equal to ObjectiveLimit, the algorithm stops.	Double scalar value. Default is -Inf.
OutputFcn	Output function to report on solver progress or to stop the solver. See Output Function.	Function handle or cell array of function handles. Default: [].
PlotFcn	Plot function to display solver progress or to stop solver. See Plot Function.	Function handle or cell array of function handles. Built-in plot functions are: @optimplotfval (default) — Plot the best objective function value found as a line plot. @optimplotx — Plot the best solution found as a bar chart. @surrogateoptplot — Plot the objective function value at each iteration, showing which phase of the algorithm produces the value and the best value found both in this phase and overall. See Interpret surrogateoptplot.
UseParallel	Boolean value indicating whether to compute objective function values in parallel.	Boolean. Default is false. For algorithmic details, see Parallel surrogateopt Algorithm.

Example: options = optimoptions('surrogateopt','Display','iter','UseParallel',true)

problem — Problem structure

structure

Problem structure, specified as a structure with the following fields:

• objective — Objective function

• lb — Lower bounds for x

• ub — Upper bounds for x

• solver — 'surrogateopt'

• options — Options created with optimoptions

• rngstate — Optional field to reset the state of the random number generator

Note

All fields in problem are required except rngstate.

Data Types: struct

checkpointFile — Path to checkpoint file

string | character vector

Path to a checkpoint file, specified as a string or character vector. If you specify a file name without a path, surrogateopt uses a checkpoint file in the current folder. The extension .mat is optional.

A checkpoint file stores the state of an optimization for resuming the optimization. surrogateopt updates the checkpoint file at each function evaluation, so you can resume the optimization even when surrogateopt halts prematurely. For an example, see Restart Surrogate Optimization from Checkpoint File.

surrogateopt creates a checkpoint file when it has a valid CheckpointFile option.

You can change some options when resuming from a checkpoint file. See opts.

The data in a checkpoint file is in .mat format. To avoid errors or other unexpected results, do not modify the data before calling surrogateopt.

Example: 'checkfile'

Example: "C:\Program Files\MATLAB\docs\checkpointNov2019.mat"

Data Types: char | string

opts — Options for resuming from checkpoint file

[] (default) | optimoptions options from a restricted set

Options for resuming optimization from the checkpoint file, specified as optimoptions options (from a restricted set) that you can change from the original options. The options you can change are:

• CheckpointFile

• Display

• MaxFunctionEvaluations

• MaxTime

• MinSurrogatePoints

• ObjectiveLimit

• OutputFcn

• PlotFcn

• UseParallel

Example: opts = optimoptions(options,'MaxFunctionEvaluations',400);

Output Arguments

x — Solution

real vector

Solution, returned as a real vector. x has the same length as lb and as ub.

fval — Objective function value at the solution

real number

Objective function value at the solution, returned as a real number. Generally, fval = fun(x).

exitflag — Reason surrogateopt stopped

integer

Reason surrogateopt stopped, returned as one of these integer values:

Exit Flag	Description
1	The objective function value is less than or equal to options.ObjectiveLimit.
0	The number of function evaluations exceeds options.MaxFunctionEvaluations or the elapsed time exceeds options.MaxTime.
-1	The optimization is terminated by an output function or plot function.
-2	No feasible point is found. A lower bound lb(i) exceeds a corresponding upper bound ub(i).

output — Information about the optimization process

structure

Information about the optimization process, returned as a structure with these fields:

• funccount — Total number of function evaluations.

• elapsedtime — Time spent running the solver in seconds, as measured by tic/toc.

• message — Reason why the algorithm stopped.

• rngstate — State of the MATLAB^® random number generator just before the algorithm starts. Use this field to reproduce your results. See Reproduce Results, which discusses using rngstate for ga.

trials — Points evaluated

structure

Points evaluated, returned as a structure with these fields:

• X — Matrix with nvars columns, where nvars is the length of lb or ub. Each row of X represents one point evaluated by surrogateopt.

• Fval — Column vector, where each entry is the objective function value of the corresponding row of X.

The trials structure has the same form as the options.InitialPoints structure. So, you can continue an optimization by passing the trials structure as the InitialPoints option.

Algorithms

surrogateopt repeatedly performs the following steps:

1. Create a set of trial points by sampling MinSurrogatePoints random points within the bounds, and evaluate the objective function at the trial points.

2. Create a surrogate model of the objective function by interpolating a radial basis function through all of the random trial points.

3. Create a merit function that gives some weight to the surrogate and some weight to the distance from trial points. Locate a small value of the merit function by randomly sampling the merit function in a region around the incumbent point (best point found since the last surrogate reset). Use this point, called the adaptive point, as a new trial point.

4. Evaluate the objective at the adaptive point, and update the surrogate based on this point and its value. Count a "success" if the objective function value is sufficiently lower than the previous best (lowest) value observed, and count a "failure" otherwise.

5. Update the dispersion of the sample distribution upwards if there are three successes before max(nvar,5) failures, where nvar is the number of dimensions. Update the dispersion downwards if there are max(nvar,5) failures before three successes.

6. Continue from step 3 until all trial points are within MinSampleDistance of the evaluated points. At that time, reset the surrogate by discarding all adaptive points from the surrogate, reset the scale, and go back to step 1 to create MinSurrogatePoints new random trial points for evaluation.

For details, see Surrogate Optimization 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.