NOX::LineSearch::Polynomial Class Reference

A polynomial line search, either quadratic or cubic. More...

#include <NOX_LineSearch_Polynomial.H>

Inheritance diagram for NOX::LineSearch::Polynomial:

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

Collaboration graph
[legend]

List of all members.

Public Member Functions

 Polynomial (const Teuchos::RCP< NOX::GlobalData > &gd, Teuchos::ParameterList &params)
 Constructor.
 ~Polynomial ()
 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.

Protected Types

enum  SufficientDecreaseType { ArmijoGoldstein, AredPred, None }
 Types of sufficient decrease conditions used by checkConvergence(). More...
enum  InterpolationType { Quadratic, Cubic, Quadratic3 }
 Interpolation types used by compute(). More...
enum  RecoveryStepType { Constant, LastComputedStep }
 Type of recovery step to use. More...

Protected Member Functions

bool checkConvergence (double newValue, double oldValue, double oldSlope, double step, double eta, int nIters, int nNonlinearIters) const
 Returns true if converged.
bool updateGrp (NOX::Abstract::Group &newGrp, const NOX::Abstract::Group &oldGrp, const NOX::Abstract::Vector &dir, double step) const
 Updates the newGrp by computing a new x and a new F(x).
double computeValue (const NOX::Abstract::Group &grp, double phi)
 Compute the value used to determine sufficient decrease.
void printOpeningRemarks () const
 Used to print opening remarks for each call to compute().
void printBadSlopeWarning (double slope) const
 Prints a warning message saying that the slope is negative.

Protected Attributes

SufficientDecreaseType suffDecrCond
 Choice for sufficient decrease condition; uses "Sufficient Decrease Condition" parameter.
InterpolationType interpolationType
 Choice of interpolation type; uses "Interpolation Type" parameter.
RecoveryStepType recoveryStepType
 Choice of the recovery step type; uses "Recovery Step Type" parameter.
double minStep
 Minimum step length (i.e., when we give up); uses "Mimimum Step" parameter.
double defaultStep
 Default step; uses "Default Step" parameter.
double recoveryStep
 Default step for linesearch failure; uses "Recovery Step" parameter.
int maxIters
 Maximum iterations; uses "Max Iters" parameter.
double alpha
 The $ \alpha $ for the Armijo-Goldstein condition, or the $ \alpha $ for the Ared/Pred condition; see checkConvergence(). Uses "Alpha Factor" parameter.
double minBoundFactor
 Factor that limits the minimum size of the new step based on the previous step; uses "Min Bounds Factor" parameter.
double maxBoundFactor
 Factor that limits the maximum size of the new step based on the previous step; uses "Max Bounds Factor" parameter.
bool doForceInterpolation
 True is we should force at least one interpolation step; uses "Force Interpolation" parameter.
int maxIncreaseIter
 No increases are allowed if the number of nonlinear iterations is greater than this value; uses "Maximum Iterations for Increase".
bool doAllowIncrease
 True if we sometimes allow an increase(!) in the decrease measure, i.e., maxIncreaseIter > 0.
double maxRelativeIncrease
 Maximum allowable relative increase for decrease meausre (if allowIncrease is true); uses "Allowed Relative Increase" parameter.
bool useCounter
 True if we should use counter and output the results; uses "Use Counters" parameter.
Teuchos::RCP< NOX::GlobalDataglobalDataPtr
 Global data pointer. Keep this so the parameter list remains valid.
Teuchos::ParameterList * paramsPtr
 Pointer to the input parameter list.
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 slopeUtil
 Common slope calculations for line searches.
Teuchos::RCP
< NOX::MeritFunction::Generic
meritFuncPtr
 Pointer to a user supplied merit function.


Detailed Description

A polynomial line search, either quadratic or cubic.

This line search can be called via NOX::LineSearch::Manager.

The goal of the line search is to find a step $\lambda$ for the calculation $x_{\rm new} = x_{\rm old} + \lambda d$, given $x_{\rm old}$ and $ d $. To accomplish this goal, we minimize a merit function $ \phi(\lambda) $ that measures the "goodness" of the step $\lambda$. The standard merit function is

