SQOPT/SNOPT SQOPT/SNOPT Large-scale linear, quadratic, and nonlinear programming problems
This document describes two new software packages for constrained optimization (linear, quadratic and nonlinear programming). The software is maintained by research personnel at the University of California, San Diego and Stanford University. Here we give guidance on the choice of package and summarize the distribution procedure.
Optimization Software and Problem Types
SNOPT: Large-scale linear, quadratic and nonlinear programs.
SQOPT: Large-scale linear and quadratic programs (convex).
These packages are implemented in Fortran 77 and distributed as source code. They are intended for any machine with a reasonable amount of memory and a Fortran compiler. They may be called from a driver program (typically in Fortran, C or MATLAB). They can also be used as stand-alone packages, reading data in the MPS format used by commercial mathematical programming systems.
SQOPT is part of SNOPT, but is also available as a separate package. SQOPT forms part of the Optimization Chapter of the NAG Fortran library.
SNOPT is compatible with the SOL package MINOS at the top level.
Linear Programming
Given sufficient memory, SNOPT and SQOPT can process large LP models similar to those solved by commercial packages (notably OSL and CPLEX). It should be at least as reliable, though may be somewhat slower for a variety of reasons. (For example, it does not include a presolve feature to reduce the model size.) Warm starts are possible via basis files. For subroutine use, the sparse data structure allows simple in-core problem modification (e.g., within a specialized branch-and-bound algorithm).
Quadratic Programming
SNOPT is suitable for general large-scale QP problems. It is more efficient if only some of the variables appear quadratically in the objective, or if many constraints are active at a solution. If the quadratic is indefinite (not positive definite or semidefinite), the solution obtained may be a local optimum.
SQOPT is suitable for semidefinite problems. In this case, SQOPT will generally be more efficient than SNOPT.
Nonlinear Objective Functions
The SQP algorithm used by SNOPT is highly effective for problems with a nonlinear objective function and large numbers of sparse linear constraints. As with QP problems, efficiency is best if only some of the variables enter nonlinearly, or if the number of active constraints (including simple bounds) is nearly as large as the number of variables.
Nonlinear Constraints
SNOPT performs best if both function and gradient values can be provided. It uses an SQP algorithm (Sequential Quadratic Programming) in which a sequence of subproblems in which the constraints are linearized, and the objective is a quadratic approximation of a Lagrangian. (Hence, no function or gradient values are needed during the solution of each QP.)
SNOPT versus MINOS
SNOPT and MINOS are both general-purpose optimizers, designed to find locally optimal solutions for models involving smooth nonlinear functions. They are often more widely useful. (For example, local optima are often global solutions, and discontinuities in the function gradients can often be tolerated if they are not too close to an optimum.) Ideally, users should provide gradients. Unknown components are estimated by finite differences.
The algorithms used are significantly different. Both methods solve a sequence of subproblems in which the constraints are linearized. In SNOPT the objective is quadratic, in MINOS, the objective is a Lagrangian (involving all nonlinear functions).
The best choice of method depends mainly on the complexity of the model. For models of moderate size, the choice is not critical. Both methods take advantage of sparsity in the constraints. They are efficient and reliable for linear programs, and deal with nonlinear objective functions (and large numbers of linear constraints) with similar reliability.
We recommend MINOS if the objective and constraint functions are relatively inexpensive to evaluate, or if the problem is highly nonlinear. If the constraints are nonlinear, there is a good chance that a solution will be obtained, but no guarantee. In contrast, SNOPT generally requires fewer evaluations of the nonlinear functions, and convergence to a solution is assured for a large class of problems. Few general-purpose optimizers offer comparable reliability. In summary, we recommend SNOPT in the following cases:
Distribution Information
SQOPT and SNOPT are distributed at cost to bona-fide researchers and US Federal Government Agencies. Visit the homepage for Stanford Systems Optimization Laboratory Software, or contact:
Stanford Business Software, Inc. 2672 Bayshore Parkway, Suite 304 Mountain View, CA 94043 Phone: (415) 962-8719 Fax: (415) 962-1869 Contact: Ms Radhika Thapa Manager, Software Distribution
Portable Fortran 77 source code is provided for all machines (PC, Macintosh, workstations, mainframes) on DOS or Macintosh diskettes. Included are test problems and makefiles for DOS, Unix, and OpenVMS systems.
Specialized license agreements are available for applications involving resale of UCSD/SOL software as part of a larger package. For further information, please contact:
Luis Mejia mejia@leland.stanford.edu Office of Technology Licensing (415) 723-0651 Stanford University (415) 725-7295 Fax 900 Welch Road, Suite 350 Palo Alto, CA 94304-1850
Technical Support
For further information about the algorithms, please contact one of the following:
Philip Gill pgill@ucsd.edu Dept of Mathematics (619) 534-4879 University of California, San Diego La Jolla, CA 92093-0112 Walter Murray Walter@SOL-Walter.Stanford.edu Dept of Operations Research (415) 723-1307 Stanford University (415) 723-4107 Fax Stanford, CA 94305-4022 Michael Saunders Mike@SOL-Michael.Stanford.edu Dept of Operations Research (415) 723-1875 Stanford University (415) 723-4107 Fax Stanford, CA 94305-4022
[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]