Main Content

Choosing the Algorithm

fmincon Algorithms

fmincon has five algorithm options:

  • 'interior-point' (default)

  • 'trust-region-reflective'

  • 'sqp'

  • 'sqp-legacy'

  • 'active-set'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

  • Use the 'interior-point' algorithm first.

    For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

  • To run an optimization again to obtain more speed on small- to medium-sized problems, try 'sqp' next, and 'active-set' last.

  • Use 'trust-region-reflective' when applicable. Your problem must have: objective function includes gradient, only bounds, or only linear equality constraints (but not both).

See Potential Inaccuracy with Interior-Point Algorithms.

Reasoning Behind the Recommendations

  • 'interior-point' handles large, sparse problems, as well as small dense problems. The algorithm satisfies bounds at all iterations, and can recover from NaN or Inf results. It is a large-scale algorithm; see Large-Scale vs. Medium-Scale Algorithms. The algorithm can use special techniques for large-scale problems. For details, see Interior-Point Algorithm in fmincon options.

  • 'sqp' satisfies bounds at all iterations. The algorithm can recover from NaN or Inf results. It is not a large-scale algorithm; see Large-Scale vs. Medium-Scale Algorithms.

  • 'sqp-legacy' is similar to 'sqp', but usually is slower and uses more memory.

  • 'active-set' can take large steps, which adds speed. The algorithm is effective on some problems with nonsmooth constraints. It is not a large-scale algorithm; see Large-Scale vs. Medium-Scale Algorithms.

  • 'trust-region-reflective' requires you to provide a gradient, and allows only bounds or linear equality constraints, but not both. Within these limitations, the algorithm handles both large sparse problems and small dense problems efficiently. It is a large-scale algorithm; see Large-Scale vs. Medium-Scale Algorithms. The algorithm can use special techniques to save memory usage, such as a Hessian multiply function. For details, see Trust-Region-Reflective Algorithm in fmincon options.

For descriptions of the algorithms, see Constrained Nonlinear Optimization Algorithms.

fsolve Algorithms

fsolve has three algorithms:

  • 'trust-region-dogleg' (default)

  • 'trust-region'

  • 'levenberg-marquardt'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

  • Use the 'trust-region-dogleg' algorithm first.

    For help if fsolve fails, see When the Solver Fails or When the Solver Might Have Succeeded.

  • To solve equations again if you have a Jacobian multiply function, or want to tune the internal algorithm (see Trust-Region Algorithm in fsolve options), try 'trust-region'.

  • Try timing all the algorithms, including 'levenberg-marquardt', to find the algorithm that works best on your problem.

Reasoning Behind the Recommendations

  • 'trust-region-dogleg' is the only algorithm that is specially designed to solve nonlinear equations. The others attempt to minimize the sum of squares of the function.

  • The 'trust-region' algorithm is effective on sparse problems. It can use special techniques such as a Jacobian multiply function for large-scale problems.

For descriptions of the algorithms, see Equation Solving Algorithms.

fminunc Algorithms

fminunc has two algorithms:

  • 'quasi-newton' (default)

  • 'trust-region'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

  • If your objective function includes a gradient, use 'Algorithm' = 'trust-region', and set the SpecifyObjectiveGradient option to true.

  • Otherwise, use 'Algorithm' = 'quasi-newton'.

For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

For descriptions of the algorithms, see Unconstrained Nonlinear Optimization Algorithms.

Least Squares Algorithms

lsqlin

lsqlin has three algorithms:

  • 'interior-point', the default

  • 'trust-region-reflective'

  • 'active-set'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

  • Try 'interior-point' first.

    Tip

    For better performance when your input matrix C has a large fraction of nonzero entries, specify C as an ordinary double matrix. Similarly, for better performance when C has relatively few nonzero entries, specify C as sparse. For data type details, see Sparse Matrices. You can also set the internal linear algebra type by using the 'LinearSolver' option.

  • If you have no constraints or only bound constraints, and want higher accuracy, more speed, or want to use a Jacobian Multiply Function with Linear Least Squares, try 'trust-region-reflective'.

  • If you have a large number of linear constraints and not a large number of variables, try 'active-set'.

For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

See Potential Inaccuracy with Interior-Point Algorithms.

For descriptions of the algorithms, see Least-Squares (Model Fitting) Algorithms.

lsqcurvefit and lsqnonlin

lsqcurvefit and lsqnonlin have three algorithms:

  • 'trust-region-reflective' (default for unconstrained or bound-constrained problems)

  • 'levenberg-marquardt'

  • 'interior-point' (default for problems with linear or nonlinear constraints)

Use optimoptions to set the Algorithm option at the command line.

Recommendations

  • For problems with bound constraints only, try 'trust-region-reflective' or 'levenberg-marquardt' first.

  • If your bound-constrained problem is underdetermined (fewer equations than dimensions), try 'levenberg-marquardt' first.

  • If your problem has linear or nonlinear constraints, use 'interior-point'.

For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

For descriptions of the algorithms, see Least-Squares (Model Fitting) Algorithms.

Linear Programming Algorithms

