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

#include <NOX_Solver_InexactTrustRegionBased.H>

Inheritance diagram for NOX::Solver::InexactTrustRegionBased:

Collaboration diagram for NOX::Solver::InexactTrustRegionBased:

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

virtual	~InexactTrustRegionBased ()
	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	TrustRegionType { Standard, Inexact }
	Type of Trust Region algorithm to use. More...

enum	InnerIterationReturnType { Converged, Unconverged, Failed }
	Return types for inner iteration status test. More...

enum	StepType { Newton, Cauchy, Dogleg }
	Enumerated list for each direction that may be required in the Trust region computation. More...

Protected Member Functions
virtual NOX::StatusTest::StatusType	iterateStandard ()
	"Standard" trust region implementation

virtual NOX::StatusTest::StatusType	iterateInexact ()
	"Inexact Trust Region"

virtual void	init ()
	Print out initialization information and calcuation the RHS.

virtual void	printUpdate ()
	Prints the current iteration information.

virtual void	invalid (const std::string &param, double value) const
	Print an error message and throw an error during parameter reads.

virtual void	throwError (const std::string &method, const std::string &mesage) const
	Print an error message and throw an error.

NOX::StatusTest::StatusType	checkStep (const NOX::Abstract::Vector &step, double &radius)
	Check to see if the current step is acceptable. If not, it reduces the trust region radius accordingly.

virtual double	computeNorm (const NOX::Abstract::Vector &v)
	Computes the norm of a given vector. More...

Protected Attributes
TrustRegionType	method
	Type of trust region algorithm to use.

Teuchos::RCP< NOX::GlobalData >	globalDataPtr
	Pointer to the global data object.

Teuchos::RCP< NOX::Utils >	utils
	Utils.

InnerIterationReturnType	innerIterationStatus
	Current status of the trust region inner iteration.

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 >	cauchyVecPtr
	Current cauchy direction pointer.

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

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

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

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

Teuchos::RCP < NOX::StatusTest::Generic >	testPtr
	Stopping test.

Teuchos::RCP < Teuchos::ParameterList >	paramsPtr
	Input parameters.

NOX::Direction::Utils::InexactNewton	inNewtonUtils
	Inexact Newton utitilities.

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

double	eta
	Current linear solve tolerance (inexact only).

double	eta_last
	Linear solve tolerance used in last iteration (inexact only).

NOX::StatusTest::StatusType	status
	Status of nonlinear solver.

NOX::StatusTest::CheckType	checkType
	Type of check to use for status tests. See NOX::StatusTest for more details.

StepType	stepType
	Type of step to be taken.

Teuchos::RCP < NOX::MeritFunction::Generic >	meritFuncPtr
	Stores merit function supplied by global data.

bool	useCauchyInNewtonDirection
	If set to true, the initial guess for the Newton direction computation will use the Cauchy direction as the initial guess.

bool	writeOutputParamsToList
	If set to true, statistics/counters will be output to the output list.

bool	useCounters
	If set to true, counters will be stored by the solver.

NOX::SolverStats::TrustRegionStats *	counters
	Counters for the algorithm.

bool	useAredPredRatio
	If set to true, the minimum improvement ratio condition uses an Ared/Pred approach.

