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

#include <NOX_LineSearch_Polynomial.H>

Inheritance diagram for NOX::LineSearch::Polynomial:

Collaboration diagram for NOX::LineSearch::Polynomial:

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

Public Member Functions inherited from NOX::LineSearch::Generic
	Generic ()
	Default constructor.

virtual	~Generic ()
	Destructor.

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

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

double	computeValue (const NOX::Abstract::Group &grp, double phi)
	Compute the value used to determine sufficient decrease. More...

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::GlobalData >	globalDataPtr
	Global data pointer. Keep this so the parameter list remains valid.

Teuchos::ParameterList *	paramsPtr
	Pointer to the input parameter list. More...

NOX::LineSearch::Utils::Printing	print
	Common line search printing utilities.

NOX::LineSearchCounters *	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:

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 $ 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().

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

enum NOX::LineSearch::Polynomial::RecoveryStepType

protected

Type of recovery step to use.

Enumerator
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()

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

References NOX::StatusTest::FiniteValue::finiteNumberTest().

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

References Teuchos::ParameterList::get(), NOX::Solver::Generic::getList(), NOX::Solver::Generic::getNumIterations(), and NOX::Solver::Generic::getPreviousSolutionGroup().

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

References NOX::Abstract::Group::getNormF().

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())
denotes the search direction (dir).
$\lambda$ denote the step (step),