Frame-based algorithms for derivative-free optimisation. (2004)
AuthorsByatt, Davidshow all
A class of provably convergent frame-based line search algorithms that do not explicitly rely on derivative information is developed for unconstrained and linearly constrained optimisation. A frame-based approach relies on the underlying theory of positive bases. The use of positive bases (either directly or indirectly) facilitates the development of convergence proofs for many (including some already well-established) derivative-free optimisation algorithms. Although positive bases have recently been the subject of renewed interest in optimisation research they do not feature in many modern texts on linear algebra. For this reason background material on positive bases and grids (the precursors to frames) is also presented. A weakness with a common choice of stopping conditions for existing grid- (which includes pattern search) and frame-based derivative-free methods is identified and a solution is presented. This solution is shown to possess good numerical stability properties when extended for use with existing derivative-based (BFGS and DFP) algorithms-even when approximate second-order information is available to only limited precision-as is usually the case in practice since, for many "real-world" problems, explicit gradient or second order information may not be available and the evaluation of the objective function to arbitrary levels of precision is not possible.