# In which cases does the nonlinear conjugate gradient method take more than $n$ steps?

I have programmed a couple of Matlab implementations of nonlinear Conjugate Gradient methods (Fletcher Reeves and Polak Ribeire). However, I am concerned with how many steps it's taking to optimise the function $$f(x,y) = x^2 + 5x^4 + 10y^2$$, roughly 100. I have read that the bound for convergence is $$O(n)$$ where $$n$$ is the dimension of the space my function lives in.

Are there properties of this function's Hessian/Gradient that mean that this bound doesn't apply in this case? If so why? Are there any simple functions to test my implementation with, that have an expected convergence rate?

Edit 1: I should mention that the tolerance is set quite low, $$10^{-12}$$, is this probably the issue? Why should it be so if it is?

• Would you mind adding the complete bibliographic information? – nicoguaro Feb 6 '20 at 16:48
• I'm reading Nocedal and Wright's Optimization textbook. – skailasa Feb 7 '20 at 10:58

## 1 Answer

The nonlinear conjugate gradient method will converge for a quadratic function in $$N$$ steps at most. You do not have a quadratic function, and have no guarantees on convergence. It can be helpful to reset your search direction every $$N$$ steps or to use a better method (i.e., Newton's method). A simple function that you could use to test would be a quadratic function, one with the form: $$f = \lvert\lvert(b - Ax)\rvert\rvert^2$$ for scalar functions, this is a parabola (for positive a and b), and should be very easy to check as you have a closed-form expression for the solution. For vector functions, $$A$$ is a matrix, $$b$$ and $$x$$ are vectors and you solve for $$x$$ to minimize the function $$f(x)$$. When you move beyond quadratic functions, you can look at the Rosenbrock problem which is numerically tricky but has a known solution and is a good validation case for basic algorithms and codes.

EDIT: I edited for clarity. You also have a fairly obvious typo in your formula. Is one of the $$x^2$$ terms supposed to be a $$y^2$$?

• Thanks for your answer. I’ll try out a simple quadratic function and see what happens. I’ve also added a edit for the typo! – skailasa Feb 7 '20 at 10:16