A Comparisation of Methods for the Optimisation of a Non-Linear Function Subject to Non-Linear Constraints

Abstract

This thesis deals mainly with a comparison of certain computational techniques used for the solution of non-linear constrained mathematical programming problems. The three techniques being considered here are: (a) Sequential Unconstrained Minimisation Technique, (S.U.M.T.), by Fiacco and McCormick; (b) Kowalik, Osborne and Ryan’s method; (c) Powell’s method for constrained problems. They all convert the problem into a sequence of unconstrained problems, that is to say the objective function and the constraints of the original problem are transformed to define a new objective function called an auxiliary or penalty function. By gradually changing the effects of the constraints in the penalty function, a sequence of unconstrained problems is generated. As the penalty function is being minimised at each step of the sequence, an efficient unconstrained minimisation algorithm had to be found. Three unconstrained algorithms have been compared: A direct search method (Simplex); Two conjugate direction methods: (a) Powell (64)'s method not requiring the calculation of derivatives; (b) Fletcher and Powell’s method requiring the calculation of derivatives. All the methods have been written in the same language, ICL Algol 60, and have been tested with the same set of well-known standard test problems and some larger ones. All the methods have been described followed by their respective results. For overall comparison, the best results from each algorithm are considered and tabulated in function of the total number of function evaluations and in function of computer time. We can, then, draw two conclusions: (a) if, as some people suggest, the total number of function evaluations is more important, the Powell’s method could be the more efficient of the methods considered; (b) if computer time is more important, then S.U.M.T. could be the more efficient method.