Optimization Online


A practical method for solving large-scale TRS

M.S. Apostolopoulou (msa***at***math.upatras.gr)
D.G. Sotiropoulos (dgs***at***ionio.gr)
C.A. Botsaris (botsaris***at***ucg.gr)
P. Pintelas (pintelas***at***math.upatras.gr)

Abstract: We present a nearly-exact method for the large scale trust region subproblem (TRS) based on the properties of the minimal-memory BFGS method. Our study in concentrated in the case where the initial BFGS matrix can be any scaled identity matrix. The proposed method is a variant of the Mor\'{e}-Sorensen method that exploits the eigenstructure of the approximate Hessian $B$, and incorporates both the standard and the hard case. The eigenvalues are expressed analytically, and consequently a direction of negative curvature can be computed immediately by performing a sequence of inner products and vector summations. Thus, the hard case is handled easily while the Cholesky factorization is completely avoided. An extensive numerical study is presented, for covering all the possible cases arising in the TRS with respect to the eigenstructure of $B$. Our numerical experiments confirm that the method is suitable for very large scale problems.

Keywords: Trust region subproblem, Nearly exact method, L-BFGS method, Eigenvalues, Negative curvature direction, Large scale optimization

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Nonlinear Optimization (Constrained Nonlinear Optimization )

Citation: Optimization Letters http://www.springerlink.com/content/p4t7481772123874 Technical Report No. TR09-01, University of Patras, Department of Mathematics, March 2009.

Download: [PDF]

Entry Submitted: 03/07/2009
Entry Accepted: 03/07/2009
Entry Last Modified: 05/16/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society