Numerical experience with a recursive trust-region method for multilevel nonlinear bound-constrained optimization

Abstract

We consider an implementation of the recursive multilevel trust-region algorithm proposed by Gratton et al. (A recursive trust-region method in infinity norm for bound-constrained nonlinear optimization, IMA J. Numer. Anal. 28(4) (2008), pp. 827–861) for bound-constrained nonlinear problems, and provide numerical experience on multilevel test problems. A suitable choice of the algorithm's parameters is identified on these problems, yielding a satisfactory compromise between reliability and efficiency. The resulting default algorithm is then compared with alternative optimization techniques such as mesh refinement and direct solution of the fine-level problem. It is also shown that its behaviour is similar to that of multigrid algorithms for linear systems.

Keywords:

• nonlinear optimization
• bound-constrained problems
• multilevel problems
• simplified models
• recursive algorithms
• numerical performance

Notes

We refer the reader to Gratton et al. 19 for a more complete discussion of these advantages.

The first-order modification (5) is usual in multigrid applications in the context of the ‘full approximation scheme’, where it is usually called the ‘tau correction’ (see, for instance, [3, Chapter 3], or 22).

See [3, p. 10] or [17, p. 510] or [29, p. 241], among many others.

A the coarsest level, 0, smoothing iterations are skipped and recursion is impossible.

Notice that we did not represent the tests where the coarse model is defined as in (5) because preliminary tests showed that performing only a first-order correction is indisputably not competitive.

Observe that the MR variant had to be stopped after 1 h of computing on this problem.

We should note here that the Hessian of this quadratic problem is not supplied by the MINPACK code and has been obtained once and for all at the beginning of the calculation by applying an optimized finite-difference scheme (see 30).