# 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:

[legend]
Collaboration diagram for NOX::LineSearch::Polynomial:
[legend]
List of all members.

## Public Member Functions

Polynomial (const NOX::Utils &u, NOX::Parameter::List &params)
Constructor.
~Polynomial ()
Destructor.
bool reset (NOX::Parameter::List &params)
Reset parameters.
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...
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 computePhi (const NOX::Abstract::Group &grp)
Computes the value of the merit function.
double computeValue (const NOX::Abstract::Group &grp, double phi)
Compute the value used to determine sufficient decrease.
double computeSlope (const NOX::Abstract::Vector &dir, const NOX::Abstract::Group &grp)
Compute .
void printOpeningRemarks () const
Used to print opening remarks for each call to compute().
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 for the Armijo-Goldstein condition, or the for the Ared/Pred condition; see checkConvergence(). Uses "Alpha" 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 #counterUtil and output the results; uses "Use Counters" parameter.
NOX::Parameter::ListparamsPtr
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.
NOX::Parameter::UserNormuserNormPtr
Pointer to a user supplied norm.
NOX::Parameter::MeritFunctionmeritFuncPtr
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 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:

• The sufficient decrease condition is met; see checkConvergence() for details.

• The maximum iterations are reached; see parameter "Max Iters". This is considered a failure and the recovery step is used; see parameter "Recovery Step".

• The minimum step length is reached; see parameter "Minimum Step". This is considered a line search failure and the recovery step is used; see parameter "Recovery Step".

Polynomial Models of the Merit Function

We compute by interpolating . For the quadratic fit, we interpolate , , and where is the st 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".

• "Quadratic" - We construct a quadratic model of , and solve for to get

• "Cubic" - We construct a cubic model of , and solve for . We use the quadratic model to solve for ; otherwise,

where

• "Quadratic3" - We construct a quadratic model of using , , and . No derivative information for is used. We let , and otherwise

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":

• "Method" = "Polynomial" [required]

"Line Search"/"Polynomial":

• "Default Step" - Starting step length, i.e., . Defaults to 1.0.

• "Max Iters" - Maximum number of line search iterations. The search fails if the number of iterations exceeds this value. Defaults to 100.

• "Minimum Step" - Minimum acceptable step length. The search fails if the computed is less than this value. Defaults to 1.0e-12.

• "Recovery Step Type" - Determines the step size to take when the line search fails. Choices are:

• "Constant" [default] - Uses a constant value set in "Recovery Step".
• "Last Computed Step" - Uses the last value computed by the line search algorithm.

• "Recovery Step" - The value of the step to take when the line search fails. Only used if the "Recovery Step Type" is set to "Constant". Defaults to value for "Default Step".

• "Interpolation Type" - Type of interpolation that should be used. Choices are

• "Cubic" [default]

• "Min Bounds Factor" - Choice for , i.e., the factor that limits the minimum size of the new step based on the previous step. Defaults to 0.1.

• "Max Bounds Factor" - Choice for , i.e., the factor that limits the maximum size of the new step based on the previous step. Defaults to 0.5.

• "Sufficient Decrease Condition" - See checkConvergence() for details. Choices are:

• "Armijo-Goldstein" [default]
• "Ared/Pred"
• "None"

• "Alpha Factor" - Parameter choice for sufficient decrease condition. See checkConvergence() for details. Defaults to 1.0e-4.

• "Force Interpolation" (boolean) - Set to true if at least one interpolation step should be used. The default is false which means that the line search will stop if the default step length satisfies the convergence criteria. Defaults to false.

• "Use Counters" (boolean) - Set to true if we should use counters and then output the result to the paramter list as described in Output Parameters. Defaults to true.

• "Maximum Iteration for Increase" - Maximum index of the nonlinear iteration for which we allow a relative increase. See checkConvergence() for further details. Defaults to 0 (zero).

• "Allowed Relative Increase" - See checkConvergence() for details. Defaults to 100.

• "User Defined Merit Function" - The user can redefine the merit function used; see computePhi() and NOX::Parameter::MeritFunction for details.

• "User Defined Norm" - The user can redefine the norm that is used in the Ared/Pred sufficient decrease condition; see computeValue() and NOX::Parameter::UserNorm for details.

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:

• "Total Number of Line Search Calls" - Total number of calls to the compute() method of this line search.

• "Total Number of Non-trivial Line Searches" - Total number of steps that could not directly take a full step and meet the required "Sufficient Decrease Condition" (i.e., the line search had to do at least one interpolation).

