Techniques for solving Nonlinear Programming Problems with Emphasis on Interior Point Methods and Optimal Control Problems
View/ Open
Buchanan thesis 08 texfiles.zip (134.9Kb)
Buchanan thesis 08 epsfiles.zip (1.810Mb)
Date
2008Author
Buchanan, Catherine
Metadata
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.