@MASTERSTHESIS\{IMM2007-05456,
    author       = "E. L. Hansen and C. Volcker",
    title        = "Numerical Algorithms for Sequential Quadratic Optimization",
    year         = "2007",
    school       = "Informatics and Mathematical Modelling, Technical University of Denmark, {DTU}",
    address      = "Richard Petersens Plads, Building 321, {DK-}2800 Kgs. Lyngby",
    type         = "",
    note         = "Supervised by Assoc. Prof. John Bagterp J{\o}rgensen, {IMM,} {DTU}.",
    url          = "http://www2.compute.dtu.dk/pubdb/pubs/5456-full.html",
    abstract     = "This thesis investigates numerical algorithms for sequential quadratic programming (SQP). {SQP} algorithms are used for solving nonlinear programs, i.e. mathmatical optimization problems with nonlinear constraints.

{SQP} solves the nonlinear constrained program by solving a sequence of associating quadratic programs (QP’s). A {QP} is a constrained optimization problem in which the objective function is quadratic and the constraints are linear. The {QP} is solved by use of the primal active set method or the dual active set method. The primal active set method solves a convex {QP} where the Hessian matrix is positive semi definite. The dual active set method requires the {QP} to be strictly convex, which means that the Hessian matrix must be positive definite. The active set methods solve an inequality constrained {QP} by solving a sequence of corresponding equality constrained {QP}’s.

The equality constrained {QP} is solved by solving an indefinite symmetric linear system of equations, the so-called Karush-Kuhn-Tucker (KKT) system. When solving the {KKT} system, the range space procedure or the null space procedure is used. These procedures use Cholesky and {QR} factorizations. The range space procedure requires the Hessian matrix to be positive definite, while the null space procedure only requires it to be positive semi-definite.

By use of Givens rotations, complete factorization is avoided at each iteration of the active set methods. The constraints are divided into bounded variables and general constraints. If a bound becomes active the bounded variable is fixed, otherwise it is free. This is exploited for further optimization of the factorizations.

The algorithms has been implemented in Matlab and tested on strictly convex {QP}’s of sizes up to 1800 variables and 7200 constraints. The testcase is the quadruple tank process, described in appendix A.

Main Findings of this Thesis:

When the number of active constraints reaches a certain amount compared to the number of variables, the null space procedure should be used. The range space procedure is only prefereble, when the number of active constraints is very small compared to the number of variables.

The update procedures of the factorizations give significant improvement in computational speed.

Whenever the Hessian matrix of the {QP} is positive definite the dual active set method is prefereble. The calculation of a starting point is implicit in the method and furthermore convergence is guaranteed.

When the Hessian matrix is positive semi definite, the primal active set can be used. For this matter an {LP} solver should be implemented, which computes a starting point and an active set that makes the reduced Hessian matrix positive definite. This {LP} solver has not been implemented, as it is out of the range of this thesis."
}