Global Optimization Toolbox Solver Characteristics

Solver Choices

This section describes Global Optimization Toolbox solver characteristics. The section includes recommendations for obtaining results more effectively.

To achieve better or faster solutions, first try tuning the recommended solvers by setting appropriate options or bounds. If the results are unsatisfactory, try other solvers.

Desired Solution	Smooth Objective and Constraints	Nonsmooth Objective or Constraints
Explanation of “Desired Solution”	Choosing Between Solvers for Smooth Problems	Choosing Between Solvers for Nonsmooth Problems
Single local solution	Optimization Toolbox™ functions; see Optimization Decision Table	fminbnd, patternsearch, fminsearch, ga, particleswarm, simulannealbnd, surrogateopt
Multiple local solutions	GlobalSearch, MultiStart	patternsearch, ga, particleswarm, simulannealbnd, or surrogateopt started from multiple initial points x0 or from multiple initial populations
Single global solution	GlobalSearch, MultiStart, patternsearch, particleswarm, ga, simulannealbnd, surrogateopt	patternsearch, ga, particleswarm, simulannealbnd, surrogateopt
Single local solution using parallel processing	MultiStart, Optimization Toolbox functions	patternsearch, ga, particleswarm, surrogateopt
Multiple local solutions using parallel processing	MultiStart	patternsearch, ga, or particleswarm started from multiple initial points x0 or from multiple initial populations
Single global solution using parallel processing	MultiStart	patternsearch, ga, particleswarm, surrogateopt

Explanation of “Desired Solution”

To understand the meaning of the terms in “Desired Solution,” consider the example

f(x)=100x²(1–x)²–x,

which has local minima x1 near 0 and x2 near 1:

 Code for generating the figure

fplot(@(x)100*x^2*(1-x)^2 - x,[-0.2,1.2])
ylabel('f(x)')
xlabel('x')
title('100 x^2 (1 - x)^2 - x')
hold on
plot([0 0],[-1.7 0],'r--')
plot([1 1],[-1.7 -1],'r--')
annotation('textbox',[0.25 0.1 0.07 0.1],...
    'String',{'x1'},'EdgeColor','none');
annotation('textbox',[0.8 0.1 0.07 0.1],...
    'String',{'x2'},'EdgeColor','none');
hold off

The minima are located at:

fun = @(x)(100*x^2*(x - 1)^2 - x);
x1 = fminbnd(fun,-0.1,0.1)
x1 =
    0.0051

x2 = fminbnd(fun,0.9,1.1)
x2 =
    1.0049

Description of the Terms

Term	Meaning
Single local solution	Find one local solution, a point x where the objective function f(x) is a local minimum. For more details, see Local vs. Global Optima. In the example, both x1 and x2 are local solutions.
Multiple local solutions	Find a set of local solutions. In the example, the complete set of local solutions is {x1,x2}.
Single global solution	Find the point x where the objective function f(x) is a global minimum. In the example, the global solution is x2.

Choosing Between Solvers for Smooth Problems

• Single Global Solution

• Multiple Local Solutions

Single Global Solution

1. Try GlobalSearch first. It is most focused on finding a global solution, and has an efficient local solver, fmincon.

2. Try MultiStart next. It has efficient local solvers, and can search a wide variety of start points.

3. Try patternsearch next. It is less efficient, since it does not use gradients. However, patternsearch is robust and is more efficient than the remaining local solvers To search for a global solution, start patternsearch from a variety of start points.

4. Try surrogateopt next. surrogateopt attempts to find a global solution using the fewest objective function evaluations. surrogateopt has more overhead per function evaluation than most other solvers. surrogateopt requires finite bounds, and accepts integer constraints, linear constraints, and nonlinear inequality constraints.

5. Try particleswarm next, if your problem is unconstrained or has only bound constraints. Usually, particleswarm is more efficient than the remaining solvers, and can be more efficient than patternsearch.

6. Try ga next. It can handle all types of constraints, and is usually more efficient than simulannealbnd.

7. Try simulannealbnd last. It can handle problems with no constraints or bound constraints. simulannealbnd is usually the least efficient solver. However, given a slow enough cooling schedule, it can find a global solution.

Multiple Local Solutions

GlobalSearch and MultiStart both provide multiple local solutions. For the syntax to obtain multiple solutions, see Multiple Solutions. GlobalSearch and MultiStart differ in the following characteristics:

• MultiStart can find more local minima. This is because GlobalSearch rejects many generated start points (initial points for local solution). Essentially, GlobalSearch accepts a start point only when it determines that the point has a good chance of obtaining a global minimum. In contrast, MultiStart passes all generated start points to a local solver. For more information, see GlobalSearch Algorithm.

• MultiStart offers a choice of local solver: fmincon, fminunc, lsqcurvefit, or lsqnonlin. The GlobalSearch solver uses only fmincon as its local solver.

• GlobalSearch uses a scatter-search algorithm for generating start points. In contrast, MultiStart generates points uniformly at random within bounds, or allows you to provide your own points.

• MultiStart can run in parallel. See How to Use Parallel Processing in Global Optimization Toolbox.

Choosing Between Solvers for Nonsmooth Problems

Choose the applicable solver with the lowest number. For problems with integer constraints, use ga.

1. Use fminbnd first on one-dimensional bounded problems only. fminbnd provably converges quickly in one dimension.

