Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can the non-linear conjugate gradient optimization method with Polak-Ribier line-search choice, be named as a quasi-Newton optimization technique?

If not, why?

share|improve this question
add comment

2 Answers

A Newton based optimization method tries to find the roots of the gradient by Newton's method. This involves evaluating the Hessian and solving linear systems involving the Hessian. A quasi-Newton optimization technique use some approximation for the Hessian, or at least can be interpreted as implicitly using some approximation for the Hessian.

The non-linear conjugate gradient optimization method is not a quasi-Newton technique, because there is no Hessian involved, not even implicitly.

share|improve this answer
    
Thank you, this question is what I was looking for. –  linello Jun 14 '12 at 19:12
    
Sorry but this answer is erroneous. –  Dominique May 7 at 18:00
    
@Dominique Interesting. Can you also tell me which part is erroneous? My guess is that you disagree with: "A quasi-Newton optimization technique use some approximation for the Hessian, or at least can be interpreted as implicitly using some approximation for the Hessian." Or do you disagree with my last "... not even implicitly"? In that case, could you please help me to also recognize the implicit Hessian you have in mind? –  Thomas Klimpel May 7 at 18:22
    
@ThomasKlimpel It's the last paragraph I don't agree with. As the paper below shows, limited-memory BFGS methods coincide with the nonlinear CG provided you perform exact line searches. L-BFGS has a memory parameter. If you set it to zero, you obtain a specific update of the Hessian approximation. –  Dominique May 7 at 18:48
add comment

Nonlinear conjugate gradient methods are equivalent to memoryless BFGS quasi-Newton methods under the assumption that you perform an exact line search. This was stated in a 1978 paper by Shanno (he's the S in BFGS). Here's the relevant paragraph:

enter image description here

See http://dx.doi.org/10.1287/moor.3.3.244 for the whole paper.

share|improve this answer
    
How can I talk of approximating the Hessian, if I restart the approximation at every step? I rather would interpret the cited passage as a suggestion that BFGS might perform better than nonlinear conjugate gradient methods (ignoring memory consumption), because its a true quasi-Newton method. –  Thomas Klimpel May 7 at 18:28
    
You have an approximate Hessian at every step. The quoted passage doesn't tell the whole story. The paper establishes that memoryless BFGS = nonlinear conjugate gradient. –  Dominique May 7 at 18:45
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.