Computing a Trust Region Step

TLDR

The paper proposes an algorithm that minimizes a quadratic function under an ellipsoidal constraint and guarantees near‑optimal solutions in finite iterations. The algorithm is integrated into a trust‑region Newton method to solve the constrained quadratic problem. The method converges to a point satisfying necessary optimality conditions, and numerical tests show GQTPAR achieves this in about 1.6 iterations on average, demonstrating effectiveness in trust‑region applications.

Abstract

We propose an algorithm for the problem of minimizing a quadratic function subject to an ellipsoidal constraint and show that this algorithm is guaranteed to produce a nearly optimal solution in a finite number of iterations. We also consider the use of this algorithm in a trust region Newton’s method. In particular, we prove that under reasonable assumptions the sequence generated by Newton’s method has a limit point which satisfies the first and second order necessary conditions for a minimizer of the objective function. Numerical results for GQTPAR, which is a Fortran implementaton of our algorithm, show that GQTPAR is quite successful in a trust region method. In our tests a call to GQTPAR only required 1.6 iterations on the average.