SPRNLP and SOCS SPRNLP and SOCS Sparse and Dense Nonlinear Programming, Sparse Nonlinear Least Squares, Sparse Optimal Control
Sparse NLP and Sparse Least Squares
The basis of the SPRNLP software is a sequential quadratic programming algorithm for sparse nonlinear programming problems. The basic method is capable of solving problems with nonlinear equality and inequality constraints, simple variable bounds, and either general or nonlinear least squares objective functions. The sparsity pattern of the Hessian and Jacobian matrices is defined by the user. The software employs a reverse communication format, and the user must provide Jacobian and Hessian information when requested.
The underlying SQP method is designed to utilize second order information, and incorporates a Levenberg modification strategy to insure the projected Hessian is positive definite. The quadratic programming subproblem is solved using a Schur-complement QP algorithm proposed by Gill, Murray, Saunders, and Wright. The Schur-complement method relies on the efficient solution of a sparse symmetric indefinite Kuhn-Tucker (KT) system, which is achieved using the multifrontal method. The linear algebra software was developed at Boeing and incorporates an exhaustive explicit pivoting strategy for stability.
Four options control the behavior of the nonlinear programming method. The default option (``FM'') first locates a feasible point and then minimizes the objective. The second option ``M'' proceeds directly from the user supplied initial guess to the constrained optimal solution. Option ``F'' can be used to locate a feasible (and suboptimal) point. Option ``FME'' first locates a feasible point and then maintains feasiblity with respect to the equality constraints. A safeguarded polynomial interpolation method is used in the linesearch procedure in order to reduce an augmented Lagrangian merit function. Default values are assigned to all algorithm control parameters (e.g. iteration limits, etc), and parameter values may be changed by calls to a special purpose input specification subroutine.
Dense NLP
A dense nonlinear programming capability is available that utilizes the sparse nonlinear programming algorithm. Four different options are available for constructing the Hessian matrix including three quasi-Newton procedures (SR1, BFGS, and SSQN), as well as a full second order method. For dense applications the quadratic programming subproblem can be solved using the sparse Schur-complement method or a dense nullspace QP. The dense NLP can be used with either a forward or reverse communication format. The reverse communication format is available to permit the user to evaluate gradients analytically. The forward communication format of the algorithm, constructs gradient information using finite differences and requires only that the user supply a subroutine to evaluate the problem functions.
Finite Difference Jacobian/Hessian approximations
A collection of utility subroutines for constructing finite difference approximations to the Jacobian and Hessian matrices has been implemented. For many sparse applications this approach permits calculation of the derivatives with far fewer perturbations than the number of variables. Software to construct the variable partitions (index sets), and check the sparsity pattern are also included.
Sparse Optimal Control Software (SOCS)
The SOCS package is a collection of subroutines capable of solving optimal control problems. The package implements a direct transcription or collocation method to convert the continuous control problem into a discrete approximation. The discretization yields a finite dimensional sparse nonlinear programming problem which can be solved using the sparse SQP algorithm SPRNLP. Numerical procedures to improve the accuracy of the discretization by mesh refinement are implemented in the package. SOCS is capable of solving problems with multiple phases, state and control variable equality and inequality constraints, and can be applied to general nonlinear boundary value problems. The solution produced is represented in a B-spline format for subsequent evaluation and analysis.
All software is written in ANSI Standard FORTRAN 77 for use on most major computational platforms. In particular the software has been executed on workstations (SUN, HP, SGI, etc), mainframes (Cray, Convex, IBM), and personal computers (386, 486, Pentium).
The Sparse Otimal Control Software (SOCS) is available without restriction for commercial applicatoins as well as academic research. For more information visit the SOCS webpage.
Contact:
John Betts
Phone: (425) 865-3298
E-mail: john.t.betts@boeing.com
Paul Frank
Phone: (425) 865-3548
E-mail: paul.d.frank@boeing.com
Steve Keeler
Phone: (425) 865-3519
E-mail: steve.keeler@pss.boeing.com
Betts, J.T. and Frank, P.D., ``A Sparse Nonlinear Optimization Algorithm,'' Journal of Optimization Theory and Applications, Vol. 82, No. 3, Sept. 1994.
Betts, J.T. and Huffman, W.P., ``Path Constrained Trajectory Optimization Using Sparse Sequential Quadratic Programming,'' AIAA Journal of Guidance, Control, and Dynamics, Vol. 16, No. 1, Jan-Feb, 1993, pp 59-68.
[ Optimization Software Guide | OTC Home Page | NEOS Server | NEOS Guide ]