From: stewart@cs.umd.edu (G. W. Stewart)
Newsgroups: sci.math.num-analysis
Subject: Re: Conjugate gradient and line searches
Date: 3 Nov 1995 03:04:30 -0500

In article <x6ka5ig60x.fsf@galileo.line.com>,
Roland B Roberts <roberts@panix.com> wrote:
#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.
#
[material deleted]
#
#I've looked through a few texts on optimization, but can't find any that
#specifically address this problem.  Numerical Recipes merely says there
#is no good theory for trying to find a bracketing interval.  Luenberger
#[Linear and Non-Linear Programming] gives methods for selecting `u'
#based on the quadratic form; most are fairly straightforward if you know
#the Hessian.
#

Try the following references.

@inbook{noce:91,
   author = "J. Nocedal",
   year = "1991",
   title = "Theory of Algorithms for Unconstrained Optimization",
   journal = "Acta Numerica",
   pages = "199--242",
   kwds = "nlop, conjugate gradients, quasi-Newton method"
}

@book{gimw:81,
    author = "P.E. Gill and W. Murray and M.H. Wright",
    year = "1981",
    title = "Practical Optimization",
    publisher = "Academic Press",
    address = "New York",
    kwds = "book, nlop"
 }

Pete Stewart

==============================================================================

Newsgroups: sci.math.num-analysis
From: Henry Wolkowicz <hwolkowi>
Subject: Re: Conjugate gradient and line searches
Date: Fri, 3 Nov 1995 14:24:31 GMT

stewart@cs.umd.edu (G. W. Stewart) wrote:

[previous article quoted in entirety; deleted -- djr]

You may also want to try the following reference which actually contains
pseudocode for the linesearch (bracketing) problem

       AUTHOR = "R. FLETCHER",
        TITLE = "Practical Methods of Optimization",
        PUBLISHER = "John Wiley \& Sons",
        YEAR = 1987,
        EDITION = "second",

-- 
||Henry Wolkowicz                |Fax:   (519) 725-5441
||University of Waterloo         |Tel:   (519) 888-4567, 1+ext. 5589
||Dept of Comb and Opt           |email:  henry@orion.uwaterloo.ca
||Waterloo, Ont. CANADA N2L 3G1  |URL: http://orion.uwaterloo.ca/~hwolkowi
||          anonymous ftp available at orion.uwaterloo.ca

==============================================================================

From: Mike Yukish <may106@psu.edu>
Newsgroups: sci.math.num-analysis
Subject: Re: Conjugate gradient and line searches
Date: 3 Nov 1995 14:23:18 GMT

In article <x6ka5ig60x.fsf@galileo.line.com> Roland B Roberts,
roland@galileo.line.com writes:
>I've looked through a few texts on optimization, but can't find any that
>specifically address this problem.  Numerical Recipes merely says there
>is no good theory for trying to find a bracketing interval.  Luenberger
>[Linear and Non-Linear Programming] gives methods for selecting `u'
>based on the quadratic form; most are fairly straightforward if you know
>the Hessian.
>
>roland
>-- 
>Roland B Roberts
>roberts@panix.com

Fletcher's book has a good section on the above problem. 

Fletcher, R. ( Roger. )
    Practical methods of optimization. / R. Fletcher. 2nd ed. Chichester;
New
  York, Wiley, c1987.
    xiv, 436 p. ill. 24 cm.
    "A Wiley-Interscience publication.".
    Includes index.
    Bibliography: p. [417]-429.
    1. Mathematical optimization.
 Call#: QA402.5.F43 1987
    Engineering Library, 325 Hammond Building

That's Penn State's call#.

Mike Yukish
Applied Research Lab
may106@psu.edu
http://quark.arl.psu.edu/staff/yuke-home.html

==============================================================================

From: adams@handel.EECS.Berkeley.EDU (Adam L. Schwartz)
Newsgroups: sci.math.num-analysis
Subject: Re: Conjugate Gradients and Inexact Line Searches
Date: 16 Nov 1995 18:35:42 GMT

In article <487voh$r3a@airgun.wg.waii.com>,
>In J.L. Nazareth, Conjugate gradient methods less dependent on conjugacy,
>Vol 28, No 4, Dec 1986, pp 501-511, the so called three-term recurrence
>relation is method is mentioned.  This conjugate gradient update scheme
>can be used when the initial search direction is not parallel to the
>gradient and when the line search is not necessarily exact.  Does anyone
>have any experience using this update scheme?

I tried it awhile ago for solving optimal control problems.  It
didn't work better for me than using the Polak-Ribiere method with
restarts.  However, I think that results with the conjugate-gradient 
method are very problem and implementation dependent.

I'll also mention another reference that might interest you.  Similar
ideas to those in Nazareth's work can be found, along with some
insightfull discussion, in

	"Restart Procedures for the conjugate gradient method,"
	M.J.D. Powell, Math. Prog. 12 (1977), pp. 241-254.


-- 
      Adam Schwartz        |    The opinions expressed here are my own 
 adams@eecs.berkeley.edu   |    and those of anyone who agrees with me.

        WWW Home Page: http://robotics.eecs.berkeley.edu/~adams


==============================================================================