A Globally Convergent Interior Point Algorithm for General Non-Linear Programming Problems

Ioannis Akrotirianakis and Berc Rustem

This paper presents a primal-dual interior point algorithm for solving general constrained non-linear programming problems. The initial problem is transformed to an equivalent equality constrained problem, with inequality constraints incorporated into the objective function by means of a logarithmic barrier function. Satisfaction of the equality constraints is enforced through the incorporation of an adaptive quadratic penalty function into the objective. The penalty parameter is determined using a strategy that ensures a descent property for a merit function. It is shown that the adaptive penalty does not grow indefinitely. The algorithm applies Newton's method to solve the first order optimality conditions of the equivalent equality problem. Global convergence of the algorithm is achieved through the monotonic decrease of a merit function. Locally the algorithm is shown to be quadratically convergent.

Technical Report 97/14, (November 1997), Department of Computing, Imperial College of Science, Technology and Medicine, 180 Queen's Gate, London SW7 2BZ, UK.

Contact: ia4@doc.ic.ac.uk