[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
An Interior-Point Subspace Minimization Method for the Trust-Region Step.
by Philip E. Gill, J. B. Erway
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.
UCSD-CCoM-08-01.pdf January 2008
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
by Philip E. Gill, J. B. Erway
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.
UCSD-CCoM-08-01.pdf January 2008