#include <NOX_LineSearch_Polynomial.H>
Public Member Functions | |
Polynomial (const Teuchos::RCP< NOX::GlobalData > &gd, Teuchos::ParameterList ¶ms) | |
Constructor. | |
~Polynomial () | |
Destructor. | |
bool | reset (const Teuchos::RCP< NOX::GlobalData > &gd, Teuchos::ParameterList ¶ms) |
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 ![]() ![]() | |
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::GlobalData > | globalDataPtr |
Global data pointer. Keep this so the parameter list remains valid. | |
Teuchos::ParameterList * | paramsPtr |
Pointer to the input parameter list. | |
NOX::LineSearch::Utils::Printing | |
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. |
This line search can be called via NOX::LineSearch::Manager.
The goal of the line search is to find a step for the calculation
, given
and
. To accomplish this goal, we minimize a merit function
that measures the "goodness" of the step
. The standard merit function is
but a user defined merit function can be used instead (see computePhi() for details). Our first attempt is always to try a step , and then check the stopping criteria. The value of
is the specified by the "Default Step" parameter. If the first try doesn't work, then we successively minimize polynomial approximations,
.
Stopping Criteria
The inner iterations continue until:
Polynomial Models of the Merit Function
We compute by interpolating
. For the quadratic fit, we interpolate
,
, and
where
is the
approximation to the step. For the cubit fit, we additionally include
.
The steps are calculated iteratively as follows, depending on the choice of "Interpolation Type".
where
For "Quadratic" and "Cubic", see computeSlope() for details on how is calculated.
Bounds on the step length
We do not allow the step to grow or shrink too quickly by enforcing the following bounds:
Here and
are defined by parameters "Min Bounds Factor" and "Max Bounds Factor".
Input Parameters
"Line Search":
"Line Search"/"Polynomial":
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:
Definition at line 321 of file NOX_LineSearch_Polynomial.H.
enum NOX::LineSearch::Polynomial::SufficientDecreaseType [protected] |
Types of sufficient decrease conditions used by checkConvergence().
ArmijoGoldstein | Armijo-Goldstein conditions. |
AredPred | Ared/Pred condition. |
None | No condition. |
Definition at line 469 of file NOX_LineSearch_Polynomial.H.
enum NOX::LineSearch::Polynomial::InterpolationType [protected] |
Interpolation types used by compute().
Definition at line 479 of file NOX_LineSearch_Polynomial.H.
enum NOX::LineSearch::Polynomial::RecoveryStepType [protected] |
Type of recovery step to use.
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.
NOX::LineSearch::Polynomial::Polynomial | ( | const Teuchos::RCP< NOX::GlobalData > & | gd, | |
Teuchos::ParameterList & | params | |||
) |
NOX::LineSearch::Polynomial::~Polynomial | ( | ) |
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:
grp | The initial solution vector, ![]() | |
dir | A vector of directions to be used in the line search, ![]() | |
s | The nonlinear solver. |
step | The distance the direction was scaled, ![]() | |
grp | The grp is updated with a new solution, ![]() |
Ideally, (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.
For the first two cases, is specified by the parameter "Alpha Factor".
newValue | Depends on the "Sufficient Decrease Condition" parameter.
| |
oldValue | Depends on the "Sufficient Decrease Condition" parameter.
| |
oldSlope | Only applicable to "Armijo-Goldstein", in which case it should be ![]() | |
step | The current step, ![]() | |
eta | Only applicable to "Ared/Pred", in which case it should be the value of ![]() | |
nIters | Number of inner iterations. | |
nNonlinearIters | Number of nonlinear iterations. |
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
newGrp
)dir
).step
),We compute
and . 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 .
If the "Sufficient Decrease Condition" is not set to "Ared/Pred", then we simply return phi.
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().
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().
double NOX::LineSearch::Polynomial::minStep [protected] |
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().
double NOX::LineSearch::Polynomial::defaultStep [protected] |
Default step; uses "Default Step" parameter.
Definition at line 512 of file NOX_LineSearch_Polynomial.H.
Referenced by compute().
double NOX::LineSearch::Polynomial::recoveryStep [protected] |
Default step for linesearch failure; uses "Recovery Step" parameter.
Definition at line 515 of file NOX_LineSearch_Polynomial.H.
Referenced by compute().
int NOX::LineSearch::Polynomial::maxIters [protected] |
Maximum iterations; uses "Max Iters" parameter.
Definition at line 518 of file NOX_LineSearch_Polynomial.H.
Referenced by compute().
double NOX::LineSearch::Polynomial::alpha [protected] |
The for the Armijo-Goldstein condition, or the
for the Ared/Pred condition; see checkConvergence(). Uses "Alpha Factor" parameter.
Definition at line 523 of file NOX_LineSearch_Polynomial.H.
Referenced by checkConvergence().
double NOX::LineSearch::Polynomial::minBoundFactor [protected] |
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().
double NOX::LineSearch::Polynomial::maxBoundFactor [protected] |
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().
bool NOX::LineSearch::Polynomial::doForceInterpolation [protected] |
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().
int NOX::LineSearch::Polynomial::maxIncreaseIter [protected] |
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().
bool NOX::LineSearch::Polynomial::doAllowIncrease [protected] |
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().
double NOX::LineSearch::Polynomial::maxRelativeIncrease [protected] |
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().
bool NOX::LineSearch::Polynomial::useCounter [protected] |
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().
Teuchos::RCP<NOX::GlobalData> NOX::LineSearch::Polynomial::globalDataPtr [protected] |
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.
Teuchos::RCP<NOX::MeritFunction::Generic> NOX::LineSearch::Polynomial::meritFuncPtr [protected] |
Pointer to a user supplied merit function.
Definition at line 573 of file NOX_LineSearch_Polynomial.H.
Referenced by compute(), and printOpeningRemarks().