A New Generating Set Search Method for Unconstrained Optimisation

Lennart Frimannslund
University of Bergen, Norway

Trond Steihaug
University of Bergen, Norway

Ladda ner artikel

Ingår i: Nordic MPS 2004. The Ninth Meeting of the Nordic Section of the Mathematical Programming Society

Linköping Electronic Conference Proceedings 14:13, s.

Visa mer +

Publicerad: 2004-12-28


ISSN: 1650-3686 (tryckt), 1650-3740 (online)


Generating set searches; a class of derivative-free optimisation methods; has been an area of active research in recent years; much caused by the development of convergence theory. However; although these methods are usually easy to implement; robust and provably convergent in most cases; their attractiveness suffers from the fact that they are slow when it comes to convergence. Usually these methods do not take the local topography of the objective function into account.

We present a new algorithm which is a modification to a well known generating set search method; Compass Search. The new algorithm tries to adapt its search directions to the local topography by accumulating curvature information about the objective function as the search progresses. We present some theory regarding its properties; as well as numerical results that show our algorithm to outperform Compass Search most of the time; sometimes by significant relative margins; on noisy as well as smooth problems. In addition; preliminary numerical results indicate that we can exploit the sparsity information of the Hessian matrix. Thus allowing us to solve relatively large problems using methods in this class.


Inga nyckelord är tillgängliga


Inga referenser tillgängliga

Citeringar i Crossref