-

 

 

 




Optimization Online





 

On the connection between the conjugate gradient method and quasi-Newton methods on quadratic problems

Anders Forsgren (andersf***at***kth.se)
Tove Odland (odland***at***kth.se)

Abstract: It is well known that the conjugate gradient method and a quasi-Newton method, using any well-defined update matrix from the one-parameter Broyden family of updates, produce identical iterates on a quadratic problem with positive-definite Hessian. This equivalence does not hold for any quasi-Newton method. We define precisely the conditions on the update matrix in the quasi-Newton 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 quasi-Newton condition is satisfied. In the framework based on a sufficient condition to obtain mutually conjugate search directions, we show that the one-parameter Broyden family is complete. A one-to-one correspondence between the Broyden parameter and the non-zero scaling of the search direction obtained from the corresponding quasi-Newton method compared to the one obtained in the conjugate gradient method is derived. In addition, we show that the update matrices from the one-parameter Broyden family are almost always well-defined on a quadratic problem with positive-definite Hessian. The only exception is when the symmetric rank-one 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, quasi-Newton 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
Entry Accepted: 02/09/2013
Entry Last Modified: 03/09/2015

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
Mathematical Optimization Society