linprog has four algorithms:

  • 'dual-simplex-highs', the default

  • 'dual-simplex-legacy'

  • 'interior-point'

  • 'interior-point-legacy'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

Use the 'dual-simplex-highs' algorithm, the 'dual-simplex-legacy' algorithm, or the 'interior-point' algorithm first. It is difficult to know which algorithm will work more effectively on a problem.

For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

See Potential Inaccuracy with Interior-Point Algorithms.

Reasoning Behind the Recommendations

  • Often, the 'dual-simplex-highs', 'dual-simplex-legacy', and 'interior-point' algorithms are fast, and use relatively little memory.

  • The 'interior-point-legacy' algorithm is similar to 'interior-point', but 'interior-point-legacy' can be slower, less robust, or use more memory.

For descriptions of the algorithms, see Linear Programming Algorithms.

Mixed-Integer Linear Programming Algorithms

intlinprog has two algorithms:

  • 'highs', the default

  • 'legacy'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

Use the 'highs' algorithm first.

For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

Reasoning Behind the Recommendations

  • Often, the 'highs' algorithm works faster or more successfully than the 'legacy' algorithm.

  • The 'highs' algorithm has many fewer tuning options. Therefore, you have fewer choices to make when solving a problem.

  • The 'legacy' algorithm will be removed in a future release.

For descriptions of the algorithms, see Mixed-Integer Linear Programming (MILP) Algorithms.

Quadratic Programming Algorithms

quadprog has three algorithms:

  • 'interior-point-convex' (default)

  • 'trust-region-reflective'

  • 'active-set'

Use optimoptions to set the Algorithm option at the command line.

Recommendations

  • If you have a convex problem, or if you don't know whether your problem is convex, use 'interior-point-convex'.

  • Tip

    For better performance when your Hessian matrix H has a large fraction of nonzero entries, specify H as an ordinary double matrix. Similarly, for better performance when H has relatively few nonzero entries, specify H as sparse. For data type details, see Sparse Matrices. You can also set the internal linear algebra type by using the 'LinearSolver' option.

  • If you have a nonconvex problem with only bounds, or with only linear equalities, use 'trust-region-reflective'.

  • If you have a positive semidefinite problem with a large number of linear constraints and not a large number of variables, try 'active-set'.

For help if the minimization fails, see When the Solver Fails or When the Solver Might Have Succeeded.

See Potential Inaccuracy with Interior-Point Algorithms.

For descriptions of the algorithms, see Quadratic Programming Algorithms.

Large-Scale vs. Medium-Scale Algorithms

An optimization algorithm is large scale when it uses linear algebra that does not need to store, nor operate on, full matrices. This may be done internally by storing sparse matrices, and by using sparse linear algebra for computations whenever possible. Furthermore, the internal algorithms either preserve sparsity, such as a sparse Cholesky decomposition, or do not generate matrices, such as a conjugate gradient method.

In contrast, medium-scale methods internally create full matrices and use dense linear algebra. If a problem is sufficiently large, full matrices take up a significant amount of memory, and the dense linear algebra may require a long time to execute.

Don't let the name “large scale” mislead you; you can use a large-scale algorithm on a small problem. Furthermore, you do not need to specify any sparse matrices to use a large-scale algorithm. Choose a medium-scale algorithm to access extra functionality, such as additional constraint types, or possibly for better performance.

Potential Inaccuracy with Interior-Point Algorithms

Interior-point algorithms in fmincon, quadprog, lsqlin, and linprog have many good characteristics, such as low memory usage and the ability to solve large problems quickly. However, their solutions can be slightly less accurate than those from other algorithms. The reason for this potential inaccuracy is that the (internally calculated) barrier function keeps iterates away from inequality constraint boundaries.

For most practical purposes, this inaccuracy is usually quite small.

To reduce the inaccuracy, try to:

  • Rerun the solver with smaller StepTolerance, OptimalityTolerance, and possibly ConstraintTolerance tolerances (but keep the tolerances sensible.) See Tolerances and Stopping Criteria).

  • Run a different algorithm, starting from the interior-point solution. This can fail, because some algorithms can use excessive memory or time, and all linprog and some quadprog algorithms do not accept an initial point.

For example, try to minimize the function x when bounded below by 0. Using the fmincon default interior-point algorithm:

options = optimoptions(@fmincon,'Algorithm','interior-point','Display','off');
x = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x =

   2.0000e-08

Using the fmincon sqp algorithm:

options.Algorithm = 'sqp';
x2 = fmincon(@(x)x,1,[],[],[],[],0,[],[],options)
x2 =

   0

Similarly, solve the same problem using the linprog interior-point-legacy algorithm:

opts = optimoptions(@linprog,'Display','off','Algorithm','interior-point-legacy');
x = linprog(1,[],[],[],[],0,[],1,opts)
x =

   2.0833e-13

Using the linprog dual-simplex algorithm:

opts.Algorithm = 'dual-simplex';
x2 = linprog(1,[],[],[],[],0,[],1,opts)
x2 =

     0

In these cases, the interior-point algorithms are less accurate, but the answers are quite close to the correct answer.

Related Topics