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...
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	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 $\phi'(0)$ .
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" 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::List *	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.
NOX::Parameter::UserNorm *	userNormPtr
	Pointer to a user supplied norm.
NOX::Parameter::MeritFunction *	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:

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 $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 $ st 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".

"Quadratic" - We construct a quadratic model of $\phi$ , and solve for $\lambda$ to get

$\lambda_{k} = \frac{-\phi'(0) \lambda_{k-1}^2 }{2 \left[ \phi(\lambda_{k-1}) - \phi(0) -\phi'(0) \lambda_{k-1} \right]}$
"Cubic" - We construct a cubic model of $\phi$ , and solve for $\lambda$ . We use the quadratic model to solve for $\lambda_1$ ; otherwise,

$\lambda_k = \frac{-b+\sqrt{b^2-3a \phi'(0)}}{3a}$

where

$\left[ \begin{array}{c} a \\ \\ b \end{array} \right] = \frac{1}{\lambda_{k-1} - \lambda_{k-2}} \left[ \begin{array}{cc} \lambda_{k-1}^{-2} & -\lambda_{k-2}^{-2} \\ & \\ -\lambda_{k-2}\lambda_{k-1}^{-2} & \lambda_{k-1}\lambda_{k-2}^{-2} \end{array} \right] \left[ \begin{array}{c} \phi(\lambda_{k-1}) - \phi(0) - \phi'(0)\lambda_{k-1} \\ \\ \phi(\lambda_{k-2}) - \phi(0) - \phi'(0)\lambda_{k-2} \end{array} \right]$
"Quadratic3" - We construct a quadratic model of $\phi$ using $\phi(0)$ , $\phi(\lambda_{k-1})$ , and $\phi(\lambda_{k-2})$ . No derivative information for $\phi$ is used. We let $\lambda_1 = \frac{1}{2} \lambda_0$ , and otherwise

$\lambda_k = - \frac{1}{2} \frac{\lambda_{k-1}^2 [\phi(\lambda_{k-2}) -\phi(0)] - \lambda_{k-2}^2 [\phi(\lambda_{k-1}) -\phi(0)]} {\lambda_{k-2} [\phi(\lambda_{k-1}) -\phi(0)] - \lambda_{k-1} [\phi(\lambda_{k-2}) -\phi(0)]}$

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

"Method" = "Polynomial" [required]

"Line Search"/"Polynomial":

"Default Step" - Starting step length, i.e., $\lambda_0$ . 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 $\lambda_k$ 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]
- "Quadratic"
- "Quadratic3"
"Min Bounds Factor" - Choice for $\gamma_{min}$ , 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 $\gamma_{max}$ , 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.

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

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

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
$\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".

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.

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

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

In the end, we should have computed $\lambda$ and updated grp so that
$x_{\rm new} = x_{\rm old} + \lambda d.$

Ideally, $\|F(x_{\rm new})\| < \|F(x_{\rm old})\|$ .
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

$\frac{1}{2} \| F(x) \|^2$

double NOX::LineSearch::Polynomial::computeSlope ( const NOX::Abstract::Vector & dir,

const NOX::Abstract::Group & grp

) [protected]

Compute $\phi'(0)$ .
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
$d^T (J(x_{\rm old})^T F(x_{\rm old}))$
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 $\|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).

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.

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:43:33 2008 for NOX by

1.3.9.1

NOX::LineSearch::Polynomial Class Reference

Public Member Functions

Protected Types

Protected Member Functions

Protected Attributes

Detailed Description

Member Enumeration Documentation

Member Function Documentation

Member Data Documentation