bool	useDoglegMinimization
	If set to true, the $\tau$ parameter is minimized over the dogleg line segments instead of being computed at the trust regioin radius.

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.
  - "Inner Iteration Method" - Choice of trust region algorithm to use. Choices are:
    - "Standard Trust Region"
    - "Inexact Trust Region"
  - "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. Furthermore, 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 Min Model".
  - "Minimum Trust Region Radius" ( $\Delta_{\min}$ ) - Minimum allowable trust region radius. Defaults to 1.0e-6.
  - "Maximum Trust Region Radius" ( $\Delta_{\max}$ ) - Minimum 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 \| }$
  - "Use Cauchy in Newton Direction" - Boolean. Used only by the "Inexact Trust Region" algorithm. If set to true, the initial guess for the Newton direction computation will use the Cauchy direction as the initial guess. Defaults to false.
  - "Use Dogleg Segment Minimization" - Boolean. Used only by the "Inexact Trust Region" algorithm. If set to true, the $\tau$ parameter is minimized over the dogleg line segments instead of being computed at the trust regioin radius. Used only by the "Inexact Trust Region" algorithm. Defaults to false.
  - "Use Counters" - Boolean. If set to true, solver statistics will be stored. Defaults to true.
  - "Write Output Parameters" - Boolean. If set to true, the solver statistics will be written to the relevant "Output" sublists (see Output Parameters). Defaults to true.
  - "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 called "Output" will be created at the top level of the parameter list and contain the following general solver parameters:
  - "Nonlinear Iterations" - Number of nonlinear iterations
  - "2-Norm or Residual" - Two-norm of final residual
  A sublist called "Output" will be created in the "Trust Region" sublist and contain the following trust region specific output parameters:
  - "Number of Cauchy Steps" - Number of cauchy steps taken during the solve.
  - "Number of Newton Steps" - Number of Newton steps taken during the solve.
  - "Number of Dogleg Steps" - Number of Dogleg steps taken during the solve.
  - "Number of Trust Region Inner Iterations" - Number of inner iterations required to adjust the trust region radius.
  - "Dogleg Steps: Average Fraction of Newton Step Length" - Average value of the fraction a dogleg step took compared to the full Newton step. The fractional value is computed as $\mbox{frac} = \frac{\| d \|}{\| n\|}$ .
  - "Dogleg Steps: Average Fraction Between Cauchy and Newton Direction" - Average value of the fraction a dogleg step took between the Cauchy and Newton directions. This is the $\gamma$ variable in the standard dogleg algorithm and the $\tau$ parameter in the inexact dogleg algorithm. A value of 0.0 is a full step in the Cauchy direction and a value of 1.0 is a full step in the Newton direction.
    
    Author
    Tammy Kolda (SNL 8950), Roger Pawlowski (SNL 9233)

Member Enumeration Documentation

enum NOX::Solver::InexactTrustRegionBased::InnerIterationReturnType

protected

Return types for inner iteration status test.

Enumerator
Converged	Converged.
Unconverged	Unconverged.
Failed	Failed by hitting minimum radius bound.

enum NOX::Solver::InexactTrustRegionBased::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.

enum NOX::Solver::InexactTrustRegionBased::TrustRegionType

protected

Type of Trust Region algorithm to use.

Enumerator
Standard	Basic trust region method for nonlinear systems (Nocedal and Wright?).
Inexact	Inexact Trust region WITHOUT minimization of the local linear model over the line segments.

Constructor & Destructor Documentation

NOX::Solver::InexactTrustRegionBased::InexactTrustRegionBased	(	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 counters, globalDataPtr, init(), inNewtonUtils, meritFuncPtr, observer, paramsPtr, NOX::Solver::parseObserver(), Teuchos::rcp(), NOX::Direction::Utils::InexactNewton::reset(), Teuchos::ParameterList::sublist(), utils, and NOX::Solver::validateSolverOptionsSublist().

Member Function Documentation

double NOX::Solver::InexactTrustRegionBased::computeNorm ( const NOX::Abstract::Vector & v )

protectedvirtual

Computes the norm of a given vector.

Defaults to the L-2 norm but could use a user defined norm also.

References NOX::Abstract::Vector::norm().

void NOX::Solver::InexactTrustRegionBased::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 NOX::Utils::fill(), NOX::Utils::Parameters, and NOX::StatusTest::Unconverged.

NOX::StatusTest::StatusType NOX::Solver::InexactTrustRegionBased::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 Teuchos::ParameterList::set(), Teuchos::ParameterList::sublist(), and NOX::StatusTest::Unconverged.