Active set algorithms for large-scale nonlinear programming

This thesis concerns the development of active set algorithms for large-scale nonlinear programming. Active set algorithms are characterized by their ability to identify the activity of constraints, hopefully at an early stage of the optimization process. This contrasts with interior point methods, which, despite their widely recognized performance in a range of applications, almost never yield a clean identification of the active constraints. To measure the performance of an active set algorithm, one need consider not only its rate of convergence, but also its performance in terms of constraint activity identification. The purpose of this thesis is to design, analyze and evaluate new active set algorithms that meet these criteria for the solution of general constrained smooth nonlinear programming problems.;The first part of this thesis pertains the development of a subspace minimization technique intended to accelerate sequential quadratic programming (SQP), a traditional active set algorithm. The novelty of this technique, referred to as SQP+, is that it allows the use of exact second-order information (Hessian) through the solution of an additional equality constrained quadratic program (EQP) per iteration. The additional EQP is normally less expensive to solve than a general quadratic program and allows for the application of iterative methods that scale up in the number of variables.;The second part of the thesis focuses on the design and development of a new active set algorithm that we call PLA, and whose novel feature lies in the use of piecewise linear models in active set identification. Motivated by the promise and limitations of the two main active set methods---SL-QP and SQP, the new algorithm employs curvature information in its active set identification phase, as in SQP methods, and achieves the computational economy of only solving linear programs and equality constrained quadratic programs, as in the SL-QP approaches. Most important among our contributions of PLA are the detailed guidelines for defining and updating the sequence of piecewise linear models that endow the new algorithm with favorable global and asymptotic convergence properties.;We present a practical implementation of PLA in the last part of the thesis, where several practical considerations of PLA, such as the treatment of inconsistent constraints and the solution methodology for the piecewise linear programs, are discussed. Our numerical experience of the PLA method on the CUTEr problem set is also reported.