NOX::LineSearch::MoreThuente Class Reference

More'-Thuente Line Search. Original code by Dianne O'Leary, modfified by Tammy Kolda and Roger Pawlowski for the NOX project. This version has been slightly optimized and also supports Homer Walker's work on adaptive forcing terms and Ared/Pred conditions. It also allows for arbitrary merit functions and norms to be supplied by the user. More...

#include <NOX_LineSearch_MoreThuente.H>

Inheritance diagram for NOX::LineSearch::MoreThuente:

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

Collaboration graph
[legend]

List of all members.

Public Member Functions

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

Private Types

enum  RecoveryStepType { Constant, LastComputedStep }
 Type of recovery step to use. More...
enum  SufficientDecreaseCondition { ArmijoGoldstein, AredPred }
 Options for sufficient decrease criteria. More...

Private Member Functions

int cvsrch (NOX::Abstract::Group &newgrp, double &step, const NOX::Abstract::Group &oldgrp, const NOX::Abstract::Vector &dir, const Solver::Generic &s)
 More'-Thuente's cvsrch subroutine.
int cstep (double &stx, double &fx, double &dx, double &sty, double &fy, double &dy, double &stp, double &fp, double &dp, bool &brackt, double stmin, double stmax)
 More'-Thuente's cstep subroutine.
double max (double a, double b)
 max
double min (double a, double b)
 min
double absmax (double a, double b, double c)
 absmax - returns the max of the absolute value of the three inputs

Private Attributes

Teuchos::RCP< NOX::GlobalDataglobalDataPtr
 Global data pointer. Keep this so the parameter list remains valid.
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 slope
 Common slope calculations for line searches.
Teuchos::ParameterList * paramsPtr
 Pointer to the input parameter list. This is saved so data stored in the counter object can be written to the "Output" parameter list.
double ftol
 Sufficient decrease parameter.
double gtol
 Curvature condition parameter.
double xtol
 Threshold on width of the uncertainty.
double stpmin
 Minimum step.
double stpmax
 Maximum step.
int maxfev
 Maximum number of function evaluations.
RecoveryStepType recoveryStepType
 Choice of the recovery step type; uses "Recovery Step Type" parameter.
double defaultstep
 Default step length.
double recoverystep
 Recovery step if linesearch fails.
SufficientDecreaseCondition suffDecrCond
 Chioce for the sufficient decrease criteria.
bool useOptimizedSlopeCalc
 If set to true the value of $ s^TJ^Tf $ is estimated using a directional derivative. This eliminates having to compute the Jacobian at each inner iteration of the line search.
Teuchos::RCP
< NOX::MeritFunction::Generic
meritFuncPtr
 Stores the merit function.


Detailed Description

More'-Thuente Line Search. Original code by Dianne O'Leary, modfified by Tammy Kolda and Roger Pawlowski for the NOX project. This version has been slightly optimized and also supports Homer Walker's work on adaptive forcing terms and Ared/Pred conditions. It also allows for arbitrary merit functions and norms to be supplied by the user.

This code is based on the More'-Thuente line search from the 1983 MINPACK Project. More specifically, this code is based on Dianne O'Leary's 1991 Matlab-implementation of the More'-Thuente line search. The original comments are preserved in the descriptions of the individual subroutines. What follows is an updated summary.

The merit function we are minimizing is given by

\[ f(x) = 0.5 \|F(x)\|^2 \]

(alternatively the user can define this)

The purpose of the More'-Thuente line search is to find a step which satisfies a sufficient decrease condition and a curvature condition. At each stage the subroutine updates an interval of uncertainty with endpoints stx and sty. The interval of uncertainty is initially chosen so that it contains a minimizer of the modified function

\[ f(x+{\rm stp} \; s) - f(x) - {\rm ftol} \; {\rm stp} \; (\nabla f(x)^T s). \]

If a step is obtained for which the modified function has a nonpositive function value and nonnegative derivative, then the interval of uncertainty is chosen so that it contains a minimizer of $f(x+{\rm stp}\;s)$.

The algorithm is designed to find a step which satisfies one of two sufficient decrease conditions:

(1) Armijo-Goldstein Condition

\[ f(x + {\rm stp} \; s) \le f(x) + {\rm ftol} \; {\rm stp} \; (\nabla f(x)^T s), \]

or

(2) Ared/Pred Condtition

\[ F(x_{n-1}+ \lambda s) \le F(x_{n-1})(1-\alpha(1-\eta)) \]