• "Total Number of Failed Line Searches" - Total number of line searches that failed and used a recovery step.

• "Total Number of Line Search Inner Iterations" - Total number of inner iterations of all calls to compute().

References

This line search is based on materials in the following:

• Section 8.3.1 in C.T. Kelley, "Iterative Methods for Linear and Nonlinear Equations", SIAM, 1995.

• Section 6.3.2 and Algorithm 6.3.1 of J. E. Dennis Jr. and Robert B. Schnabel, "Numerical Methods for Unconstrained Optimization and Nonlinear Equations," Prentice Hall, 1983.

• Section 3.4 of Jorge Nocedal and Stephen J. Wright, "Numerical Optimization,"Springer, 1999.

• "An Inexact Newton Method for Fully Coupled Solution of the Navier-Stokes Equations with Heat and Mass Transfer", Shadid, J. N., Tuminaro, R. S., and Walker, H. F., Journal of Computational Physics, 137, 155-185 (1997)

Author:
Russ Hooper, Roger Pawlowski, Tammy Kolda

## Member Enumeration Documentation

 enum NOX::LineSearch::Polynomial::InterpolationType [protected]

Interpolation types used by compute().

Enumeration values:
 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.).

 enum NOX::LineSearch::Polynomial::RecoveryStepType [protected]

Type of recovery step to use.

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

 enum NOX::LineSearch::Polynomial::SufficientDecreaseType [protected]

Types of sufficient decrease conditions used by checkConvergence().

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

## Member Function Documentation

 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 the "Sufficient Decrease Condition Parameter", as follows.

• "Armijo-Goldstein": Return true if

• "Ared/Pred": Return true if

• "None": Always return true.

For the first two cases, is specified by the parameter "Alpha".

Parameters:
 newValue Depends on the "Sufficient Decrease Condition" parameter. "Armijo-Goldstein" - "Ared/Pred" - "None" - N/A oldValue Depends on the "Sufficient Decrease Condition" parameter. "Armijo-Goldstein" - "Ared/Pred" - "None" - N/A 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 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.

 bool NOX::LineSearch::Polynomial::compute ( NOX::Abstract::Group & newgrp, double & step, const NOX::Abstract::Vector & dir, const NOX::Solver::Generic & s )  [virtual]
 Perform a line search. Let denotes the new solution to be calculated (corresponding to grp) denotes the step to be calculated (step), denotes the search direction (dir). denotes the previous solution (i.e., the result of s.getPreviousSolutionGroup().getX()) In the end, we should have computed and updated grp so that Ideally, . Implements NOX::LineSearch::Generic.

 double NOX::LineSearch::Polynomial::computePhi ( const NOX::Abstract::Group & grp )  [protected]
 Computes the value of the merit function. If a "User Defined Merit Function" parameter is specified, then the NOX::Parameter::MeritFunction::computeF function on the user-supplied merit function is used. Otherwise, we compute and return

 double NOX::LineSearch::Polynomial::computeSlope ( const NOX::Abstract::Vector & dir, const NOX::Abstract::Group & grp )  [protected]

Compute .

If a "User Defined Merit Function" is provided, then we use NOX::Parameter::MeritFunction::computeSlope to compute this value.

Otherwise, we are using the standard merit function, so we want to compute

To do this, we use NOX::LineSearch::Utils::Slope.

Parameters:
 grp Should correspond to s.getPreviousSolutionGroup() from 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.

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

 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 denote the new solution to be calculated (corresponding to newGrp) denote the previous solution (i.e., the result of oldGrp.getX()) denotes the search direction (dir). denote the step (step), We compute and . The results are stored in newGrp.

## Member Data Documentation

 NOX::Parameter::MeritFunction* NOX::LineSearch::Polynomial::meritFuncPtr [protected]
 Pointer to a user supplied merit function. This should not be deleted in the destructor

 NOX::Parameter::List* 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 #counterUtil. This should not be deleted in the destructor

 NOX::Parameter::UserNorm* NOX::LineSearch::Polynomial::userNormPtr [protected]
 Pointer to a user supplied norm. This should not be deleted in the destructor

The documentation for this class was generated from the following files:
• NOX_LineSearch_Polynomial.H
• NOX_LineSearch_Polynomial.C

Generated on Thu Sep 18 12:42:29 2008 for NOX by  1.3.9.1