SOL Logo

Systems Optimization Laboratory

Stanford University
Dept of Management Science and Engineering (MS&E)

Huang Engineering Center

Stanford, CA 94305-4121  USA

Constrained Optimization

Professors Walter Murray and Michael Saunders lead the SOL research program on constrained optimization, in close cooperation with Professor Philip Gill at UC San Diego. Numerical optimization involves fundamental research on mathematical methods for linear and nonlinear programming, as well as techniques for implementing the methods as efficient and reliable computer software. We have a special interest in algorithms for large-scale problems. Our general-purpose packages (MINOS, NPSOL, SNOPT, etc.) have been distributed to thousands of sites world-wide. Feedback from users brings about many fruitful collaborative efforts with industry, government and academia.

Algorithms

The algorithms implemented in SOL software include the simplex method for linear programs (all solvers), the reduced-gradient method (MINOS, for linear constraints), a projected Lagrangian method (MINOS, for nonlinear constraints), and SQP methods for linear and nonlinear constraints (NPSOL and SNOPT).

Active-set methods are employed for all problems or subproblems involving linear constraints. These generate search directions that stay on a certain subset of constraints (the working set). The corresponding constraint gradients form the "working-set matrix". This must be factorized to allow computation of search directions. Most of the work per iteration lies in updating the matrix factors and using them to compute the next search direction.

The dense solvers LSSOL, QPOPT and NPSOL employ orthogonal factors of the working-set matrix for maximum stability. For MINOS, SQOPT and SNOPT, the vital engine is LUSOL: a set of routines for computing sparse LU factors of a square or rectangular matrix. New factorizations are obtained using the Markowitz criterion to preserve sparsity, and "Threshold Partial Pivoting", "Threshold Rook Pivoting", or "Threshold Complete Pivoting" to preserve stability. The LU factors are updated in a sparse and stable way by the Bartels-Golub-Reid method.

Software

SOL's optimization software is available as portable Fortran 77 source code for PCs, workstations, and mainframes. Problem types are: large-scale linear and nonlinear programs (MINOS, SNOPT), large-scale quadratic programs (SQOPT), dense nonlinear programs (NPSOL), and dense linear and quadratic programs (LSSOL, QPOPT).


Contact Stanford Business Software Inc. for additional information.

Applications

SOL optimization software has been applied in many areas of engineering, economics, finance, forestry, etc. Example include: design of both yachts in the 1995 America's Cup final; online control of transmission networks for electricity and gas; prediction of oil prices by the Federal Reserve; climate modeling for the greenhouse debate; determination of forces on the thigh bone prior to prosthesis insertion; trajectory optimization for aircraft and spacecraft, including optimal control of the DC-X experimental single-stage VTOL rocket.

Applications of NPSOL

Applications of SNOPT