A Derivative-free Algorithm for Sparse Unconstrained Optimization Problems

                   B. Colson and Ph. L. Toint

We consider the problem of minimizing a function whose derivatives are not
available. This paper first presents an algorithm for solving problems of this
class using interplation polynomials and trust-region techniques.  We then
show how both the data structure and the procedure allowing to build
theinterpolating polynomials may be adapted in a suitable way to consider
problems for which the Hessian matrix is known to be sparse.  The favourable
behaviour of the resulting algorithm is confirmed with numerical experiments
illustrating the advantages of the method in terms of storage, speed and
function evaluations, the latter criterion being particularly important in the
framework of derivative-free optimization.