A subspace minimization method for the trust-region step

Jennifer B. Erway (erwayjbwfu.edu)
Philip E. Gill (pgillucsd.edu)

Abstract: We consider methods for large-scale unconstrained minimization based on finding an approximate minimizer of a quadratic function subject to a two-norm trust-region inequality constraint. The Steihaug-Toint method uses the conjugate-gradient algorithm to minimize the quadratic over a sequence of expanding subspaces until the iterates either converge to an interior point or cross the constraint boundary. Recent extensions of the Steihaug-Toint method allow the accuracy of the trust-region step to be specified, thereby allowing the overall cost of computing the problem functions to be balanced against the cost of computing the trust-region steps. However, if a preconditioner is used with the conjugate-gradient algorithm, the Steihaug-Toint method requires the trust-region norm to be defined in terms of the preconditioning matrix. If a different preconditioner is used for each trust-region subproblem, the shape of the trust-region can change substantially from one subproblem to the next, which implies that the assumptions on which standard methods for adjusting the trust-region radius are based do not hold. In this paper we propose a method that allows the trust-region norm to be defined independently of the preconditioner. The method solves the inequality constrained trust-region subproblem over a sequence of evolving low-dimensional subspaces. Each subspace includes an accelerator direction obtained from a Newton method applied to an primal-dual interior method. A crucial property of this direction is that it can be computed by applying the preconditioned conjugate-gradient method to a positive-definite system in both the primal and dual variables of the trust-region subproblem.

Keywords: Large-scale unconstrained optimization, trust-region methods, conjugate-gradient methods, Krylov methods, preconditioning

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Unconstrained Optimization )

Citation: Numerical Analysis Report 08-1, Department of Mathematics, University of California San Diego, La Jolla, CA, 92093-0112; Technical Report 2008-2, Department of Mathematics, Wake Forest University, Winston-Salem, NC, 2008

Download: [PDF]

Entry Submitted: 03/19/2008
Entry Accepted: 03/19/2008
Entry Last Modified: 04/03/2008

Modify/Update this entry