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