\[ \phi(\lambda) \equiv \frac{1}{2}||F (x_{\rm old} + \lambda s)||^2, \]

but a user defined merit function can be used instead (see computePhi() for details). Our first attempt is always to try a step $ \lambda_0 $, and then check the stopping criteria. The value of $ \lambda_0 $ is the specified by the "Default Step" parameter. If the first try doesn't work, then we successively minimize polynomial approximations, $ p_k(\lambda) \approx \phi(\lambda) $.

Stopping Criteria

The inner iterations continue until:

Polynomial Models of the Merit Function

We compute $ p_k(\lambda) $ by interpolating $f$. For the quadratic fit, we interpolate $ \phi(0) $, $ \phi'(0) $, and $ \phi(\lambda_{k-1}) $ where $ \lambda_{k-1} $ is the $ k-1 $ approximation to the step. For the cubit fit, we additionally include $\phi(\lambda{k-2})$.

The steps are calculated iteratively as follows, depending on the choice of "Interpolation Type".

For "Quadratic" and "Cubic", see computeSlope() for details on how $ \phi'(0) $ is calculated.

Bounds on the step length

We do not allow the step to grow or shrink too quickly by enforcing the following bounds:

\[ \gamma_{min} \; \lambda_{k-1} \leq \lambda_k \le \gamma_{max} \; \lambda_{k-1} \]

Here $ \gamma_{min} $ and $ \gamma_{max} $ are defined by parameters "Min Bounds Factor" and "Max Bounds Factor".

Input Parameters

"Line Search":

"Line Search"/"Polynomial":

Output Parameters

If the "Use Counters" parameter is set to true, then a sublist for output parameters called "Output" will be created in the parameter list used to instantiate or reset the class. Valid output parameters are:

References

This line search is based on materials in the following:

Author:
Russ Hooper, Roger Pawlowski, Tammy Kolda

Definition at line 321 of file NOX_LineSearch_Polynomial.H.


Member Enumeration Documentation

Types of sufficient decrease conditions used by checkConvergence().

Enumerator:
ArmijoGoldstein  Armijo-Goldstein conditions.
AredPred  Ared/Pred condition.
None  No condition.

Definition at line 469 of file NOX_LineSearch_Polynomial.H.

Interpolation types used by compute().

Enumerator:
Quadratic  Use quadratic interpolation throughout.
Cubic  Use quadratic interpolation in the first inner iteration and cubic interpolation otherwise.
Quadratic3  Use a 3-point quadratic line search. (The second step is 0.5 times the default step.).

Definition at line 479 of file NOX_LineSearch_Polynomial.H.

Type of recovery step to use.

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

Definition at line 492 of file NOX_LineSearch_Polynomial.H.


Constructor & Destructor Documentation

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

Constructor.

Definition at line 55 of file NOX_LineSearch_Polynomial.C.

NOX::LineSearch::Polynomial::~Polynomial (  ) 

Destructor.

Definition at line 65 of file NOX_LineSearch_Polynomial.C.


Member Function Documentation

bool NOX::LineSearch::Polynomial::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 144 of file NOX_LineSearch_Polynomial.C.

References AredPred, checkConvergence(), computeValue(), Constant, counter, defaultStep, NOX::Solver::Generic::getList(), NOX::Solver::Generic::getNumIterations(), NOX::Solver::Generic::getPreviousSolutionGroup(), NOX::LineSearch::Utils::Counters::incrementNumFailedLineSearches(), NOX::LineSearch::Utils::Counters::incrementNumIterations(), NOX::LineSearch::Utils::Counters::incrementNumLineSearches(), NOX::LineSearch::Utils::Counters::incrementNumNonTrivialLineSearches(), interpolationType, maxBoundFactor, maxIters, meritFuncPtr, minBoundFactor, minStep, paramsPtr, print, printBadSlopeWarning(), printOpeningRemarks(), NOX::LineSearch::Utils::Printing::printStep(), Quadratic, Quadratic3, recoveryStep, recoveryStepType, NOX::LineSearch::Utils::Counters::setValues(), suffDecrCond, updateGrp(), and useCounter.

