Skip to main content Skip to secondary navigation

Constrained Optimization

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.


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.


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