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

#include <NOX_Solver_TrustRegionBased.H>

Inheritance diagram for NOX::Solver::TrustRegionBased:

Collaboration diagram for NOX::Solver::TrustRegionBased:

Public Member Functions
	TrustRegionBased (const Teuchos::RCP< NOX::Abstract::Group > &grp, const Teuchos::RCP< NOX::StatusTest::Generic > &tests, const Teuchos::RCP< Teuchos::ParameterList > &params)
	Constructor. More...

virtual	~TrustRegionBased ()
	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 void	reset ()
	Resets the solver for another solve. This resets the counters and status only. Uses the final solution from the last solve as the initial guess for the next solve. More...

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. More...

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 NOX::StatusTest::StatusType	getStatus () const
	Returns the current status of the solver.

virtual int	getNumIterations () const
	Get number of iterations.

virtual const Teuchos::ParameterList &	getList () const
	Return a reference to the solver parameters.

virtual Teuchos::RCP< const NOX::Abstract::Group >	getSolutionGroupPtr () const
	Return a RCP to the solution group.

virtual Teuchos::RCP< const NOX::Abstract::Group >	getPreviousSolutionGroupPtr () const
	Return a RCP to the previous solution group.

virtual Teuchos::RCP< const Teuchos::ParameterList >	getListPtr () const
	Return a RCP to the solver parameters.

virtual Teuchos::RCP< const NOX::SolverStats >	getSolverStatistics () const
	Return a RCP to the solver statistics.

Public Member Functions inherited from NOX::Solver::Generic
	Generic ()
	Constructor (does nothing)

virtual	~Generic ()
	Destructor (does nothing)

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 std::string &param, double value) const
	Print and error message and throw and error.

virtual void	printUpdate ()
	Prints the current iteration information.

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. More...

Teuchos::RCP < NOX::Abstract::Vector >	newtonVecPtr
	Current search direction.pointer. More...

Teuchos::RCP < NOX::Abstract::Vector >	cauchyVecPtr
	Current search direction.pointer. More...

Teuchos::RCP < NOX::Abstract::Vector >	aVecPtr
	Extra vector used in computations. More...

Teuchos::RCP < NOX::Abstract::Vector >	bVecPtr
	Extra vector used in computations. More...

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::RCP < NOX::Direction::Generic >	newtonPtr
	Newton Search Direction.

Teuchos::RCP < NOX::Direction::Generic >	cauchyPtr
	Cauchy Search Direction.

double	radius
	Radius of the trust region.

double	minRatio
	Minimum improvement ratio to accept step.

double	initRadius
	Initial trust region radius.

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.

Teuchos::RCP < NOX::MeritFunction::Generic >	meritFuncPtr
	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.

Teuchos::RCP< NOX::Observer >	observer
	Pointer to a user defined NOX::Observer object.

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 $\rho < \rho_{\min}$ and $\Delta > \Delta_{\min}$ , 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)|}$
```
</ul>
```
- 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$ .
```
<li> Otherwise if \form#238, then shrink the
     trust region: \form#239@_fakenl.

<li> Otherwise if \form#240 and \form#241@_fakenl, then expand the trust region: \form#242@_fakenl.

</ul>
```
  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.

Enumerator
Newton	Use the Newton direction.
Cauchy	Use the Cauchy direction.
Dogleg	Use the doglog direction.

Constructor & Destructor Documentation

TrustRegionBased::TrustRegionBased	(	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.

References globalDataPtr, init(), meritFuncPtr, observer, NOX::Solver::parseObserver(), Teuchos::rcp(), Teuchos::ParameterList::sublist(), utilsPtr, and NOX::Solver::validateSolverOptionsSublist().

Member Function Documentation

void TrustRegionBased::reset ( )

virtual

Resets the solver for another solve. This resets the counters and status only. Uses the final solution from the last solve as the initial guess for the next solve.

NOTE: All NOX solvers will call reset() automatically at teh beginning of the solve() method. We add the reset() method to the solver interface for the application to call in case the application needs to reset counters and status manually before the next call to solve() is made.

Implements NOX::Solver::Generic.

References dx, nIter, status, and NOX::StatusTest::Unconverged.

Referenced by solve().

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.

References NOX::Abstract::Group::getNormF(), nIter, observer, paramsPtr, reset(), Teuchos::ParameterList::set(), solnPtr, status, step(), Teuchos::ParameterList::sublist(), and NOX::StatusTest::Unconverged.