1
$\begingroup$

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?

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

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$?

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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! $\endgroup$ – skailasa Feb 7 at 10:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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