A modified nearly exact method for solving low-rank trust region subproblem

Zhaosong Lu (zhaosongisye.gatech.edu)
Renato Monteiro (monteiroisye.gatech.edu)

Abstract: In this paper we present a modified nearly exact (MNE) method for solving low-rank trust region (LRTR) subproblem. The LRTR subproblem is to minimize a quadratic function, whose Hessian is a positive diagonal matrix plus explicit low-rank update, subject to a Dikin-type ellipsoidal constraint, whose scaling matrix is positive definite and has the similar structure as the objective Hessian just described. The nearly exact (NE) method proposed by Mor{\'e} and Sorensen \cite{MORE83} is properly modified to solve the LRTR subproblem by avoiding computations of Cholesky factorization of large-scale matrix. The resulting MNE method is quite efficient and robust to for computing NE solutions of large-scale LRTR subproblems. This method can be applied to solve some large-scale nonlinear programming problems. Some computational results are reported to illustrate the performance.

Keywords: large-scale optimization, Limited-memory BFGS method, trust region method,nearly exact method, Sherman-Morrison-Woodbury formula.

Category 1: Nonlinear Optimization

Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205 USA, June 2004.

Download: [Postscript][PDF]

Entry Submitted: 05/31/2004
Entry Accepted: 06/02/2004
Entry Last Modified: 12/12/2004

Modify/Update this entry