SNOPT: An SQP Algorithm for Large-Scale Constrained Optimization
Philip E. Gill, Walter Murray, Michael A. Saunders · SIAM Review · 2005
Sequential quadratic programming (SQP) methods have proved highly effective for solving constrained optimization problems with smooth nonlinear functions in the objective and constraints. Here we consider problems with general inequality constraints (linear and nonlinear). We assume that first derivatives are available and that the constraint gradients are sparse. Second derivatives are assumed to be unavailable or too expensive to calculate. We discuss an SQP algorithm that uses a smooth augmented Lagrangian merit function and makes explicit provision for infeasibility in the original problem and the QP subproblems. The Hessian of the Lagrangian is approximated using a limited-memory quasi-Newton method. SNOPT is a particular implementation that uses a reduced-Hessian semidefinite QP solver (SQOPT) for the QP subproblems. It is designed for problems with many thousands of constraints and variables but is best suited for problems with a moderate number of degrees of freedom (say, up to 2000). Numerical results are given for most of the CUTEr and COPS test collections (about 1020 examples of all sizes up to 40000 constraints and variables, and up to 20000 degrees of freedom).
Cited by 2,834 works. doi:10.1137/s0036144504446096
Authors
References
- Practical optimization
- Practical methods of optimization
- Numerical Optimization
- On the limited memory BFGS method for large scale optimization
- LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
- A Limited Memory Algorithm for Bound Constrained Optimization
- Solution of Sparse Indefinite Systems of Linear Equations
- Large-scale linearly constrained optimization
- Trust Region Methods
- Benchmarking optimization software with performance profiles