bool NOX::LineSearch::Polynomial::checkConvergence ( double  newValue,
double  oldValue,
double  oldSlope,
double  step,
double  eta,
int  nIters,
int  nNonlinearIters 
) const [protected]

Returns true if converged.

We go through the following checks for convergence.

  1. If the "Force Interpolation" parameter is true and this is the first inner iteration (i.e., nIters is 1), then we return false.

  2. Next, it checks to see if the "Relative Increase" condition is satisfied. If so, then we return true. The "Relative Increase" condition is satisfied if both of the following two conditions hold.

    • The number of nonlinear iterations is less than or equal to the value specified in the "Maximum Iteration for Increase" parameter

    • The ratio of newValue to oldValue is less than the value specified in "Allowed Relative Increase".

  3. Last, we check the sufficient decrease condition. We return true if it's satisfied, and false otherwise. The condition depends on the value of "Sufficient Decrease Condition", as follows.

    • "Armijo-Goldstein": Return true if

      \[ \phi(\lambda) \leq \phi(0) + \alpha \; \lambda \; \phi'(0) \]

    • "Ared/Pred": Return true if

      \[ \| F(x_{\rm old} + \lambda d )\| \leq \| F(x_{\rm old}) \| (1 - \alpha (1 - \eta)) \]

    • "None": Always return true.

    For the first two cases, $\alpha$ is specified by the parameter "Alpha Factor".

Parameters:
newValue Depends on the "Sufficient Decrease Condition" parameter.
  • "Armijo-Goldstein" - $ \phi(\lambda) $
  • "Ared/Pred" - $ \| F(x_{\rm old} + \lambda d )\| $
  • "None" - N/A
oldValue Depends on the "Sufficient Decrease Condition" parameter.
  • "Armijo-Goldstein" - $ \phi(0) $
  • "Ared/Pred" - $ \| F(x_{\rm old} )\| $
  • "None" - N/A
oldSlope Only applicable to "Armijo-Goldstein", in which case it should be $\phi'(0)$.
step The current step, $\lambda$.
eta Only applicable to "Ared/Pred", in which case it should be the value of $\eta$ for last forcing term calculation in NOX::Direction::Newton
nIters Number of inner iterations.
nNonlinearIters Number of nonlinear iterations.
Note:
The norm used for "Ared/Pred" can be specified by the user by using the "User Defined Norm" parameter; this parameter is any object derived from NOX::Parameter::UserNorm.

Definition at line 354 of file NOX_LineSearch_Polynomial.C.

References alpha, AredPred, ArmijoGoldstein, doAllowIncrease, doForceInterpolation, NOX::Utils::err(), NOX::StatusTest::FiniteValue::finiteNumberTest(), maxIncreaseIter, maxRelativeIncrease, None, print, and suffDecrCond.

Referenced by compute().

bool NOX::LineSearch::Polynomial::updateGrp ( NOX::Abstract::Group newGrp,
const NOX::Abstract::Group oldGrp,
const NOX::Abstract::Vector dir,
double  step 
) const [protected]

Updates the newGrp by computing a new x and a new F(x).

Let

  • $x_{\rm new}$ denote the new solution to be calculated (corresponding to newGrp)
  • $x_{\rm old}$ denote the previous solution (i.e., the result of oldGrp.getX())
  • $d$ denotes the search direction (dir).
  • $\lambda$ denote the step (step),

We compute

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

and $ F(x_{\rm new})$. The results are stored in newGrp.

Definition at line 400 of file NOX_LineSearch_Polynomial.C.

References NOX::Abstract::Group::computeF(), NOX::Abstract::Group::computeX(), and NOX::Abstract::Group::Ok.

Referenced by compute().

double NOX::LineSearch::Polynomial::computeValue ( const NOX::Abstract::Group grp,
double  phi 
) [protected]

Compute the value used to determine sufficient decrease.

If the "Sufficient Decrease Condition" is set to "Ared/Pred", then we do the following. If a "User Defined Norm" parameter is specified, then the NOX::Parameter::UserNorm::norm function on the user-supplied merit function is used. If the user does not provide a norm, we return $ \|F(x)\| $.

If the "Sufficient Decrease Condition" is not set to "Ared/Pred", then we simply return phi.

Parameters:
phi - Should be equal to computePhi(grp).

Definition at line 415 of file NOX_LineSearch_Polynomial.C.

References AredPred, NOX::Abstract::Group::getNormF(), and suffDecrCond.

Referenced by compute().

void NOX::LineSearch::Polynomial::printOpeningRemarks (  )  const [protected]

Used to print opening remarks for each call to compute().

Definition at line 427 of file NOX_LineSearch_Polynomial.C.

References NOX::Utils::Details, NOX::Utils::fill(), NOX::Utils::InnerIteration, NOX::Utils::isPrintType(), meritFuncPtr, NOX::Utils::out(), and print.

Referenced by compute().

void NOX::LineSearch::Polynomial::printBadSlopeWarning ( double  slope  )  const [protected]

Prints a warning message saying that the slope is negative.

Definition at line 443 of file NOX_LineSearch_Polynomial.C.

References NOX::Utils::out(), print, and NOX::Utils::Warning.

Referenced by compute().


Member Data Documentation

Choice for sufficient decrease condition; uses "Sufficient Decrease Condition" parameter.

Definition at line 500 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence(), compute(), and computeValue().

Choice of interpolation type; uses "Interpolation Type" parameter.

Definition at line 503 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Choice of the recovery step type; uses "Recovery Step Type" parameter.

Definition at line 506 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Minimum step length (i.e., when we give up); uses "Mimimum Step" parameter.

Definition at line 509 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Default step; uses "Default Step" parameter.

Definition at line 512 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Default step for linesearch failure; uses "Recovery Step" parameter.

Definition at line 515 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Maximum iterations; uses "Max Iters" parameter.

Definition at line 518 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

The $ \alpha $ for the Armijo-Goldstein condition, or the $ \alpha $ for the Ared/Pred condition; see checkConvergence(). Uses "Alpha Factor" parameter.

Definition at line 523 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence().

Factor that limits the minimum size of the new step based on the previous step; uses "Min Bounds Factor" parameter.

Definition at line 527 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Factor that limits the maximum size of the new step based on the previous step; uses "Max Bounds Factor" parameter.

Definition at line 531 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

True is we should force at least one interpolation step; uses "Force Interpolation" parameter.

Definition at line 535 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence().

No increases are allowed if the number of nonlinear iterations is greater than this value; uses "Maximum Iterations for Increase".

Definition at line 540 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence().

True if we sometimes allow an increase(!) in the decrease measure, i.e., maxIncreaseIter > 0.

Definition at line 544 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence().

Maximum allowable relative increase for decrease meausre (if allowIncrease is true); uses "Allowed Relative Increase" parameter.

Definition at line 548 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence().

True if we should use counter and output the results; uses "Use Counters" parameter.

Definition at line 552 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Global data pointer. Keep this so the parameter list remains valid.

Definition at line 555 of file NOX_LineSearch_Polynomial.H.

Teuchos::ParameterList* NOX::LineSearch::Polynomial::paramsPtr [protected]

Pointer to the input parameter list.

We need this to later create an "Output" sublist to store output parameters from counter.

Definition at line 561 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Common line search printing utilities.

Definition at line 564 of file NOX_LineSearch_Polynomial.H.

Referenced by checkConvergence(), compute(), printBadSlopeWarning(), and printOpeningRemarks().

Common common counters for line searches.

Definition at line 567 of file NOX_LineSearch_Polynomial.H.

Referenced by compute().

Common slope calculations for line searches.

Definition at line 570 of file NOX_LineSearch_Polynomial.H.

Pointer to a user supplied merit function.

Definition at line 573 of file NOX_LineSearch_Polynomial.H.

Referenced by compute(), and printOpeningRemarks().


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

Generated on Thu Dec 17 11:03:08 2009 for Nonlinear Solver Project by  doxygen 1.5.9