Solver Algorithms and AutoSelect

When you use the functions Find, Minerr, Minimize, and Maximize, the AutoSelect feature automatically determines the kind of problem you are solving and attempts appropriate solving algorithms until one of the methods converges. To see which algorithm was used:

1. Right-click on the function to bring up the menu.

2. AutoSelect and one of the following methods are checked:

   • Linear

   • Nonlinear: Conjugate Gradient

   • Nonlinear: Quasi-Newton

   • Nonlinear: Levenberg-Marquardt

   • Quadratic: Solving and Optimization Extension Pack (SOEP) only

AutoSelect is used by default. If the problem is linear, the Linear method is applied. If Quadratic, the Quadratic method is used (if the Solving and Optimization Extension Pack is installed). If the problem calls for a nonlinear solver, AutoSelect uses the Conjugate Gradient solver; if that fails to converge, the Levenberg-Marquardt solver; if that too fails, the Quasi-Newton solver. These methods use different algorithms to determine the curvature and direction in which the search is to proceed.

Although it is usually convenient to have AutoSelect turned on, you can right-click the function and choose a specific method from the menu if necessary.

Algorithm Descriptions

Linear Method

Linear - a simplex method with branch/bound techniques. The guess values, while required, have no effect on the solution values, as the simplex method does not iterate starting with a guess value. In the case of a problem whose solution is an array, the guess value for the array indicates the size of the solution. The Linear option does not use the built-in variable TOL when solving.

Nonlinear Methods

All methods for nonlinear minimization are iterative. They require the following information:

1. A gradient direction given by the Jacobian matrix of estimated first derivatives.
2. A step size to move in the gradient direction.

In addition, the algorithm must examine the Hessian matrix (2nd derivatives) to determine if the solution is converging towards a minimum, maximum or a saddle point.

Nonlinear: Levenberg-Marquardt – The MINPACK algorithm is the basis of the L-M solver, which is a variant on the quasi-Newton method. It attempts to find the zeros of, or, at worst, minimize the sum of squares of the errors in the constraints. For this reason you get better performance from the L-M method by expressing your system as the vector of residuals set equal to zero, rather than summing and squaring the error in the Solve Block.

Modifications to the MINPACK routine: The first time the solver stops at a point that is not a solution, a small random amount is added to all the variables, and the solver restarts, similar to the Conjugate Gradient method. This helps avoid getting stuck in local minima. L-M does this only once per solve, the first time the solver stops on a point that is not a solution. If the system includes inequality constraints, the subsystem consisting of only the inequalities is solved first before adding in the equality constraints. This is equivalent to moving the guesses into an area where the inequalities are all satisfied.

Nonlinear: Conjugate Gradient – The generalized reduced-gradient method generates search directions without storing a Hessian matrix, and is useful in circumstances where matrix factorization is not viable because the matrix is too large or too dense. The termination criterion uses restarting with the steepest-descent direction, and can be useful if the problem has discontinuities or very flat regions.

Nonlinear: Quasi-Newton – Newton-type methods use the curvature information provided by the Hessian matrix, creating a local quadratic model of the objective function to determine search direction. Quasi-Newton methods build up curvature information as the iterations calculating direction of descent proceed.

Convergence rates for the above three methods vary, as does the ability of the solver to converge, depending on the steepness of the objective function. As the gradient becomes shallow near the minimum, increasingly many steps are needed to slide down to the minimum. Linear methods are good far away from the minimum (when the gradient is steep) but are less efficient near a minimum. On the other hand quadratic methods are very sensitive to guess values and time-consuming.

Algorithms in between these two extremes implement different logic to come up with a good step size while avoiding updating the Jacobian at every step. L-M is one such method. It can be thought of as a linear method far way from a minimum and as near-quadratic near the minimum while continuously and smoothly updating the step size.

Quadratic (SOEP only) – A quadratic program is one in which the objective function contains linear and quadratic terms or cross-terms, and uses a modified simplex method with branch/bound techniques. The guess values, while required, have no effect on the solution values, as the simplex method does not iterate starting with a guess value. In the case of a problem whose solution is an array, the guess value for the array indicates the size of the solution. The Quadratic option does not use the built-in variable TOL when solving.

Nonlinear methods terminate when the errors are less than TOL and CTOL, or when the direction of search, based on the gradient of the objective function, is less than TOL (no preferred search direction), or when a maximum number of iterations is reached. They also terminate when roundoff errors make it unlikely that further computation would increase accuracy of the solution, typically when TOL is set to a value below 10⁻¹⁵. After the termination criteria are met, if the final error for each of the equations is less than TOL, an answer is returned, and the value of the sum of squares of the errors is assigned to the internal variable ERR. If not, an error is returned. In these cases, you may wish to try Minerr, which returns a value even if the solver did not converge to a sufficiently small answer.

Notes:

• If you have trouble finding a solution:

  • Try a different guess value or add an inequality constraint. Provide a complex guess value if you are solving for a complex solution.
  • Use Minerr instead of Find to reach an approximate solution.
  • Try a different value of TOL or CTOL.
  • Try adjusting the Advanced Options from the right-click menu for the C-G or Quasi-Newton methods. If it's not clear which is the profitable search direction, for example, if the objective function's surface is nearly flat, or has discontinuities, the "central differences" choice on the Advanced tab may provide extra accuracy from the derivative, since the numerical estimate is taken symmetrically around the current guess rather than all to one side of the guess ("forward differences"). Other options may also be tried.

• For systems having more than one solution, the solution returned depends on the guess values. Adding inequalities may also force the solver to find a different solution.

• The ERR built-in variable gives the error for the system as a whole. There is no built-in variable for determining the size of the error for individual solutions to the unknowns.

• If you have the SOEP, and are solving linear or quadratic programming problems, you can use mixed integer programming, which allows you to force solutions to be integers or binary numbers.

QuickSheet

References

User's Guide to Minpack I.  More, Jorge J., Burton S. Garbow, and Kenneth E. Hillstrom, Argonne National Laboratory publication ANL-80-74, 1980.

Numerical Recipes in C.  Press, W. H., W. T. Flannery, S. A. Teukolsky, and B. P. Vetterling, New York: Cambridge University Press, 1992.

Optimization – Algorithms and Consistent Approximations. Polak, E., New York: Springer-Verlag, 1997.

Operations Research: Applications and Algorithms. Winston, W., Belmont: Wadsworth, 1994.

Practical Optimization. Gill, P., W. Murray, and M. Wright, San Diego: Academic Press, 1981.

Solver.com, Frontline Systems.