Newsgroups: sci.math.num-analysis
From: lpa@netcom.com (Pierre Asselin)
Subject: Re: Conjugate gradient and line searches
Date: Tue, 7 Nov 1995 02:45:27 GMT

roland@galileo.line.com (Roland B Roberts) writes:

>I'm writing some code to non-linear optimization using a conjugate
>gradient method.  The one problem I'm having difficulty with is trying
>to decide how to go about doing the line search part of the algorithm.

>Here's the basic problem.  I've determined a search direction, dX, and
>now want to minimize my objective function along that direction from my
>starting point X:

>    min F(X + u dX), subject to u > 0

>[...] My strategy right
>now is to pick u=0.25 (which is an arbitrary choice) and then decrease u
>if my objective function became larger (meaning my step was too big):
>[...and otherwise increase u until the function increases, thereby
> bracketing a minimum.]

Without more information, this is about the best you can do.
Personally, I try very hard to obtain some scaling information for
the problem, in case the optimal u turns out to be 0.25e-13 or 5.2e+22.  

The directional derivative of the objective is [(gradF)^t dX]
and the second directional derivative is [(dX)^t H dX], where H is the
Hessian.  See if you can compute or approximate that product without
computing and storing the entire Hessian.  The ratio F'/F'' is a good
starting value for u.  Asymptotically, it is the optimal u.

If you are using conjugate gradients you probably have analytic first
derivatives.  In that case, your line search will be more accurate if
you look for a zero crossing of F'(u), say with Regula Falsi.  As
before you want to bracket the zero and, as before, it is the initial
scaling that is hard to get.  Do check for a decrease of F(u) because
this is the most robust protection against divergence.

SOAP BOX:
The line search is the best place to run sanity checks on the
algorithm.  If any of the following happen,

    1) F''(0) negative (if you have access to it);
    2) bracketing had to reach further than expected;
    3) line search had to backtrack;
    4) Regula Falsi (or Golden search or whatever) had to
       work harder than expected;

Then you *know* that you haven't reached the bottom of the bowl.  The
objective function doesn't look like a quadratic yet.  Restart the
conjugate gradient algorithm at the next step.
-- 
--Pierre Asselin, Westminster, Colorado
  lpa@netcom.com
  pa@verano.sba.ca.us