NOX::LineSearch::NonlinearCG Class Reference

Use NonlinearCG linesearch. More...

#include <NOX_LineSearch_NonlinearCG.H>

Inheritance diagram for NOX::LineSearch::NonlinearCG:

Inheritance graph
[legend]
Collaboration diagram for NOX::LineSearch::NonlinearCG:

Collaboration graph
[legend]

List of all members.

Public Member Functions

 NonlinearCG (const Teuchos::RCP< NOX::GlobalData > &gd, Teuchos::ParameterList &params)
 Constructor.
 ~NonlinearCG ()
 Destructor.
bool reset (const Teuchos::RCP< NOX::GlobalData > &gd, Teuchos::ParameterList &params)
bool compute (NOX::Abstract::Group &newgrp, double &step, const NOX::Abstract::Vector &dir, const NOX::Solver::Generic &s)
 Perform a line search.

Private Member Functions

NOX::Abstract::VectorcomputeDirectionalDerivative (const Abstract::Vector &dir, const Abstract::Group &grp)
 Method for computing directional derivatives numerically.

Private Attributes

Teuchos::RCP< NOX::Utilsutils
 Printing utilities.
Teuchos::RCP
< NOX::Abstract::Vector
vecPtr
 Temporary Vector pointer used to compute directional derivatives.
Teuchos::RCP
< NOX::Abstract::Group
grpPtr
 Temporary Group pointer used to compute directional derivatives.
Teuchos::RCP
< NOX::StatusTest::FiniteValue
finiteValueTester
 Utililty object to test for NaN or Inf values for computed steps.


Detailed Description

Use NonlinearCG linesearch.

This is a simple linesearch intended to be used with NOX::Direction::NonlinearCG, which provides search direction $ d $, in computing an update to the current solution vector $ x_{new} = x_{old} + \lambda d $. It is designed to compute a step length $ \lambda $ consistent with the exact linesearch of Linear CG for linear problems, and it avoids use of matrices by employing a directional derivative (details below). The step length, $ \lambda $ is computed from a single evaluation of,

\[ \lambda = - \frac{F(x_{old})^T d}{d^T J(x_{old})d} \]

where $ J $ is the n x n Jacobian matrix. Explicit construction of $ J $ is avoided by performing the product $ Jd $ using a directional derivative (cf NOX::Epetra::MatrixFree):

\[ J(x_{old})d \approx \frac{F(x_{old} + \delta d) - F(x_{old})}{\delta} \]

where $ \delta = 10^{-6} (10^{-6} + ||x_{old}|| / ||d||) $ .

Derivation / Theory:

This linesearch is derived by attempting to achieve in a single step, the following minimization:

\[ \min_\lambda \phi(\lambda)\equiv\phi (x_{old}+ \lambda d) \]

where $ \phi $ is a merit function chosen (but never explicitly given) so that an equivalence to Linear CG holds, ie $ \nabla\phi(x) \leftrightarrow F(x) $. The minimization above can now be cast as an equation:

\[ \phi ' (\lambda) = \nabla\phi (x_{old}+ \lambda d)^T d = F(x_{old}+ \lambda d)^T d = 0~~. \]

An approximate solution to this equation can be obtained from a second-order expansion of

\[ \phi(\lambda) \]

,

\[ \phi(\lambda)\approx\phi (0) + \phi ' (0)\lambda + \phi '' (0) \frac{\lambda^2}{2} \]

from which it immediately follows

\[ \%lambda_{min} \approx - \frac{\phi ' (0)}{\phi '' (0)} = - \frac{F(x_{old})^T d}{d^T J(x_{old})d} \]

Input Parameters

The NonlinearCG linesearch is selected using:

"Line Search"

"Method" = "%NonlinearCG" [required]

Currently, no adjustable parameters exist for this linesarch.

References

linesearch is adapted from ideas presented in Section 14.2 of:

Jonathan Richard Shewchuk, "An Introduction to the Conjugate Gradient Method Without the Agonizing Pain," 1994. Though presented within the context of nonlinear optimization, the connection to solving nonlinear equation systems is made via the equivalence $ f'(x) \leftrightarrow F(x) $.

Author:
Russ Hooper, Org. 9233, Sandia National Labs

Definition at line 145 of file NOX_LineSearch_NonlinearCG.H.


Constructor & Destructor Documentation

NOX::LineSearch::NonlinearCG::NonlinearCG ( const Teuchos::RCP< NOX::GlobalData > &  gd,
Teuchos::ParameterList &  params 
)

Constructor.

Definition at line 51 of file NOX_LineSearch_NonlinearCG.C.

NOX::LineSearch::NonlinearCG::~NonlinearCG (  ) 

Destructor.

Definition at line 58 of file NOX_LineSearch_NonlinearCG.C.


Member Function Documentation

bool NOX::LineSearch::NonlinearCG::compute ( NOX::Abstract::Group grp,
double &  step,
const NOX::Abstract::Vector dir,
const NOX::Solver::Generic s 
) [virtual]

Perform a line search.

On input:

Parameters:
grp The initial solution vector, $x_{\rm old}$.
dir A vector of directions to be used in the line search, $d$.
s The nonlinear solver.
On output:
Parameters:
step The distance the direction was scaled, $ \lambda $.
grp The grp is updated with a new solution, $ x_{\rm new} $, resulting from the linesearch. Normally, for a single direction line search, this is computed as:

\[ x_{\rm new} = x_{\rm old} + \lambda d. \]

Ideally, $ \|F(x_{\rm new})\| < \|F(x_{\rm old})\| $ (e.g the final direction is a descent direction).

Note that the dir object is a std::vector. For typical line searches as described in the above equation, this vector is of size one. We have used a std::vector to allow for special cases of multi-directional line searches such as the Bader/Schnabel curvillinear line search.

Return value is true for a successful line search computation.

Implements NOX::LineSearch::Generic.

Definition at line 72 of file NOX_LineSearch_NonlinearCG.C.

References computeDirectionalDerivative(), NOX::Abstract::Group::computeF(), NOX::Abstract::Group::computeX(), NOX::Utils::fill(), finiteValueTester, NOX::Abstract::Group::getF(), NOX::Solver::Generic::getPreviousSolutionGroup(), NOX::Utils::InnerIteration, NOX::Abstract::Vector::innerProduct(), and utils.

NOX::Abstract::Vector & NOX::LineSearch::NonlinearCG::computeDirectionalDerivative ( const Abstract::Vector dir,
const Abstract::Group grp 
) [private]


Member Data Documentation

Printing utilities.

Definition at line 173 of file NOX_LineSearch_NonlinearCG.H.

Referenced by compute(), and computeDirectionalDerivative().

Temporary Vector pointer used to compute directional derivatives.

Definition at line 176 of file NOX_LineSearch_NonlinearCG.H.

Referenced by computeDirectionalDerivative().

Temporary Group pointer used to compute directional derivatives.

Definition at line 179 of file NOX_LineSearch_NonlinearCG.H.

Referenced by computeDirectionalDerivative().

Utililty object to test for NaN or Inf values for computed steps.

Definition at line 182 of file NOX_LineSearch_NonlinearCG.H.

Referenced by compute().


The documentation for this class was generated from the following files:

Generated on Wed Oct 21 14:28:47 2009 for Nonlinear Solver Project by  doxygen 1.5.9