2. Use patternsearch on any other type of problem. patternsearch provably converges, and handles all types of constraints.

3. Try surrogateopt for problems that have time-consuming objective functions. surrogateopt searches for a global solution. surrogateopt requires finite bounds, and accepts integer constraints, linear constraints, and nonlinear inequality constraints.

4. Try fminsearch next for low-dimensional unbounded problems. fminsearch is not as general as patternsearch and can fail to converge. For low-dimensional problems, fminsearch is simple to use, since it has few tuning options.

5. Try particleswarm next on unbounded or bound-constrained problems. particleswarm has little supporting theory, but is often an efficient algorithm.

6. Try ga next. ga has little supporting theory and is often less efficient than patternsearch or particleswarm. ga handles all types of constraints. ga and surrogateopt are the only Global Optimization Toolbox solvers that accept integer constraints.

7. Try simulannealbnd last for unbounded problems, or for problems with bounds. simulannealbnd provably converges only for a logarithmic cooling schedule, which is extremely slow. simulannealbnd takes only bound constraints, and is often less efficient than ga.

Solver Characteristics

Solver	Convergence	Characteristics
GlobalSearch	Fast convergence to local optima for smooth problems	Deterministic iterates
		Gradient-based
		Automatic stochastic start points
		Removes many start points heuristically
MultiStart	Fast convergence to local optima for smooth problems	Deterministic iterates
		Can run in parallel; see How to Use Parallel Processing in Global Optimization Toolbox
		Gradient-based
		Stochastic or deterministic start points, or combination of both
		Automatic stochastic start points
		Runs all start points
		Choice of local solver: fmincon, fminunc, lsqcurvefit, or lsqnonlin
patternsearch	Proven convergence to local optimum; slower than gradient-based solvers	Deterministic iterates
		Can run in parallel; see How to Use Parallel Processing in Global Optimization Toolbox
		No gradients
		User-supplied start point
surrogateopt	Proven convergence to global optimum for bounded problems; slower than gradient-based solvers; generally stops by reaching a function evaluation limit or other limit	Stochastic iterates
		Can run in parallel; see How to Use Parallel Processing in Global Optimization Toolbox
		Best used for time-consuming objective functions
		Requires bound constraints, accepts linear constraints and nonlinear inequality constraints
		Allows integer constraints; see Mixed-Integer Surrogate Optimization
		No gradients
		Automatic start points or user-supplied points, or a combination of both
particleswarm	No convergence proof	Stochastic iterates
		Can run in parallel; see How to Use Parallel Processing in Global Optimization Toolbox
		Population-based
		No gradients
		Automatic start population or user-supplied population, or a combination of both
		Only bound constraints
ga	No convergence proof	Stochastic iterates
		Can run in parallel; see How to Use Parallel Processing in Global Optimization Toolbox
		Population-based
		No gradients
		Allows integer constraints; see Mixed Integer ga Optimization
		Automatic start population or user-supplied population, or a combination of both
simulannealbnd	Proven to converge to global optimum for bounded problems with very slow cooling schedule	Stochastic iterates
		No gradients
		User-supplied start point
		Only bound constraints

Explanation of some characteristics:

• Convergence — Solvers can fail to converge to any solution when started far from a local minimum. When started near a local minimum, gradient-based solvers converge to a local minimum quickly for smooth problems. patternsearch provably converges for a wide range of problems, but the convergence is slower than gradient-based solvers. Both ga and simulannealbnd can fail to converge in a reasonable amount of time for some problems, although they are often effective.

• Iterates — Solvers iterate to find solutions. The steps in the iteration are iterates. Some solvers have deterministic iterates. Others use random numbers and have stochastic iterates.

• Gradients — Some solvers use estimated or user-supplied derivatives in calculating the iterates. Other solvers do not use or estimate derivatives, but use only objective and constraint function values.

• Start points — Most solvers require you to provide a starting point for the optimization in order to obtain the dimension of the decision variables. ga and surrogateopt do not require any starting points, because they take the dimension of the decision variables as an input or infer dimensions from bounds. These solvers generate a start point or population automatically, or they accept a point or points that you supply.

Compare the characteristics of Global Optimization Toolbox solvers to Optimization Toolbox solvers.

Solver	Convergence	Characteristics
fmincon, fminunc, fseminf, lsqcurvefit, lsqnonlin	Proven quadratic convergence to local optima for smooth problems	Deterministic iterates
		Gradient-based
		User-supplied starting point
fminsearch	No convergence proof — counterexamples exist.	Deterministic iterates
		No gradients
		User-supplied start point
		No constraints
fminbnd	Proven convergence to local optima for smooth problems, slower than quadratic.	Deterministic iterates
		No gradients
		User-supplied start interval
		Only one-dimensional problems

All these Optimization Toolbox solvers:

• Have deterministic iterates

• Require a start point or interval

• Search just one basin of attraction

Why Are Some Solvers Objects?

GlobalSearch and MultiStart are objects. What does this mean for you?

• You create a GlobalSearch or MultiStart object before running your problem.

• You can reuse the object for running multiple problems.

• GlobalSearch and MultiStart objects are containers for algorithms and global options. You use these objects to run a local solver multiple times. The local solver has its own options.

For more information, see the Classes documentation.