Using Partial Separability of Functions in Generating Set Search Methods for Unconstrained Optimisation

Lennart Frimannslund (lennartii.uib.no)
Trond Steihaug (trondii.uib.no)

Abstract: Generating set Search Methods (GSS), a class of derivative-free methods for unconstrained optimisation, are in general robust but converge slowly. It has been shown that the performance of these methods can be enhanced by utilising accumulated information about the objective function as well as a priori knowledge such as partial separability. This paper introduces a notion of partial separability which is not dependent on differentiability. We present a provably convergent method which extends and enhances a previously published GSS method. Whereas the old method for two times continuously differentiable functions takes advantage of Hessian sparsity, the new method takes advantage of the separability properties of partially separable functions with full Hessians as well. If the Hessian is undefined we show a similar extension, compared with the old method. In addition, we introduce some new theoretical results and discuss variants of the method.

Keywords: Unconstrained optimisation, derivative-free optimisation, noisy optimisation, generating set search, pattern search, separability, sparsity

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Report 2006-318, Department of Informatics, University of Bergen, Norway, 2006.

Download: [PDF]

Entry Submitted: 04/26/2006
Entry Accepted: 04/26/2006
Entry Last Modified: 04/26/2006

Modify/Update this entry