Computing a trust region step. (English) Zbl 0551.65042

Moré, Jorge J.; Sorensen, D. C.

SIAM J. Sci. Stat. Comput. 4, 553-572 (1983).

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 implementation 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.

MSC:

65K05	Numerical mathematical programming methods
90C20	Quadratic programming

Keywords:

Newton’s method; trust region; ellipsoidal constraint; global convergence

Software:

NMTR; GQTPAR; MSS