SOL -- Constrained Optimization

Constrained Optimization

Department of MS&E
Stanford University

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 either "Threshold Partial Pivoting" or "Threshold Complete Pivoting" to preserve stability. The LU factors are updated in a stable way by a sparse form of the method of Bartels and Golub.

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).

Please 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 MINOS

AMPL Review from OR/MS Today 12/93 (see "Using AMPL")
Branch and bound for global nonlinear optimization (1995 Thesis)
Automated tool for air traffic control scenarios (see "Linear Programming")
Northern Telecom improves quality (May 93)
Santa Barbara uses optimization for water-supply management (ongoing study)

Applications of NPSOL

America's Cup 1995 (Yacht Design)
NPSOL was used in different ways by both AC95 finalists. For Team Dennis Conner (U.S.), NPSOL was used in conjunction with Boeing's TRANAIR CFD system for optimal hull design of Young America. For Team New Zealand, Andrew Philpott (University of Auckland) used NPSOL to maximize the velocity around the course of 11 potential hull designs. One design appeared significantly faster and was chosen to become the New Zealand boat Black Magic.
NASA: Aerodynamic Optimization for High Speed Civil Aircraft (HSCA)
Protein Folding (Fall 1992)
Aircraft Configuration Optimization
Aircraft Design
Interplanetary Trajectories, Mars Mission Research Center (North Carolina State University, 1994)
Aircraft Design (Rutgers, 1995)
Prescription Retrieval (Hubble telescope pictures)
Chemical Engineering at UT

Applications of SNOPT

Also of Interest

[SOL Home] [MS&E Home] [Stanford University]

Updated: 17 Jan 2001