NOX::Solver::TensorBased Class Reference

Nonlinear solver based on a rank-1 tensor method. More...

#include <NOX_Solver_TensorBased.H>

Inheritance diagram for NOX::Solver::TensorBased:

[legend]Collaboration diagram for NOX::Solver::TensorBased:


Public Member Functions
	TensorBased (const Teuchos::RCP< NOX::Abstract::Group > &grp, const Teuchos::RCP< NOX::StatusTest::Generic > &tests, const Teuchos::RCP< Teuchos::ParameterList > &params)
	Constructor.
virtual	~TensorBased ()
	Destructor.
virtual void	reset (const NOX::Abstract::Vector &initialGuess, const Teuchos::RCP< NOX::StatusTest::Generic > &tests)
	Resets the solver, sets a new status test, and sets a new initial guess.
virtual void	reset (const NOX::Abstract::Vector &initialGuess)
	Resets the solver and sets a new initial guess.
virtual NOX::StatusTest::StatusType	getStatus ()
	Check current convergence and failure status.
virtual NOX::StatusTest::StatusType	step ()
	Do one nonlinear step in the iteration sequence and return status.
virtual NOX::StatusTest::StatusType	solve ()
	Solve the nonlinear problem and return final status.
virtual const NOX::Abstract::Group &	getSolutionGroup () const
	Return a reference to the current solution group.
virtual const NOX::Abstract::Group &	getPreviousSolutionGroup () const
	Return a reference to the previous solution group.
virtual int	getNumIterations () const
	Get number of iterations.
virtual const Teuchos::ParameterList &	getList () const
	Return a refernece to the solver parameters.
Protected Types
	TensorStep
	NewtonStep
	Curvilinear
	Standard
	Dual
	FullStep
	Newton
	ArmijoGoldstein
	Sufficient decrease condition.
	AredPred
	Ared/Pred condition.
	None
	Just accept the first step.
	Halving
	Quadratic
	Constant
	Use a constant value.
	LastComputedStep
	Use the last value computed in the line search algorithm.
enum	StepType { TensorStep, NewtonStep }
	Types of steps.
enum	LineSearchType { Curvilinear, Standard, Dual, FullStep, Newton }
	Enumerated list for each type of line search.
enum	ConvergenceCriteriaType { ArmijoGoldstein, AredPred, None }
	Algorithms used to determine convergence of the line search. More...
enum	LambdaSelectionType { Halving, Quadratic }
	Types of lambda selection.
enum	RecoveryStepType { Constant, LastComputedStep }
	Type of recovery step to use. More...
Protected Member Functions
virtual void	init ()
	Print out initialization information.
virtual void	printUpdate ()
	Prints the current iteration information.
virtual bool	reset (const Teuchos::RCP< NOX::Abstract::Group > &grp, const Teuchos::RCP< NOX::StatusTest::Generic > &tests, const Teuchos::RCP< Teuchos::ParameterList > &params)
	Constructor initialization routine.
bool	computeTensorDirection (NOX::Abstract::Group &soln, const NOX::Solver::Generic &solver)
	Subroutine for computing the tensor and Newton directions.
double	calculateBeta (double qa, double qb, double qc, double &qval, double &lambdaBar, double lambda=1.0) const
	Subroutine for calculating beta.
bool	computeCurvilinearStep (NOX::Abstract::Vector &dir, const NOX::Abstract::Group &soln, const NOX::Solver::Generic &s, double &lambda)
	Subroutine for computing the curvilinear step.
bool	implementGlobalStrategy (NOX::Abstract::Group &newGrp, double &step, const NOX::Solver::Generic &s)
	Subroutine for executing the tensor linesearch.
bool	performLinesearch (NOX::Abstract::Group &newsoln, double &step, const NOX::Abstract::Vector &lsDir, const NOX::Solver::Generic &s)
	Performs a standard tensor linesearch (tensor or Newton direction).
double	getNormModelResidual (const NOX::Abstract::Vector &dir, const NOX::Abstract::Group &soln, bool isTensorModel) const
	Compute the residual norm of the local model.
void	printDirectionInfo (std::string dirName, const NOX::Abstract::Vector &dir, const NOX::Abstract::Group &soln, bool isTensorModel) const
	Print pertinent information about the direction.
double	getDirectionalDerivative (const NOX::Abstract::Vector &dir, const NOX::Abstract::Group &soln) const
	Calculate the directional derivative.
double	selectLambda (double newf, double oldf, double oldfprime, double lambda)
	Select lambda for linesearch (quadratic or halving).
void	throwError (const string &functionName, const string &errorMsg) const
	Throw an error with a method's name and error message.
Protected Attributes
Teuchos::RCP< NOX::GlobalData >	globalDataPtr
	Pointer to the global data object.
Teuchos::RCP< NOX::Utils >	utilsPtr
	Printing Utils.
Teuchos::RCP< NOX::Abstract::Group >	solnPtr
	Current solution.
Teuchos::RCP< NOX::Abstract::Group >	oldSolnPtr
	Previous solution pointer.
Teuchos::RCP< NOX::Abstract::Vector >	newtonVecPtr
	Current Newton direction (pointer).
Teuchos::RCP< NOX::Abstract::Vector >	tensorVecPtr
	Current tensor direction (pointer).
Teuchos::RCP< NOX::Abstract::Vector >	aVecPtr
	Current tensor term vector (pointer).
Teuchos::RCP< NOX::Abstract::Vector >	sVecPtr
	Vector to previous point (pointer).
Teuchos::RCP< NOX::Abstract::Vector >	tmpVecPtr
	Working vector (pointer).
Teuchos::RCP< NOX::Abstract::Vector >	residualVecPtr
	Residual vector (pointer).
Teuchos::RCP< NOX::StatusTest::Generic >	testPtr
	Stopping test.
NOX::StatusTest::CheckType	checkType
	Type of check to use for status tests. See NOX::StatusTest for more details.
Teuchos::RCP< Teuchos::ParameterList >	paramsPtr
	Input parameters.
Teuchos::ParameterList *	linearParamsPtr
	Parameters for the Linear Solver of the local model.
double	stepSize
	Current step.
double	beta
	Value of sc'*dt.
int	nIter
	Number of nonlinear iterations.
NOX::StatusTest::StatusType	status
	Status of nonlinear solver.
StepType	requestedBaseStep
	Flag for the base direction to compute after the first iteration.
LineSearchType	lsType
	Choice of line search.
ConvergenceCriteriaType	convCriteria
	Choice of convergence criteria (currently unused).
LambdaSelectionType	lambdaSelection
	Flag for lambda selection (Halving/Quadratic).
RecoveryStepType	recoveryStepType
	Choice of the recovery step type; uses "Recovery Step Type" parameter.
bool	useModifiedMethod
	Flag for using modifications that force quadratic to have real root.
bool	isNewtonDirection
	Flag for Newton direction.
bool	doRescue
	Flag for rescuing Linear Solver from a bad solve.
double	minStep
	Minimum step length (i.e., when we give up).
double	defaultStep
	Default step.
double	recoveryStep
	Default step for linesearch failure.
int	maxIters
	Maximum iterations.
double	alpha
	Scaling factor for the Armijo-Goldstein condition.
double	sTinvJF
	Value of s'inv(J)F.
double	sTinvJa
	Value of s'inv(J)a.
NOX::LineSearch::Utils::Printing	print
	Common line search printing utilities.
NOX::LineSearch::Utils::Counters	counter
	Common common counters for line searches.
NOX::LineSearch::Utils::Slope	slopeObj
	Common slope calculations for line searches.
int	numJvMults
	Counter for number of Jacobian-vector products.
int	numJ2vMults
	Counter for number of "double" Jacobian-vector products.
NOX::Solver::PrePostOperator	prePostOperator
	Pointer to a user defined NOX::Abstract::PrePostOperator object.

Detailed Description

Nonlinear solver based on a rank-1 tensor method.

Solves $F(x)=0$ using a rank-1 tensor method and a linesearch globalization.

At the kth nonlinear iteration, the solver does the following:

Computes the tensor direction by finding the root or smallest magnitude minimizer of the local model
$M_T(x_k+d) = F_k + J_kd + a_k(s_k^Td)^2,$
where
$a_k = 2(F_{k-1} - F_k - J_ks_k) / (s_k^Ts_k)^2$
and
$s_k = s_{k-1} - s_k.$
Modifies the step according to a global strategy and updates as $x_{k+1} = x_k + d(\lambda)$ via a linesearch method, where $d(\lambda)$ is some function of $\lambda$ . For instance, the curvilinear step $d_{\lambda T}$ is a function of the linesearch parameter $\lambda$ and is a parametric step that spans the directions of the tensor step and the Newton step. At $\lambda=1$ , the curvilinear step equals the full tensor step, and as $\lambda$ nears 0, the curvilinear step approaches the Newton direction. This step provides a monotonic decrease in the norm of the local tensor model as $\lambda$ varies from 0 to 1.

The solver iterates until the status tests (see NOX::StatusTest) determine either failure or convergence.

Input Parameters

To use this solver, set the "Nonlinear Solver" parameter to be "Tensor Based". Then, specify the following sublists with the appropriate parameters as indicated below.

