MULTI-STEP QUASI-NEWTON METHODS FOR OPTIMIZATION

Issam  A.R. MOGHRABI

This thesis presents a new approach to Quasi‑Newton methods for unconstrained optimization. Quasi‑Newton methods update, at each iteration, the existing Hessian approximation (or its inverse) by means of data deriving from the step just completed. These methods are based on the so‑called secant equation, which is shown to be one particular linear approximation of what is known as the Newton equation. Our methods aim at finding other approximation to the Newton equation which may be more appropriate for non‑quadratic functions. The new methods are based on considering interpolatory polynomials for the independent variables and similar forms for approximating the gradient. These polynomials utilize information from the most recent iterations. This leads to a generalization of the secant equation (which corresponds to m=l). We discuss ways for distributing the points on the curve by deriving and evaluating strategies for defining the parameter values, which correspond to the points on the curve. The choices we consider are cheap to compute since they make use of already available information.

We address the issue of maintaining positive‑definiteness for formula chosen from the convex class of Broyden's family. We also consider a limited‑memory version of the methods. We have tested the new methods using a BFGS‑type formula and used the standard form of the formula as the benchmark for comparing the new methods with the standard ones. The new methods seem to markedly improve on the standard ones especially as the dimension of the problem increases. Motivated by the success of methods which incorporate information available at each iteration in updating the Hessian approximation, we derive algorithms, which combine the multi‑step methods with the techniques of Ford & Saadallah and ford & Ghandhari for exploiting function values and curvature information. Our numerical results reveal that further gains in performance have been achieved but at the expense, in some cases, of solving a non‑linear equation in one variable at each iteration.