SNOPT

SNOPT (invented by Philip Gill, Walter Murray and Michael Saunders) is a software package for solving large-scale optimization problems (linear and nonlinear programs). It is especially effective for nonlinear problems whose functions and gradients are expensive to evaluate. The functions should be smooth but need not be convex.

For linear programs, SNOPT uses a sparse implementation of the primal simplex method, equivalent to that in MINOS.

For nonlinear problems, SNOPT employs a sparse SQP algorithm with limited-memory quasi-Newton approximations to the Hessian of Lagrangian. An augmented Lagrangian merit function promotes convergence from an arbitrary point.

SNOPT make use of nonlinear function and gradient values. The solution obtained will be a local optimum (which may or may not be a global optimum). If some of the gradients are unknown, they will be estimated by finite differences. Infeasible problems are treated methodically via elastic bounds. SNOPT allows the nonlinear constraints to be violated (if necessary) and minimizes the sum of such violations.

For large problems, efficiency is improved if only some of the variables enter nonlinearly, or if the number of active constraints is nearly as large as the number of variables (i.e., if there are few degrees of freedom at a solution). SNOPT can accommodate problems with many degrees of freedom (perhaps one or two thousand), but a few hundred or less is preferable.

SNOPT is highly effective for problems with a nonlinear objective function and large numbers of sparse linear constraints (as well as bounds on the variables). MINOS may be more efficient than SNOPT if the objective and its gradients are cheap to evaluate (though the difference is usually not great).

SNOPT is suitable for general QP problems (but may find just a local optimum if the quadratic is indefinite). LSSOL and QPOPT are suitable for LP and QP problems of arbitrary size if the constraint matrix is essentially dense, but the sparse solvers MINOS and SNOPT will usually be more efficient even for dense problems.