NOX::Solver::TrustRegionBased Class Reference

Newton-like solver using a trust region. More...

#include <NOX_Solver_TrustRegionBased.H>

Inheritance diagram for NOX::Solver::TrustRegionBased:

[legend]Collaboration diagram for NOX::Solver::TrustRegionBased:[legend]List of all members.


Public Member Functions
	TrustRegionBased (NOX::Abstract::Group &xgrp, NOX::StatusTest::Generic &t, NOX::Parameter::List &p)
	Constructor.
virtual	~TrustRegionBased ()
	Destructor.
virtual bool	reset (NOX::Abstract::Group &xgrp, NOX::StatusTest::Generic &t, NOX::Parameter::List &p)
	Reset the nonlinear solver for a new solve.
virtual bool	reset (NOX::Abstract::Group &xgrp, NOX::StatusTest::Generic &t)
	A soft reset of the nonlinear solver for a new problem.
virtual NOX::StatusTest::StatusType	getStatus ()
	Check current convergence and failure status.
virtual NOX::StatusTest::StatusType	iterate ()
	Do one nonlinear method iteration 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 NOX::Parameter::List &	getParameterList () const
	Return a refernece to the solver parameters.
Protected Types
enum	StepType { Newton, Cauchy, Dogleg }
	Enumerated list for each direction that may be required in the Trust region computation. More...
Protected Member Functions
virtual void	init ()
	Print out initialization information and calcuation the RHS.
virtual void	invalid (const string &param, double value) const
	Print and error message and throw and error.
virtual void	printUpdate ()
	Prints the current iteration information.
Protected Attributes
NOX::Abstract::Group *	solnPtr
	Current solution.
NOX::Abstract::Group *	oldSolnPtr
	Previous solution pointer.
NOX::Abstract::Group &	oldSoln
	Previous solution reference.
NOX::Abstract::Vector *	newtonVecPtr
	Current search direction.pointer.
NOX::Abstract::Vector &	newtonVec
	Current Newton direction.reference.
NOX::Abstract::Vector *	cauchyVecPtr
	Current search direction.pointer.
NOX::Abstract::Vector &	cauchyVec
	Current Cauchy direction.reference.
NOX::Abstract::Vector *	aVecPtr
	Extra vector used in computations.
NOX::Abstract::Vector &	aVec
	Extra vector.
NOX::Abstract::Vector *	bVecPtr
	Extra vector used in computations.
NOX::Abstract::Vector &	bVec
	Extra vector.
NOX::StatusTest::Generic *	testPtr
	Stopping test.
NOX::Parameter::List *	paramsPtr
	Input parameters.
NOX::Utils	utils
	Printing Utils.
NOX::Direction::Manager	newton
	Newton Search Direction.
NOX::Direction::Manager	cauchy
	Cauchy Search Direction.
double	radius
	Radius of the trust region.
double	minRatio
	Minimum improvement ratio to accept step.
double	minRadius
	Minimum trust region radius.
double	maxRadius
	Maximum trust region radius.
double	contractTriggerRatio
	ratio < alpha triggers contraction
double	expandTriggerRatio
	ratio > beta triggers expansion
double	expandFactor
	Expansion factor.
double	contractFactor
	Constraction factor.
double	recoveryStep
double	newF
	Value of at current solution.
double	oldF
	Value of at previous solution.
double	dx
	norm(xnew - xold)
int	nIter
	Number of nonlinear iterations.
NOX::StatusTest::StatusType	status
	Status of nonlinear solver.
StepType	stepType
	Type of step to be taken.
NOX::Parameter::UserNorm *	userNormPtr
	Stores a user supplied norm if supplied in the parameter list.
NOX::Parameter::MeritFunction *	userMeritFuncPtr
	Stores a user supplied merit function if supplied in the parameter list.
bool	useAredPredRatio
	If set to true, the minimum improvement ratio condition uses an Ared/Pred approach.
NOX::Parameter::PrePostOperator *	prePostOperatorPtr
	Pointer to a user defined NOX::Abstract::PrePostOperator object.
bool	havePrePostOperator
	True if a PrePostOperator was registered with the solver.

Detailed Description

Newton-like solver using a trust region.

Our goal is to solve: $ F(x) = 0, $ where $F:\Re^n \rightarrow \Re^n$ . Alternatively, we might say that we wish to solve

$\min f(x) \equiv \frac{1}{2} \|F(x)\|^2_2.$

The trust region subproblem (TRSP) at iteration $k$ is given by

