A shifted Steihaug-Toint method for computing a trust-region step.

Ladislav Luksan (luksancs.cas.cz)
Ctirad Matonoha (matonohacs.cas.cz)
Jan Vlcek (vlcekcs.cas.cz)

Abstract: Trust-region methods are very convenient in connection with the Newton method for unconstrained optimization. The More-Sorensen direct method and the Steihaug-Toint iterative method are most commonly used for solving trust-region subproblems. We propose a method which combines both of these approaches. Using the small-size Lanczos matrix, we apply the More-Sorensen method to a small-size trust-region subproblem to compute an approximation of the Lagrange multiplier. Then we solve the shifted system by the Steihaug-Toint method. This paper contains a complete theory concerning properties of the Lagrange multipliers and proves that the new method is globally convergent in the preconditioned case. Finally, results of extensive computational experiments are presented, which demonstrate an efficiency of the new method.

Keywords: Unconstrained optimization, large-scale optimization, trust-region methods, trust-region subproblems, conjugate gradients, Krylov subspaces, computational experiments.

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Citation: Report No. V914-04, Institute of Computer Science, AV CR, Pod Vodarenskou Vezi 2, 18207 Praha 8, Czech Republic. September 2004.

Download: [Postscript]

Entry Submitted: 09/17/2004
Entry Accepted: 09/17/2004
Entry Last Modified: 09/17/2004

Modify/Update this entry