Techniques for solving Nonlinear Programming Problems with Emphasis on Interior Point Methods and Optimal Control Problems

Abstract

The primary focus of this work is a thorough research into the current available techniques for solving nonlinear programming problems. Emphasis is placed on interior-point methods and the connection between optimal control problems and nonlinear programming is explored. The document contains a detailed discussion of nonlinear programming, introducing different methods used to find solutions to NLP problems and then describing a large variety of algorithms from the literature. These descriptions make use of a unified notation, highlighting key algorithmic differences between solvers. Specifically, the variations in problem formulation, chosen merit functions, ways of determining stepsize and dealing with nonconvexity are shown. Comparisons between reported results on standard test sets are made. The work also contains an understanding of optimal control problems, beginning with an introduction to Hamiltonians, based on their background in calculus of variations and Newtonian mechanics. Several small real-life problems are taken from the literature and it is shown that they can be modelled as optimal control problems so that Hamiltonian theory and Pontryagin's maximum principle can be used to solve them. This is followed by an explanation of how Runge-Kutta discretization schemes can be used to transform optimal control problems into nonlinear programs, making the wide range of NLP solvers available for their solution. A large focus of this work is on the interior point LP and QP solver hopdm. The aim has been to extend the solver so that the logic behind it can be used for solving nonlinear programming problems. The decisions which were made when converting hopdm into an nlp solver have been listed and explained. This includes a discussion of implementational details required for any interior point method, such as maintenance of centrality and choice of barrier parameter. hopdm has successfully been used as the basis for an SQP solver which is able to solve approximately 85% of the CUTE set and work has been carried out into extending it into an interior point NLP solver.