$\min \; m_k(s) \equiv f_k + g_k^T d + \frac{1}{2} d^T B_k d, \mbox{ s.t. } \|d\| \leq \Delta_k \quad \mbox{(TRSP)}$

where

$f_k = f(x_k) = \frac{1}{2} \|F(x_k)\|^2_2$ ,
$g_k = \nabla f(x_k) = J(x_k)^T F(x_k)$ ,
$B_k = J(x_k)^T J(x_k) \approx \nabla^2 f(x_k)$ ,
is the Jacobian of at , and
$\Delta_k$ is the trust region radius.

The "improvement ratio" for a given step $ s $ is defined as

$\rho = \displaystyle\frac{ f(x_k) - f(x_k + d) } { m_k(0) - m_k(d) }$

An iteration consists of the following steps.

Compute Newton-like direction:
Compute Cauchy-like direction:
If this is the first iteration, initialize $\Delta$ as follows: If $\|n\|_2 < \Delta_{\min}$ , then $\Delta = 2 \Delta_{\min}$ ; else, $\Delta = \|n\|_2$ .
Initialize $\rho = -1$
While and , do the following.
- Compute the direction as follows:
  - If $\|n\|_2 < \Delta$ , then take a Newton step by setting
  - Otherwise if $\|c\|_2 > \Delta$ , then take a Cauchy step by setting $d = \displaystyle\frac{\Delta}{\|c\|_2} c$
  - Otherwise, take a Dog Leg step by setting $d = (1-\gamma) c + \gamma n$ where $\gamma = \displaystyle\frac {-c^T a + \sqrt{ (c^Ta)^2 - (c^Tc - \Delta^2) a^Ta}}{a^Ta}$ with .
- Set $x_{\rm new} = x + d$ and calculate $f_{\rm new}$
- If $f_{\rm new} \geq f$ , then $\rho = -1$ Otherwise $\rho = \displaystyle \frac {f - f_{\rm new}} {| d^T J F + \frac{1}{2} (J d)^T (J d)|}$
Update the solution: $x = x_{\rm new}$
Update trust region:
- If $\rho < \rho_{\rm s}$ and $\|n\|_2 < \Delta$ , then shrink the trust region to the size of the Newton step: $\Delta = \|n\|_2$ .
- Otherwise if $\rho < \rho_{\rm s}$ , then shrink the trust region: $\Delta = \max \{ \beta_{\rm s} \Delta, \Delta_{\min} \}$ .
- Otherwise if $\rho > \rho_{\rm e}$ and $\|d\|_2 = \Delta$ , then expand the trust region: $\Delta = \min \{ \beta_{\rm e} \Delta, \Delta_{\rm max} \}$ .

Input Paramters

The following parameters should be specified in the "Trust Region" sublist based to the solver.

"Direction" - Sublist of the direction parameters for the Newton point, passed to the NOX::Direction::Manager constructor. If this sublist does not exist, it is created by default. Furthermore, if "Method" is not specified in this sublist, it is added with a value of "Newton".

"Cauchy %Direction" - Sublist of the direction parameters for the Cauchy point, passed to the NOX::Direction::Manager constructor. If this sublist does not exist, it is created by default. Furthremore, if "Method" is not specified in this sublist, it is added with a value of "Steepest Descent" Finally, if the sub-sublist "Steepest Descent" does not exist, it is created and the parameter "Scaling Type" is added and set to "Quadratic".

"Minimum Trust Region Radius" ( $\Delta_{\min}$ ) - Minimum allowable trust region radius. Defaults to 1.0e-6.

"Maximum Trust Region Radius" ( $\Delta_{\max}$ ) - Maximum allowable trust region radius. Defaults to 1.0e+10.

"Minimum Improvement Ratio" ( $\rho_{\min}$ ) - Minimum improvement ratio to accept the step. Defaults to 1.0e-4.

"Contraction Trigger Ratio" ( $\rho_{\rm s}$ ) - If the improvement ratio is less than this value, then the trust region is contracted by the amount specified by the "Contraction Factor". Must be larger than "Minimum Improvement Ratio". Defaults to 0.1.

"Contraction Factor" ( $\beta_{\rm s}$ ) - See above. Defaults to 0.25.

"Expansion Trigger Ratio" ( $\rho_{\rm e}$ ) - If the improvement ratio is greater than this value, then the trust region is contracted by the amount specified by the "Expansion Factor". Defaults to 0.75.

"Expansion Factor" ( $\beta_{\rm e}$ ) - See above. Defaults to 4.0.

