Investigation of an algorithm

Abstract

In recent years, a lot of attention has been paid to solving the general non-linear programming problem by reducing it to a sequence of quadratic programming problems. A quadratic approximation to the objective function is minimised subject to constraints which are linear approximations to the original constraints. This technique allows a natural extension of Quasi-Newton Methods to constrained problems by letting the matrix of co-efficients of the second order terms in the quadratic function be successively updated using a Variable Metric technique. It has been shown that if this matrix satisfies certain conditions relating it to the Hessian matrix of the Lagrangian function associated with the non-linear programming problem, then superlinear rates of convergence may be attained by the algorithm. Another very successful means of solving the minimisation problem is to incorporate the constraint and objective functions into a single penalty-type function which is minimised without regard to any constraints. If the unconstrained minimum is not feasible, then a parameter in the penalty function is altered and the unconstrained minimisation is repeated. The properties of the penalty function are usually designed to lead the sequence of unconstrained minima to the solution of the original problem. In this paper, an algorithm is presented which may be considered a natural combination of these two types of methods. A review of the theoretical properties of the various functions, matrices and solution techniques is given with particular emphasis on recent algorithms which have had a large degree of numerical success, and with good theoretical properties. Finally, some indication of the algorithm's performance is given by investigating the manner in which a selection of test problems is solved. The problems are of varying difficulty and type, and some comparisons are made with the other algorithms included in the paper.