Re: Nonlinear CG
Peter Gottschling <[email protected]> Fri, 12 Jan 2007 16:06:09 -0500
| Newsgroups | gmane.comp.lib.mtl.devel |
|---|---|
| Message-ID | <[email protected]> |
Ben, Quasi-Newton methods are used when you don't have a gradient and need to guess it. If you have the gradient you can do a regular Newton method (as we learned it in school ;-) ) and don't need a matrix. Using CG or other Krylov-subspace methods to orthogonalize the search directions can speed up the convergence (but this depends certainly on the function). Peter On 12.01.2007, at 15:31, Ben FrantzDale wrote: > Peter, Andrew, > One of the minimizers I've used has documentation here: > www.nag.co.uk/numeric/CL/nagdoc_cl08/pdf/E04/e04dgc.pdf > fThe documentation says "[it] minimizes an unconstrained nonlinear > function of several variables using a pre-conditioned, limited memory > quasi-Newton conjugate gradient method. The function is intended for > use on large scale problems." I'm not sure how that algorithm would > compare with Newton-Krylov. > > I would assume a minimizer that can take advantage of grad f would > generally be better, but I am not a minimizer expert. (That, of > course, would require a DifferentiableScalarValuedFunction concept > rather than just the Matrix concept.) > > > > —Ben > > > > > On 1/12/07, Andrew Lumsdaine <[email protected]> wrote:One approach > that we used with ITL that worked fairly well was a matrix-free > Newton-Krylov approach (cf Brown and Hindmarsh). I think ITL has > example code for this in one of the subdirectories. >> >> Cheers, >> Andrew Lumsdaine >> >> On Jan 12, 2007, at 11:42 AM, Peter Gottschling wrote: >> >>> Hi Ben, >>> >>> I'm not an expert of non-linear solvers. Most things I have seen >>> (a while ago) were approximated Newton schemes with Jacobi matrix >>> was approximated from the operator. This requires (I think) that >>> one has a matrix representation of the operator which I'm afraid you >>> probably don't. >>> >>> Regarding pseudocode or free software I would need to search too. >>> >>> Best Regards, >>> Peter >>> >>> On 09.01.2007, at 18:38, Ben FrantzDale wrote: >>> >>>> Peter, >>>> Interesting. I'll start thinking about it. >>>> >>>> I think most nonlinear CG flavors require one additional concept: >>>> a function, >>>> func(const vector& x, scalar& result, vector& result_gradient), >>>> which computes f(x) and f'(x). >>>> >>>> I actually don't want to use PETSc data. My state vector >>>> represents atom positions as well as continuum displacements, >>>> stored separately, so basically it's a heterogeneous mess. (This is >>>> part of the reason a generic approach seems so appealing – I should >>>> be able to abstract that heterogeneity away.) >>>> >>>> Do you know where I might find pseudocode (or just Free code) for >>>> of algorithm? >>>> >>>> —Ben >>>> >>>> >>>> On 1/9/07, Peter Gottschling < [email protected] > wrote:Dear >>>> Ben, >>>>> >>>>> As far as I know, non-linear solvers does not exist in ITL. It >>>>> is an >>>>> excellent idea and we will likely work on it in the future. If >>>>> you >>>>> want to work on this, I'd be happy to support you. >>>>> >>>>> I don't know if that helps you, I've written an interface between >>>>> PETSc >>>>> and parallel BGL so that one can read out parallel PETSc matrices >>>>> from >>>>> generic libraries and also access to distributed PETSc vector >>>>> without >>>>> copying them. However, it sounds more that you want to use PETSc >>>>> data >>>>> with in a clearer way than I did. ;-) >>>>> >>>>> Best Regards, >>>>> Peter >>>>> >>>>> On 09.01.2007, at 18:01, Ben FrantzDale wrote: >>>>> >>>>> > Dear ITL-devel, >>>>> > I'm glad I finally found ITL. It looks like it could be the >>>>> Right Way >>>>> > to solve a bunch of problems that various closed-source Fortran >>>>> > libraries have attempted. >>>>> > >>>>> > I am interested in solving large nonlinear minimization >>>>> problems in >>>>> > parallel. Presently we are experimenting with several CG >>>>> solvers. The >>>>> > work, but all of them want to see the state vector as a single >>>>> > contiguous array of doubles. The ITL example using PETSc in >>>>> parallel >>>>> > makes me think there are interesting possibilities for large >>>>> nonlinear >>>>> > problems as well. >>>>> > >>>>> > The ITL distribution includes two nonlinear examples, but all >>>>> of the >>>>> > solvers appear to be linear. Has anyone extended ITL to do >>>>> nonlinear >>>>> > minimization? >>>>> > >>>>> > Again, great work. >>>>> > >>>>> > Thanks, >>>>> > Ben FrantzDale_______________________________________________ >>>>> > This list is archived at >>>>> http://www.osl.iu.edu/MailArchives/mtl-devel/ >>>>> ------------ >>>>> Peter Gottschling, Ph.D. >>>>> Research Associate >>>>> Open Systems Laboratory >>>>> Indiana University >>>>> 135 Lindley Hall >>>>> Bloomington, IN 47405 >>>>> Tel.: +1-812-855-3608 Fax: +1-812-856-0853 >>>>> http://www.osl.iu.edu/~pgottsch >>>>> >>>>> >>>>> _______________________________________________ >>>>> This list is archived at >>>>> http://www.osl.iu.edu/MailArchives/mtl-devel/ >>>> _______________________________________________ >>>> This list is archived at >>>> http://www.osl.iu.edu/MailArchives/mtl-devel/ >>> ------------ >>> Peter Gottschling >>> Research Associate >>> Open Systems Laboratory >>> Indiana University >>> 135 Lindley Hall >>> Bloomington, IN 47405 >>> Tel.: +1-812-855-3608 Fax: +1-812-856-0853 >>> http://www.osl.iu.edu/~pgottsch >>> _______________________________________________ >>> This list is archived at >>> http://www.osl.iu.edu/MailArchives/mtl-devel/ >> >> >> _______________________________________________ >> This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/ >> > _______________________________________________ > This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/ ------------ Peter Gottschling Research Associate Open Systems Laboratory Indiana University 135 Lindley Hall Bloomington, IN 47405 Tel.: +1-812-855-3608 Fax: +1-812-856-0853 http://www.osl.iu.edu/~pgottsch _______________________________________________ This list is archived at http://www.osl.iu.edu/MailArchives/mtl-devel/