"Recovery Step" - Defaults to 1.0.

"Use Ared/Pred Ratio Calculation" (boolean) - Defaults to false. If set to true, this option replaces the algorithm used to compute the improvement ratio, , as described above. The improvement ratio is replaced by an "Ared/Pred" sufficient decrease criteria similar to that used in line search algorithms (see Eisenstat and Walker, SIAM Journal on Optimization V4 no. 2 (1994) pp 393-422):
- $\rho = \frac{\|F(x) \| - \| F(x + d) \| } {\| F(x) \| - \| F(x) + Jd \| }$

"Solver Options" - Sublist of general solver options.
- "User Defined Pre/Post Operator" is supported. See NOX::Parameter::PrePostOperator for more details.

Output Paramters

A sublist for output parameters called "Output" will be created and contain the following parameters:

"Nonlinear Iterations" - Number of nonlinear iterations

"2-Norm or Residual" - Two-norm of final residual

Author:: Tammy Kolda (SNL 8950), Roger Pawlowski (SNL 9233)

Member Enumeration Documentation

enum NOX::Solver::TrustRegionBased::StepType [protected]

Enumerated list for each direction that may be required in the Trust region computation.

Enumeration values:

Newton Use the Newton direction.

Cauchy Use the Cauchy direction.

Dogleg Use the doglog direction.

Constructor & Destructor Documentation

TrustRegionBased::TrustRegionBased ( NOX::Abstract::Group & xgrp,

NOX::StatusTest::Generic & t,

NOX::Parameter::List & p

)

Constructor.
See reset() for description.

Member Function Documentation

bool TrustRegionBased::reset ( NOX::Abstract::Group & xgrp,

NOX::StatusTest::Generic & t

) [virtual]

A soft reset of the nonlinear solver for a new problem.
This is a light-weight version of reset that takes no parameter list. Therefore, this reset only resets counters, the initial guess (contained in the grp argument) and new status tests (contained in the tests argument).
This reset allows problems to bypass the potentially time consuming parsing of the parameter lists.
Implements NOX::Solver::Generic.

bool TrustRegionBased::reset ( NOX::Abstract::Group & xgrp,

NOX::StatusTest::Generic & t,

NOX::Parameter::List & p

) [virtual]

Reset the nonlinear solver for a new solve.

Parameters:

grp On input, contains the intial guess. On output, contains the solution.

tests Status tests to check for convergence or failure. These tests will be modified by the solver.

params List of parameters. These parameters will be modified by the solver.

Note:
All the objects passed to reset() will be modified.
The group object will be cloned via NOX::Abstract::Group::clone(), and the vectors within will also be individually cloned via NOX::Abstract::Vector::clone().

Warning:
If the contents of grp, tests, or params are modified by the calling program after calling reset(), then the behavior of iterate() and solve() are completely undefined. To remedy this, call reset() again with the modified objects.

Implements NOX::Solver::Generic.

NOX::StatusTest::StatusType TrustRegionBased::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.

Member Data Documentation

NOX::Abstract::Vector* NOX::Solver::TrustRegionBased::aVecPtr [protected]

Extra vector used in computations.
We have both a pointer and a reference because we need to create a DERIVED object and then want to have a reference to it.

NOX::Abstract::Vector* NOX::Solver::TrustRegionBased::bVecPtr [protected]

Extra vector used in computations.
We have both a pointer and a reference because we need to create a DERIVED object and then want to have a reference to it.

NOX::Abstract::Vector* NOX::Solver::TrustRegionBased::cauchyVecPtr [protected]

Current search direction.pointer.
We have both a pointer and a reference because we need to create a DERIVED object and then want to have a reference to it.

NOX::Abstract::Vector* NOX::Solver::TrustRegionBased::newtonVecPtr [protected]

Current search direction.pointer.
We have both a pointer and a reference because we need to create a DERIVED object and then want to have a reference to it.

NOX::Abstract::Group* NOX::Solver::TrustRegionBased::oldSolnPtr [protected]

Previous solution pointer.
We have both a pointer and a reference because we need to create a DERIVED object and then want to have a reference to it.

double NOX::Solver::TrustRegionBased::recoveryStep [protected]

Take a step of this length in the Newton direction if the trust-region search fails

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

NOX_Solver_TrustRegionBased.H
NOX_Solver_TrustRegionBased.C

Generated on Thu Sep 18 12:43:34 2008 for NOX by

1.3.9.1

NOX::Solver::TrustRegionBased Class Reference

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation