  


On the connection between the conjugate gradient method and quasiNewton methods on quadratic problems
Anders Forsgren (andersfkth.se) Abstract: It is well known that the conjugate gradient method and a quasiNewton method, using any welldefined update matrix from the oneparameter Broyden family of updates, produce identical iterates on a quadratic problem with positivedefinite Hessian. This equivalence does not hold for any quasiNewton method. We define precisely the conditions on the update matrix in the quasiNewton method that give rise to this behavior. We show that the crucial facts are, that the range of each update matrix lies in the last two dimensions of the Krylov subspaces defined by the conjugate gradient method and that the quasiNewton condition is satisfied. In the framework based on a sufficient condition to obtain mutually conjugate search directions, we show that the oneparameter Broyden family is complete. A onetoone correspondence between the Broyden parameter and the nonzero scaling of the search direction obtained from the corresponding quasiNewton method compared to the one obtained in the conjugate gradient method is derived. In addition, we show that the update matrices from the oneparameter Broyden family are almost always welldefined on a quadratic problem with positivedefinite Hessian. The only exception is when the symmetric rankone update is used and the unit steplength is taken in the same iteration. In this case it is the Broyden parameter that becomes undefined. Keywords: conjugate gradient method, quasiNewton methods, unconstrained quadratic program Category 1: Nonlinear Optimization (Quadratic Programming ) Category 2: Nonlinear Optimization (Unconstrained Optimization ) Citation: arXiv:1407.1268 [math.OC] Download: Entry Submitted: 02/09/2013 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  