A multilevel algorithm for solving the trust-region subproblem

Abstract

We present a multilevel numerical algorithm for the exact solution of the Euclidean trust-region subproblem. This particular subproblem typically arises when optimizing a nonlinear (possibly non-convex) objective function whose variables are discretized continuous functions, in which case the different levels of discretization provide a natural multilevel context. The trust-region problem is considered at the highest level (corresponding to the finest discretization), but information on the problem curvature at lower levels is exploited for improved efficiency. The algorithm is inspired by the method described in [J.J. Moré and D.C. Sorensen, On the use of directions of negative curvature in a modified Newton method, Math. Program. 16(1) (1979), pp. 1–20], for which two different multilevel variants will be analysed. Some preliminary numerical comparisons are also presented.

Keywords:

• nonlinear optimization
• trust-region subproblem
• numerical algorithms
• multilevel methods

Acknowledgements

The work of Dimitri Tomanos is supported by a grant of the FRIA (Fund for Research in Agriculture and Industry). The work of Melissa Weber-Mendonça is made possible by a grant of CAPES (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior) from Brazil.

Notes

Note that conceptually similar techniques have also been proposed in the linesearch setting in 4 12 16 17 22, but we will not investigate this avenue in this paper.

In what follows, since we will describe what happens within a single ‘outer’ trust-region iteration, we will drop the iteration indices k for simplicity.

We require the Euclidean norm gradient of the objective function to be at most 10⁻⁶ for termination.

For problem BV, applying the RQMG option only when the |g| is below 10 times the stopping threshold reduces the additional cost from 50% to 10%.