Experience with a Sparse Nonlinear Programming Algorithm

Nonlinear programming problems arise naturally in data fitting applications, and when discretization techniques are applied to systems described by ordinary or partial differential equations. For applications of this type the number of variables and constraints may be large (i.e. 100 < n < 100000), and the corresponding Jacobian and Hessian matrices are very sparse (i.e. typically less than 1% of the elements are nonzero). For small problems with dense matrices one of the most successful numerical techniques is the sequential quadratic programming approach. However, when algorithms appropriate for dense applications are applied to many large sparse problems, the computational expense is dominated by the solution of the quadratic programming subproblem and the evaluation of the Hessian matrices. A method appropriate for solving large sparse nonlinear programming problems is described in [3]. A review of the original method is presented with special attention given to a number of enhancements that have been made to the original algorithm which improve robustness and extend its utility. Particular attention is given to the method for constructing a modified Hessian approximation and the treatment of defective QP subproblems.