"Direction" - Sublist of the direction parameters, passed to the NOX::Direction::Factory constructor. Defaults to an empty list.
- "Method" - Name of the direction to be computed in this solver. "Tensor" and "Newton" are the only two valid choices. A sublist by this name specifies all of the parameters to be passed to the linear solver. See below under "Linear Solver".
- "Rescue Bad Newton Solve" (Boolean) - If the linear solve does not meet the tolerance specified by the forcing term, then use the step anyway. Defaults to true.
- "Linear Solver" - Sublist for the specific linear solver parameters that are passed to NOX::Abstract::Group::computeNewton() and NOX::Abstract::Group::applyJacobianInverse(). "Linear Solver" is itself a sublist of the list specified in "Method" above (i.e., "Tensor" or "Newton"). Below is a partial list of standard parameters usually available in common linear solvers. Check with the specific linear solver being used for other parameters.
  - "Max Iterations" - Maximum number of Arnoldi iterations (also max Krylov space dimension)
  - "Tolerance" - Relative tolerance for solving local model [default = 1e-4]
  - "Output Frequency" - Print output at every number of iterations [default = 20]
"Line Search" - Sublist of the line search parameters. Because the tensor step is not guaranteed to be a descent direction on the function, not all "basic" line search approaches would be appropriate. Thus, the LineSearch classes available to Newton's method (e.g., Polynomial, More-Thuente) are not used here. Instead, this solver class approriately handles technical considerations for tensor methods with its own set of global strategies. The following parameters specify the specific options for this line search:
- "Method" - Name of the line search available to tensor methods Valid choices are:
  - "Curvilinear" - Backtrack along the "curvilinear" path that spans the tensor direction and the Newton direction and that maintains monotonicity on the tensor model. Recommended because it tends to be more robust and efficient than the other choices. [Default]
  - "Standard" - Backtrack along tensor direction unless it is not a descent direction, in which case backtrack along Newton direction.
  - "Dual" - Backtrack along both the Newton and tensor directions and choose the better of the two.
  - "Full Step" - Only use the full step and do not backtrack along both the Newton and tensor directions and choose the better of the two.
- "Lambda selection" - Flag for how to calculate the next linesearch parameter lambda. Valid choices are "Quadratic" and "Halving" (default). Quadratic constructs a quadratic interpolating polynomial from the last trial point and uses the minimum of this function as the next trial lambda (bounded by 0.1). Halving divides the linesearch parameter by 2 before each trial, which is simpler but tends to generate longer steps than quadratic.
- "Default Step" - Starting value of the linesearch parameter (defaults to 1.0)
- "Minimum Step" - Minimum acceptable linesearch parameter before the linesearch terminates (defaults to 1.0e-12). If there are many linesearch failures, then lowering this value is one thing to try.
- "Recovery Step Type" - Determines the step size to take when the line search fails. Choices are:
  - "Constant" [default] - Uses a constant value set in "Recovery Step".
  - "Last Computed Step" - Uses the last value computed by the line search algorithm.
- "Recovery Step" - Step parameter to take when the line search fails (defaults to value for "Default Step")
- "Max Iters" - Maximum number of iterations (i.e., backtracks)
"Solver Options" - Sublist of general solver options.
- "User Defined Pre/Post Operator" is supported. See NOX::Parameter::PrePostOperator for more details.

Output Parameters

Every time solve() is called, a sublist for output parameters called "Output" will be created and will contain the following parameters:

"Nonlinear Iterations" - Number of nonlinear iterations
"2-Norm of Residual" - L-2 norm of the final residual .

References

B. W. Bader, Tensor-Krylov methods for solving large-scale systems of nonlinear equations, Ph.D. Thesis, 2003, University of Colorado, Boulder, Colorado.
B. W. Bader, Tensor-Krylov methods for solving large-scale systems of nonlinear equations, submitted to SIAM J. Numer. Anal.
B. W. Bader and R. B. Schnabel, Curvilinear linesearch for tensor methods, SISC, 25(2):604-622.
R. B. Schnabel and P. D. Frank, Tensor methods for nonlinear equations, SIAM J. Numer. Anal., 21(5):815-843.

Author:: Brett Bader (SNL 9233)

Member Enumeration Documentation

enum NOX::Solver::TensorBased::ConvergenceCriteriaType [protected]

Algorithms used to determine convergence of the line search.

Enumerator:

ArmijoGoldstein	Sufficient decrease condition.
AredPred	Ared/Pred condition.
None	Just accept the first step.

enum NOX::Solver::TensorBased::RecoveryStepType [protected]

Type of recovery step to use.

Enumerator:

Constant	Use a constant value.
LastComputedStep	Use the last value computed in the line search algorithm.

Constructor & Destructor Documentation

NOX::Solver::TensorBased::TensorBased	(	const Teuchos::RCP< NOX::Abstract::Group > &	grp,
		const Teuchos::RCP< NOX::StatusTest::Generic > &	tests,
		const Teuchos::RCP< Teuchos::ParameterList > &	params
	)

Constructor.

See reset() for description.

Member Function Documentation

NOX::StatusTest::StatusType NOX::Solver::TensorBased::solve ( ) [virtual]

Solve the nonlinear problem and return final status.

By "solve", we call iterate() until the NOX::StatusTest value is either NOX::StatusTest::Converged or NOX::StatusTest::Failed.

Implements NOX::Solver::Generic.