| Quadratic programming (QP) problems are important in their own right and also arise as subproblems within a general class of nonlinear optimization algorithms known as Successive Quadratic Programming (SQP) methods. In this thesis, a sparse quadratic programming method based on both a sparse modification of Bunch and Parlett factorization of symmetric indefinite matrices and an active set strategy for indefinite projected Hessian matrices is developed. In particular, a constrained pivoting strategy is proposed and shown to significantly reduce fill-in in the iterative computation of the factorization of the Kuhn-Tucker matrices associated with the QP subproblem. A numerical algorithm for updating the lower triangular and diagonal factors is presented and shown to be very fast, usually requiring only about 5% of the cost of refactorization. An active set strategy that allows line searching in the negative line search direction is proposed and shown to handle common difficulties that arise from the projected indefiniteness of the Lagrangian Hessian such as linearly dependent constraints, Kuhn-Tucker multipliers with incorrect signs and infeasible quadratic programs. Also an LP-based trust region method is developed to handle nondescent directions. The proposed indefinite QP algorithm is tested within the context of a family of SQP methods on a variety of chemical process optimization problems with small and large degrees of freedom. Numerical results show uniformly that the proposed QP and SQP algorithms solve small and large problems reliably and efficiently. |
