×

Computing a trust region step. (English) Zbl 0551.65042

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

Software:

NMTR; MSS; GQTPAR
PDFBibTeX XMLCite
Full Text: DOI Link