Computational comparisons of some structured trust region approaches to the minimization of nonlinear partially separable functions

Trust region algorithms are strongly convergent, and typically restrict the step to lie within a spherical trust region.
Structured trust region algorithms attempt greater efficiency by allowing differing trust region radii in different partially separable subspaces. However, the unpredictable shape of this trust region takes away some convergence strength for naive implementations. Restrictions on the step, as well as new update mechanisms for the trust region radii, have been proposed in earlier work, to correct this.

In the first part of this paper we propose a new structured trust region algorithm to evaluate the practical advantage of structuring the trust region. The new algorithm solves two subproblems in each iteration: a structured set of constraints for one, and a classical spherical constraint in the other. The solution to the structured subproblem is the new step only if it achieves the greater decrease. We prove that this is a first and second order globally convergent strategy.

In the second part we give the results of computational tests on three structured algorithms, two proposed earlier by the author and the one described here, against a typical unstructured trust region algorithm. The structured approaches uniformly do better than the unstructured one.