A shorter-step trust region algorithm for the minimization of nonlinear partially separable functions

In trust region algorithms for nonlinear minimization, the fit between the objective function and its model is tested in each iteration to update the trust region radius. This radius restricts the step length equally in all directions. However, for a partially separable function, the accuracy of the model may be different for the various parts of the objective function. One would like to allow longer steps in the subspaces of the more accurately modeled parts, with the expectation that the extra flexibility will give faster convergence.

The excellent idea of structuring the trust region for partially separable problems belongs to [A.~R. Conn, Nick Gould, A. Sartenaer, and Ph.~L. Toint, Convergence properties of minimization algorithms for convex constraints using a structured trust region, {\em SIAM J. Optim.}, 6 (1996), pp. 1059--1086]. They prove global first order convergence for convex-constrained problems. Their trust region update mechanism and second order analysis are complex.

The sufficient decrease condition in Conn et al. is changed so that the exact minimizer of the model within the trust region will always satisfy it. However, we add another condition on the step that is needed to guarantee global convergence. New and simpler update mechanisms for the trust region radii are investigated. First order convergence is proved for the convex-constrained problem. Second order convergence results are proved for the unconstrained case.