and the curvature condition

\[ \vert \nabla f(x + {\rm stp} \; s)^T s) \vert \le {\rm gtol} \; |\nabla f(x)^T s| \]

If ftol is less than gtol and if, for example, the function is bounded below, then there is always a step which satisfies both conditions. If no step can be found which satisfies both conditions, then the algorithm usually stops when rounding errors prevent further progress. In this case stp only satisfies the sufficient decrease condition.

Modifications from NOX::LineSearch::MoreThuente
1. Added the option to use Ared/Pred conditions as describe in Homer Walker's papers. 2. Added support to use an adjustable forcing term as describe in Homer Walker's papers. 3. Added the option to use directional derivatives in computing the slope instead of explicitly computing the Jacobian. This eliminates the need to recompute the Jacobian at each inner iteration of the More'-Thuente algorithm. 4. Added the ability to use the NOX::Parameter::UserNorm and NOX::Parameter::MeritFunction objects to supply user defined norms and merit functions to the line search.

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

This line search is used if "More'-Thuente2" is the "Method" in the "Line Search" sublist. (See NOX::LineSearch::Manager for details.)

The following parameters can be specified for this line search in the "More'-Thuente2" sublist of the "Line Search" sublist:

Output Parameters
A sublist for output parameters will be created called "Output" in the parameter list used to instantiate or reset the class. Valid output parameters are:

Definition at line 199 of file NOX_LineSearch_MoreThuente.H.


Member Enumeration Documentation

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 486 of file NOX_LineSearch_MoreThuente.H.

Options for sufficient decrease criteria.

Definition at line 502 of file NOX_LineSearch_MoreThuente.H.


Constructor & Destructor Documentation

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

Constructor.

Definition at line 53 of file NOX_LineSearch_MoreThuente.C.

NOX::LineSearch::MoreThuente::~MoreThuente (  ) 

Destructor.

Definition at line 63 of file NOX_LineSearch_MoreThuente.C.


Member Function Documentation

bool NOX::LineSearch::MoreThuente::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 131 of file NOX_LineSearch_MoreThuente.C.

References counter, cvsrch(), NOX::Solver::Generic::getPreviousSolutionGroup(), NOX::LineSearch::Utils::Counters::incrementNumLineSearches(), NOX::LineSearch::Utils::Counters::incrementNumNonTrivialLineSearches(), paramsPtr, and NOX::LineSearch::Utils::Counters::setValues().

int NOX::LineSearch::MoreThuente::cvsrch ( NOX::Abstract::Group newgrp,
double &  step,
const NOX::Abstract::Group oldgrp,
const NOX::Abstract::Vector dir,
const Solver::Generic s 
) [private]

More'-Thuente's cvsrch subroutine.

This translation into C++ is based on a translation into Matlab by Dianne O'Leary. The return code corresponds to the "info" code described below. The original documentation follows.

