Re: conjugate gradient stuck at inflection point

Palle Uldenborg wrote:
On Aug 22, 3:55 pm, mecej4 <mec...@xxxxxxxxxxxxx> wrote:
There are two issues here, which you have intertwined. The first issue
is the nature of the objective function and its extrema and the second
is the behavior of the variant of the CG method that you have implemented.

Thank you for your reply. I should probably have left out the physics
and posed the question in a more general way. Here is a second
attempt:

I read the proofs that line search algorithms should always converge
in theory, but is it wellknown that a real life implementation of the
conjugate gradient algorithm (with cubic interpolation) may converge
to inflection point when applied to a particularly nasty function?

If this has never happened to anybody else, then I must conclude that
my code is wrong, and that should be the end of this thread. It is
probably better that I do my debugging in private :-)

If the problem is wellknown then there is a chance that my code is
correct, but that my potential energy function is so nasty that I need
extra tricks. In that case I would like to find some literature that
describes standard tricks of the trade to avoid the problem.

BTW: During the minimisation proces my algorithm sometimes seems to
spend a lot of time at one or two local minima of |grad U(x)|^2 before
continuing down to the minimum of U(x). I can see this problem by
plotting |grad U(x_i)|^2 against i, where i is the number of the line
search. While spending time at
the local minimum of |grad U(x)|^2 the line searches become shorter
and shorter until the algorithm finally breaks free and moves on down
towards the minimum, when the algorith has broken free the line
searches become longer again. Is this a common feature of line search
algorithms or should I be worried?

Thanks again

Palle

It is probably worth the effort for you to construct and present a small-size problem for which your code exhibits the behavior that you described.

With truncated Newton methods, it has been long-established that the line searches should be terminated before completion. The selection of the best Wolfe termination parameters is definitely not intuitive.

Does your problem have features that make CG the method of choice? There are excellent codes available

http://plato.asu.edu/guide.html

which encompass CG as well as many other methods. Some of these could be tried with little effort prior to "rolling your own".

-- mecej4
.