On the use of function values to improve Quasi-Newton methods

The subject of optimization (maximization or minimization) is a combination of theory and experiment, and has applications in almost every branch of technology and industry. The function may have to be optimized under certain constraints or the problem may be unconstrained. Methods of optimization may be classified as derivative (or gradient) methods and non-derivative methods. We assume that the n-variable function to be optimized and its first partial derivatives are all continuous. In this work, we intend to examine derivative methods for unconstrained problems and will seek to improve the numerical performance of one well-known and widely-used class of methods, namely, the "quasi-Newton" algorithms. The material of this thesis is organized into seven chapters. The first three chapters are devoted to a survey of existing methods for the unconstrained problem while, in the remainder of the thesis, we investigate new techniques for improving quasi-Newton methods. In chapter 1, after giving some basic definitions, we discuss the derivation and properties of fundamental algorithms in this area, such as Steepest Descent, Newton's method and the Conjugate Direction methods. In chapter 2, besides the derivation of the 'secant' equation (which constitutes the basis of quasi-Newton methods), we discuss a number of well-known update formulas. It is shown that the 'secant' equation is based on a linear model for the gradient. To find a better estimate for the solution, every quasi-Newton method usually requires the utilization of either a line-search or a trust-region technique at every iteration. Chapter 3 surveys these techniques, the convergence properties of quasi-Newton methods and termination conditions appropriate to a gradient method. In chapter 4, we investigate the design of nonlinear parametric models for the gradient and different approaches to the determination of the parameter(s) in the models. This leads to a number of new algorithms which may be utilized in place of the standard quasi-Newton methods. The new algorithms are classified into two groups (exponential and non-exponential models) and are examined in chapters 5 and 6, respectively. We show that all of the new algorithms may be expected to tend to the standard quasi-Newton algorithms as the minimum is approached. The condition number of matrices of the new algorithms are controlled in relation quasi-Newton algorithm. We also ensure to that of a standard the maintenance of positive-definiteness of the Hessian approximation, which property plays a very important role in the convergence of the algorithms. In chapter 7, we present numerical results for the new algorithms described in chapter 5 and 6. In order to assess the results, we have compared the new algorithms with two existing algorithms (one of which is the 'BFGS' algorithm (one of the best known standard quasi-Newton methods to date)). We conclude with a discussion of the numerical results and some suggestions for further research.