%   Translation of minpack subroutine cvsrch
%   Dianne O'Leary   July 1991
%     **********
%
%     Subroutine cvsrch
%
%     The purpose of cvsrch is to find a step which satisfies 
%     a sufficient decrease condition and a curvature condition.
%     The user must provide a subroutine which calculates the
%     function and the gradient.
%
%     At each stage the subroutine updates an interval of
%     uncertainty with endpoints stx and sty. The interval of
%     uncertainty is initially chosen so that it contains a 
%     minimizer of the modified function
%
%          f(x+stp*s) - f(x) - ftol*stp*(gradf(x)'s).
%
%     If a step is obtained for which the modified function 
%     has a nonpositive function value and nonnegative derivative, 
%     then the interval of uncertainty is chosen so that it 
%     contains a minimizer of f(x+stp*s).
%
%     The algorithm is designed to find a step which satisfies 
%     the sufficient decrease condition 
%
%           f(x+stp*s) <= f(x) + ftol*stp*(gradf(x)'s),
%
%     and the curvature condition
%
%           abs(gradf(x+stp*s)'s)) <= gtol*abs(gradf(x)'s).
%
%     If ftol is less than gtol and if, for example, the function
%     is bounded below, then there is always a step which satisfies
%     both conditions. If no step can be found which satisfies both
%     conditions, then the algorithm usually stops when rounding
%     errors prevent further progress. In this case stp only 
%     satisfies the sufficient decrease condition.
%
%     The subroutine statement is
%
%        subroutine cvsrch(fcn,n,x,f,g,s,stp,ftol,gtol,xtol,
%                          stpmin,stpmax,maxfev,info,nfev,wa)
%     where
%
%	fcn is the name of the user-supplied subroutine which
%         calculates the function and the gradient.  fcn must 
%      	  be declared in an external statement in the user 
%         calling program, and should be written as follows.
%
%	  subroutine fcn(n,x,f,g)
%         integer n
%         f
%         x(n),g(n)
%	  ----------
%         Calculate the function at x and
%         return this value in the variable f.
%         Calculate the gradient at x and
%         return this vector in g.
%	  ----------
%	  return
%	  end
%
%       n is a positive integer input variable set to the number
%	  of variables.
%
%	x is an array of length n. On input it must contain the
%	  base point for the line search. On output it contains 
%         x + stp*s.
%
%	f is a variable. On input it must contain the value of f
%         at x. On output it contains the value of f at x + stp*s.
%
%	g is an array of length n. On input it must contain the
%         gradient of f at x. On output it contains the gradient
%         of f at x + stp*s.
%
%	s is an input array of length n which specifies the
%         search direction.
%
%	stp is a nonnegative variable. On input stp contains an
%         initial estimate of a satisfactory step. On output
%         stp contains the final estimate.
%
%       ftol and gtol are nonnegative input variables. Termination
%         occurs when the sufficient decrease condition and the
%         directional derivative condition are satisfied.
%
%	xtol is a nonnegative input variable. Termination occurs
%         when the relative width of the interval of uncertainty 
%	  is at most xtol.
%
%	stpmin and stpmax are nonnegative input variables which 
%	  specify lower and upper bounds for the step.
%
%	maxfev is a positive integer input variable. Termination
%         occurs when the number of calls to fcn is at least
%         maxfev by the end of an iteration.
%
%	info is an integer output variable set as follows:
%	  
%	  info = 0  Improper input parameters.
%
%	  info = 1  The sufficient decrease condition and the
%                   directional derivative condition hold.
%
%	  info = 2  Relative width of the interval of uncertainty
%		    is at most xtol.
%
%	  info = 3  Number of calls to fcn has reached maxfev.
%
%	  info = 4  The step is at the lower bound stpmin.
%
%	  info = 5  The step is at the upper bound stpmax.
%
%	  info = 6  Rounding errors prevent further progress.
%                   There may not be a step which satisfies the
%                   sufficient decrease and curvature conditions.
%                   Tolerances may be too small.
%
%       nfev is an integer output variable set to the number of
%         calls to fcn.
%
%	wa is a work array of length n.
%
%     Subprograms called
%
%	user-supplied......fcn
%
%	MINPACK-supplied...cstep
%
%	FORTRAN-supplied...abs,max,min
%	  
%     Argonne National Laboratory. MINPACK Project. June 1983
%     Jorge J. More', David J. Thuente
%

Definition at line 148 of file NOX_LineSearch_MoreThuente.C.

References NOX::Abstract::Group::computeF(), NOX::Abstract::Group::computeGradient(), NOX::Abstract::Group::computeJacobian(), NOX::LineSearch::Utils::Slope::computeSlope(), NOX::LineSearch::Utils::Slope::computeSlopeWithOutJac(), NOX::Abstract::Group::computeX(), Constant, counter, cstep(), defaultstep, NOX::Utils::err(), NOX::Utils::fill(), ftol, NOX::Solver::Generic::getList(), NOX::Abstract::Group::getNormF(), gtol, NOX::LineSearch::Utils::Counters::incrementNumFailedLineSearches(), NOX::LineSearch::Utils::Counters::incrementNumIterations(), NOX::Utils::InnerIteration, NOX::Utils::isPrintType(), max(), maxfev, meritFuncPtr, min(), NOX::Abstract::Group::Ok, NOX::Utils::out(), print, NOX::LineSearch::Utils::Printing::printStep(), recoverystep, recoveryStepType, slope, stpmax, stpmin, suffDecrCond, useOptimizedSlopeCalc, NOX::Utils::Warning, and xtol.

Referenced by compute().

int NOX::LineSearch::MoreThuente::cstep ( double &  stx,
double &  fx,
double &  dx,
double &  sty,
double &  fy,
double &  dy,
double &  stp,
double &  fp,
double &  dp,
bool &  brackt,
double  stmin,
double  stmax 
) [private]

More'-Thuente's cstep subroutine.

%   Translation of minpack subroutine cstep 
%   Dianne O'Leary   July 1991
%     **********
%
%     Subroutine cstep
%
%     The purpose of cstep is to compute a safeguarded step for
%     a linesearch and to update an interval of uncertainty for
%     a minimizer of the function.
%
%     The parameter stx contains the step with the least function
%     value. The parameter stp contains the current step. It is
%     assumed that the derivative at stx is negative in the
%     direction of the step. If brackt is set true then a
%     minimizer has been bracketed in an interval of uncertainty
%     with endpoints stx and sty.
%
%     The subroutine statement is
%
%       subroutine cstep(stx,fx,dx,sty,fy,dy,stp,fp,dp,brackt,
%                        stpmin,stpmax,info)
% 
%     where
%
%       stx, fx, and dx are variables which specify the step,
%         the function, and the derivative at the best step obtained
%         so far. The derivative must be negative in the direction
%         of the step, that is, dx and stp-stx must have opposite 
%         signs. On output these parameters are updated appropriately.
%
%       sty, fy, and dy are variables which specify the step,
%         the function, and the derivative at the other endpoint of
%         the interval of uncertainty. On output these parameters are 
%         updated appropriately.
%
%       stp, fp, and dp are variables which specify the step,
%         the function, and the derivative at the current step.
%         If brackt is set true then on input stp must be
%         between stx and sty. On output stp is set to the new step.
%
%       brackt is a logical variable which specifies if a minimizer
%         has been bracketed. If the minimizer has not been bracketed
%         then on input brackt must be set false. If the minimizer
%         is bracketed then on output brackt is set true.
%
%       stpmin and stpmax are input variables which specify lower 
%         and upper bounds for the step.
%
%       info is an integer output variable set as follows:
%         If info = 1,2,3,4,5, then the step has been computed
%         according to one of the five cases below. Otherwise
%         info = 0, and this indicates improper input parameters.
%
%     Subprograms called
%
%       FORTRAN-supplied ... abs,max,min,sqrt
%                        ... dble
%
%     Argonne National Laboratory. MINPACK Project. June 1983
%     Jorge J. More', David J. Thuente
    

Definition at line 439 of file NOX_LineSearch_MoreThuente.C.

References absmax(), max(), and min().

Referenced by cvsrch().

double NOX::LineSearch::MoreThuente::max ( double  a,
double  b 
) [private]

max

Definition at line 638 of file NOX_LineSearch_MoreThuente.C.

Referenced by cstep(), and cvsrch().

double NOX::LineSearch::MoreThuente::min ( double  a,
double  b 
) [private]

min

Definition at line 633 of file NOX_LineSearch_MoreThuente.C.

Referenced by cstep(), and cvsrch().

double NOX::LineSearch::MoreThuente::absmax ( double  a,
double  b,
double  c 
) [private]

absmax - returns the max of the absolute value of the three inputs

Definition at line 644 of file NOX_LineSearch_MoreThuente.C.

Referenced by cstep().


Member Data Documentation

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

Definition at line 458 of file NOX_LineSearch_MoreThuente.H.

Common line search printing utilities.

Definition at line 461 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Common common counters for line searches.

Definition at line 464 of file NOX_LineSearch_MoreThuente.H.

Referenced by compute(), and cvsrch().

Common slope calculations for line searches.

Definition at line 467 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Teuchos::ParameterList* NOX::LineSearch::MoreThuente::paramsPtr [private]

Pointer to the input parameter list. This is saved so data stored in the counter object can be written to the "Output" parameter list.

Definition at line 470 of file NOX_LineSearch_MoreThuente.H.

Referenced by compute().

Sufficient decrease parameter.

Definition at line 473 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Curvature condition parameter.

Definition at line 475 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Threshold on width of the uncertainty.

Definition at line 477 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Minimum step.

Definition at line 479 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Maximum step.

Definition at line 481 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Maximum number of function evaluations.

Definition at line 483 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

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

Definition at line 494 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Default step length.

Definition at line 497 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Recovery step if linesearch fails.

Definition at line 499 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Chioce for the sufficient decrease criteria.

Definition at line 505 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

If set to true the value of $ s^TJ^Tf $ is estimated using a directional derivative. This eliminates having to compute the Jacobian at each inner iteration of the line search.

Definition at line 508 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().

Stores the merit function.

Definition at line 511 of file NOX_LineSearch_MoreThuente.H.

Referenced by cvsrch().


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

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