#include <APPSPACK_Directions.hpp>
Collaboration diagram for APPSPACK::Directions:
The job of this object is to generate an appropriate set of search directions for given point, and then to track and update the associated step lengths.
For each direction, we track the desired step length, the true step length (if the desired step length takes us outside the feasible region we instead substitute a step length that keeps us feasible), and the associated trial point tag.
The true step and tag are actually calculated by Solver::generateTrialPoints and just stored in this object for information purposes.
Parameters
These parameters are are stored in the Parameter::List that is passed to the Solver constructor. See Solver Parameters for full details on these parameters.
Definition at line 79 of file APPSPACK_Directions.hpp.
Public Member Functions  
Directions (Parameter::List ¶ms, const Constraints::Linear &constraints_in)  
Constructor.  
~Directions ()  
Destructor.  
Accessors  
void  getDirectionIndices (vector< int > &idvector) const 
Returns the indices of directions that are ready for new trial points.  
const Vector &  getDirection (int i) const 
Returns the ith search direction.  
double  getStep (int i) const 
Returns the ith step.  
void  setStepConverged (int i) 
Sets the step corresponding to the ith direction = stepTolerance/2.  
bool  isStepConverged () const 
Returns true if every step length is less than the step convergence tolerance.  
bool  empty () const 
Returns true of direction is empty, false otherwise.  
Manipulators  
void  computeNewDirections (const Point &newPoint) 
Computes a new set of search directions based on a new best point and resets the step information.  
void  appendNewDirections () 
Adds new directions when point remains the same but step is reduced.  
void  setTrueStepAndTag (int i, double trueStep_in, int tag_in) 
Set the true step and tag for the trial point corresponding to direction i.  
void  reduceStep (int i) 
Reduce the step corresponding to direction i.  
Printing  
void  print (const string label) const 
Print the directions, preceded by the given label  
double  getSmallestStep () const 
Returns the smallest step size for the direction that have not already converged.  
Private Member Functions  
Cone builders.  
void  buildNormalCone (Matrix &VpT, Matrix &VlT) const 
This method build the normal cone generators based on the current setting of the state vector constraintState.  
void  buildTangentCone (const Matrix &VpT, const Matrix &VlT, Matrix &T) 
This method builds the tangent cone base upon VpT and VlT.  
void  buildWithNothing (Matrix &D) 
Generate compass search directions for the variable bounds only case.  
bool  buildWithCddlib (const Matrix &VpT, const Matrix &VlT, Matrix &T) 
Generates pattern search directions using CDDLIB.  
bool  buildWithLapack (const Matrix &VpT, const Matrix &VlT, Matrix &T) 
Generate search directions using LAPACK.  
Direction generating methods  
void  generateUnconstrained (Matrix &D) 
Generates compass search directions for the "looks locally unconstrained" case.  
void  generateForLinear (Matrix &D) 
This method is called to generate search directions whenever general linear constraints are present.  
void  addNormalDirections (const Matrix &VpT, const Matrix &VlT, Matrix &D) 
Methods adds in the projected normals of the active linear inequality constraints.  
void  addCompassDirections (const Matrix &VlT, Matrix &D) 
Method adds projected compass search direction to D.  
bool  updateConstraintState (double newStep) 
Updates the state vector constraintState according to distances stored within xDistance.  
void  updateDirectionInfo (double newStep, bool isAppend=false) 
Updates the step, trueStep, and tag information.  
Private Attributes  
const Constraints::Linear &  constraints 
The constraints object.  
const int  nDimensions 
The number of dimensions.  
const Vector  zero 
The vector of all zeros.  
const double  stepTolerance 
The step tolerance used to test convergence, etc.  
const double  minStep 
Minimum size of the step after a new minimum is found.  
const double  theta 
Contraction parameter.  
const double  epsilonMax 
Defines maximum radius of about a current point used to determine active constraints.  
int  nDirections 
The current number of search directions.  
Matrix  direction 
The search directions are stored as rows of this matrix.  
Vector  step 
The steps associated with each search direction.  
Vector  trueStep 
The actual step associated with each search direction.  
vector< int >  tag 
The trial point tags corresponding to the search directions.  
Vector  tmpVector 
A temporary vector.  
vector< int >  idxVector 
A temporary integer vector.  
map< vector< Constraints::ActiveType >, Matrix >  directionCache 
Stores a cache of previously computed search directions.  
map< vector< Constraints::ActiveType >, Matrix >::iterator  cacheIter 
An iterator to be used in conjunction with the cached directions.  
vector< Constraints::ActiveType >  constraintState 
Stores a unique description of the tangent cone at the current point.  
double  epsilonMin 
Records the last value of epsilonMin used to determine active set.  
bool  withNormals 
If true, the projected constraints normals are added to direction.  
bool  withCompass 
If true, the projected compass search directions are added to direction.  
int  nCached 
Records number of time cached directions are used.  
int  nLapack 
Records number of times directions are generated using LAPACK.  
int  nCddlib 
Records number of times directions are generated using cddlib.  
int  nMaxDirections 
Records the maximum number of directions used per iteration.  
int  nAppend 
Records the number of times appendNewDirections() is called and nontrivial directions added.  
Vector  xDistance 
Stores distance from current point to each boundary wrt Constraints::Linear::aHat. 

Constructor. Reads the "Step Tolerance", "Minimum Step", "Contraction Factor", and "Epsilon Max" from the parameter list. Definition at line 46 of file APPSPACK_Directions.cpp. References epsilonMin, minStep, and stepTolerance. 

Destructor.
Definition at line 85 of file APPSPACK_Directions.cpp. 

Returns the indices of directions that are ready for new trial points. A direction is ready for a new trial point if its associated step length is greater than or equal to the convergence tolerance and it doesn't already have an active trial point. Definition at line 104 of file APPSPACK_Directions.cpp. References APPSPACK::Vector::push_back(), APPSPACK::Vector::resize(), step, and tag. Referenced by APPSPACK::Solver::generateTrialPoints(). 

Returns the ith search direction.
Definition at line 89 of file APPSPACK_Directions.cpp. References direction, and APPSPACK::Matrix::getRow(). Referenced by APPSPACK::Solver::generateTrialPoints(). 

Returns the ith step.
Definition at line 94 of file APPSPACK_Directions.cpp. References step. Referenced by APPSPACK::Solver::generateTrialPoints(). 

Sets the step corresponding to the ith direction = stepTolerance/2.
Definition at line 99 of file APPSPACK_Directions.cpp. References step, and stepTolerance. Referenced by APPSPACK::Solver::generateTrialPoints(). 

Returns true if every step length is less than the step convergence tolerance. The steps are stored in the step vector. The convergence tolerance is stored in stepTolerance. Definition at line 215 of file APPSPACK_Directions.cpp. References step. Referenced by APPSPACK::Solver::processEvaluatedTrialPoints(). 

Returns true of direction is empty, false otherwise.
Definition at line 226 of file APPSPACK_Directions.cpp. References direction, and APPSPACK::Matrix::empty(). 

Computes a new set of search directions based on a new best point and resets the step information. Search directions are computed by one of three private member functions: If only bound constraints are present, search direction are computed exclusively by buildWithNothing(). If general linear constraints are present, a call is first made to buildNormalCone(). This method returns the following:
If the search directions are already in directionCache, computeNewDirections() returns these directions. If buildNormalCone() returns false, search directions must be computed. Computing new search directions: generateUnconstrained() is called whenever the problem looks locally unconstrained, i.e. the normal cone Otherwise the search directions are computed with buildWithLapack() if possible. If buildWithLapack() is unsuccessful (this can happen if either the nearby constraints are degenerate or if APPSPACK was configured without LAPACK) buildWithCddlib() is then called. Finally, if user parameter "Add Projected Normals" is true, the projected normals are also added to the list of search directions. On exit the set of newly computed search direction are added to the direction cache and the current search directions are updated. computeNewDirections() also resets the step information. The initial step (which is the same for all directions) is calculated as
Here, is minStep. Definition at line 112 of file APPSPACK_Directions.cpp. References constraints, direction, APPSPACK::Matrix::empty(), APPSPACK::Constraints::Linear::formDistanceVector(), generateForLinear(), APPSPACK::Point::getStep(), APPSPACK::Point::getX(), theta, updateConstraintState(), updateDirectionInfo(), and xDistance. Referenced by APPSPACK::Solver::processNewBestPoint(). 

Adds new directions when point remains the same but step is reduced. The purpose of appendNewDirections is to handle the case when the step size is reduced. Because APPSPACK is asynchronous, the step size may be reduced for a given direction before the current point is rejected. In a sense, we do not know yet if , signifying a failed iteration, or if a new best point will be found. For failed iterations, the current point remains the same and the step size is reduced. Reducing the step size may alter the relevant tangent cone, i.e. fewer constraints will be seen as blocking placing increasing the number of relevant search directions. Thus, to remain theoretically convergent, trialpoints must be appended to the queue corresponding to these new directions in the advent that the current iteration fails. For this reason, appendNewDirections() will be called each time the reduced step corresponding to the ith direction satisfies
where equals the number of search directions.
Definition at line 153 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addUniqueRows(), constraints, direction, epsilonMin, generateForLinear(), APPSPACK::Constraints::Linear::getEpsMach(), getSmallestStep(), updateConstraintState(), and updateDirectionInfo(). Referenced by APPSPACK::Solver::processEvaluatedTrialPoints(). 

Set the true step and tag for the trial point corresponding to direction i.
Definition at line 179 of file APPSPACK_Directions.cpp. Referenced by APPSPACK::Solver::generateTrialPoints(). 

Reduce the step corresponding to direction i. The new step is calculated as
Also resets the corresponding trueStep and tag. Definition at line 231 of file APPSPACK_Directions.cpp. References step, tag, theta, and trueStep. Referenced by APPSPACK::Solver::processEvaluatedTrialPoints(). 

Print the directions, preceded by the given label
Definition at line 186 of file APPSPACK_Directions.cpp. References direction, APPSPACK::Matrix::getRow(), nAppend, nCached, nCddlib, nLapack, nMaxDirections, step, tag, and trueStep. Referenced by APPSPACK::Solver::generateTrialPoints(), APPSPACK::Solver::processNewBestPoint(), and APPSPACK::Solver::solve(). 

Returns the smallest step size for the direction that have not already converged.
Definition at line 622 of file APPSPACK_Directions.cpp. References APPSPACK::Vector::max(), APPSPACK::Vector::size(), and step. Referenced by appendNewDirections(), and updateDirectionInfo(). 

This method build the normal cone generators based on the current setting of the state vector constraintState. Let denote a matrix whose columns are obtained from the outward pointing normals of the active inequality constraints which are active on a single side. Let denote a matrix whose columns are obtained from the normals of the inequality constraints which are active at both their upper and lower bounds and the equality constraints. Then the normal cone is given by
Definition at line 241 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addMatrix(), APPSPACK::Matrix::addRow(), constraints, constraintState, APPSPACK::Constraints::Linear::getAhat(), APPSPACK::Constraints::Linear::getAtildeEq(), and APPSPACK::Matrix::getRow(). Referenced by generateForLinear(). 

This method builds the tangent cone base upon VpT and VlT. This method assumes the normal cone is given by
Definition at line 261 of file APPSPACK_Directions.cpp. References buildWithCddlib(), buildWithLapack(), buildWithNothing(), APPSPACK::Matrix::empty(), generateUnconstrained(), nCddlib, and nLapack. Referenced by generateForLinear(). 

Generate compass search directions for the variable bounds only case. This method in unique in that it does not require LAPACK or CDDLIB. Thus APPSPACK can reliably run (whenever only variable bounds are present) without either package. Definition at line 302 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addRow(), APPSPACK::Matrix::clear(), constraints, constraintState, APPSPACK::Constraints::Linear::getScaling(), and tmpVector. Referenced by buildTangentCone(). 

Generates pattern search directions using CDDLIB. A positive spanning set for the tangent to the normal cone
is generated by a call to compute_cone_generators(), where and are inputed in transpose form.
Definition at line 334 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addMatrix(), APPSPACK::Matrix::clear(), compute_cone_generators(), constraints, APPSPACK::Matrix::getNrows(), APPSPACK::Constraints::Linear::getScaling(), APPSPACK::Matrix::normalize(), APPSPACK::Matrix::scale(), and APPSPACK::Vector::size(). Referenced by buildTangentCone(). 

Generate search directions using LAPACK. The inputs define the normal cone
(Note that and are provided in transpose form.) The directions we need are the generators of the tangent cone . Let be a matrix whose columns form a basis for ; let be a right inverse for (if it exists), i.e., ; and let be a matrix whose columns form a basis for . Then:
Definition at line 385 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addMatrix(), APPSPACK::Matrix::clear(), constraints, APPSPACK::Matrix::empty(), APPSPACK::Constraints::Linear::getEpsMach(), APPSPACK::Matrix::getNcols(), APPSPACK::Matrix::getRighInvAndNullBasis(), APPSPACK::Constraints::Linear::getScaling(), APPSPACK::Matrix::multMat(), APPSPACK::Matrix::normalize(), APPSPACK::Matrix::nullSpace(), APPSPACK::Matrix::scale(), and APPSPACK::Matrix::setToIdentity(). Referenced by buildTangentCone(). 

Generates compass search directions for the "looks locally unconstrained" case.
Definition at line 453 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addRow(), APPSPACK::Matrix::clear(), constraints, APPSPACK::Constraints::Linear::getScaling(), and tmpVector. Referenced by addCompassDirections(), and buildTangentCone(). 

This method is called to generate search directions whenever general linear constraints are present. The method first checks the direction cache, directionCache, directions for the current setting of constraintState have already been computed. If the corresponding search directions have been found within the cache, input parameter D is updated accordingly. If search directions are not found in the cache, the normal cone generators N are formed and the tangent cone T computed (stored by rows). If no tangent directions are found, i.e. T is empty, then
If nontrivial tangent directions are found, then
Definition at line 471 of file APPSPACK_Directions.cpp. References addCompassDirections(), addNormalDirections(), buildNormalCone(), buildTangentCone(), cacheIter, APPSPACK::Matrix::clear(), constraintState, directionCache, APPSPACK::Matrix::empty(), and nCached. Referenced by appendNewDirections(), and computeNewDirections(). 

Methods adds in the projected normals of the active linear inequality constraints. This method assumes the normal cone is given by
Definition at line 511 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addMatrix(), constraints, APPSPACK::Matrix::empty(), APPSPACK::Constraints::Linear::getEpsMach(), APPSPACK::Constraints::Linear::getScaling(), APPSPACK::Matrix::multMat(), APPSPACK::Matrix::normalize(), APPSPACK::Matrix::nullSpace(), and APPSPACK::Matrix::scale(). Referenced by generateForLinear(). 

Method adds projected compass search direction to D.
Definition at line 543 of file APPSPACK_Directions.cpp. References APPSPACK::Matrix::addUniqueRows(), constraints, APPSPACK::Matrix::empty(), generateUnconstrained(), APPSPACK::Constraints::Linear::getEpsMach(), APPSPACK::Constraints::Linear::getScaling(), APPSPACK::Matrix::multMat(), APPSPACK::Matrix::normalize(), APPSPACK::Matrix::nullSpace(), and APPSPACK::Matrix::scale(). Referenced by generateForLinear(). 

Updates the state vector constraintState according to distances stored within xDistance. To determine which constraints are active (or near active), an epsilon ball is defined about the current point, with x denoting the current point and defined by
Here epsilonMax, and is given by input parameter newStep. All constraints which pass through this epsilon ball are considered active. Essentially, the constraint is considered active if
Activity of constraints is always determined in the scaled space. This method updates constraintState via a call to Constraints::Linear::getActiveIndex(), passing in as parameters xDistance and epsilon. The parameter xDistance provides a measure of the distance to each inequality constraint from the current point; it is assumed that xDistance has already been updated prior to function call.
Definition at line 573 of file APPSPACK_Directions.cpp. References constraints, constraintState, epsilonMax, APPSPACK::Constraints::Linear::getActiveIndex(), and xDistance. Referenced by appendNewDirections(), and computeNewDirections(). 

Updates the step, trueStep, and tag information.
Definition at line 592 of file APPSPACK_Directions.cpp. References APPSPACK::Vector::append(), APPSPACK::Vector::assign(), direction, epsilonMax, epsilonMin, APPSPACK::Matrix::getNrows(), getSmallestStep(), nAppend, nDirections, nMaxDirections, step, tag, and trueStep. Referenced by appendNewDirections(), and computeNewDirections(). 

The constraints object.
Definition at line 435 of file APPSPACK_Directions.hpp. Referenced by addCompassDirections(), addNormalDirections(), appendNewDirections(), buildNormalCone(), buildWithCddlib(), buildWithLapack(), buildWithNothing(), computeNewDirections(), generateUnconstrained(), and updateConstraintState(). 

The number of dimensions.
Definition at line 438 of file APPSPACK_Directions.hpp. 

The vector of all zeros.
Definition at line 441 of file APPSPACK_Directions.hpp. 

The step tolerance used to test convergence, etc.
Definition at line 444 of file APPSPACK_Directions.hpp. Referenced by Directions(), and setStepConverged(). 

Minimum size of the step after a new minimum is found.
Definition at line 447 of file APPSPACK_Directions.hpp. Referenced by Directions(). 

Contraction parameter.
Definition at line 450 of file APPSPACK_Directions.hpp. Referenced by computeNewDirections(), and reduceStep(). 

Defines maximum radius of about a current point used to determine active constraints.
Definition at line 453 of file APPSPACK_Directions.hpp. Referenced by updateConstraintState(), and updateDirectionInfo(). 

The current number of search directions.
Definition at line 456 of file APPSPACK_Directions.hpp. Referenced by updateDirectionInfo(). 

The search directions are stored as rows of this matrix.
Definition at line 459 of file APPSPACK_Directions.hpp. Referenced by appendNewDirections(), computeNewDirections(), empty(), getDirection(), print(), and updateDirectionInfo(). 

The steps associated with each search direction.
Definition at line 462 of file APPSPACK_Directions.hpp. Referenced by getDirectionIndices(), getSmallestStep(), getStep(), isStepConverged(), print(), reduceStep(), setStepConverged(), and updateDirectionInfo(). 

The actual step associated with each search direction. The step represents the longest feasible step that is less than or equal to the corresponding delta. Definition at line 468 of file APPSPACK_Directions.hpp. Referenced by print(), reduceStep(), setTrueStepAndTag(), and updateDirectionInfo(). 

The trial point tags corresponding to the search directions. A value of 1 means that there is no trial point associated with the given direction. Definition at line 474 of file APPSPACK_Directions.hpp. Referenced by getDirectionIndices(), print(), reduceStep(), setTrueStepAndTag(), and updateDirectionInfo(). 

A temporary vector.
Definition at line 477 of file APPSPACK_Directions.hpp. Referenced by buildWithNothing(), and generateUnconstrained(). 

A temporary integer vector.
Definition at line 480 of file APPSPACK_Directions.hpp. 

Stores a cache of previously computed search directions. A vector<Constraints::ActiveType> is paired with a corresponding set of search directions (stored as a Matrix) in a map to form a direction cache. Each Matrix stored in directionCache consists of
Definition at line 494 of file APPSPACK_Directions.hpp. Referenced by generateForLinear(). 

An iterator to be used in conjunction with the cached directions.
Definition at line 497 of file APPSPACK_Directions.hpp. Referenced by generateForLinear(). 

Stores a unique description of the tangent cone at the current point. A call to Constraints::Linear::getActiveIndex() returns a vector of type enum Constraints::ActiveType which uniquely identifies the tangent cone at a given point. Definition at line 505 of file APPSPACK_Directions.hpp. Referenced by buildNormalCone(), buildWithNothing(), generateForLinear(), and updateConstraintState(). 

Records the last value of epsilonMin used to determine active set.
Definition at line 508 of file APPSPACK_Directions.hpp. Referenced by appendNewDirections(), Directions(), and updateDirectionInfo(). 

If true, the projected constraints normals are added to direction.
Definition at line 511 of file APPSPACK_Directions.hpp. 

If true, the projected compass search directions are added to direction.
Definition at line 514 of file APPSPACK_Directions.hpp. 

Records number of time cached directions are used.
Definition at line 517 of file APPSPACK_Directions.hpp. Referenced by generateForLinear(), and print(). 

Records number of times directions are generated using LAPACK.
Definition at line 520 of file APPSPACK_Directions.hpp. Referenced by buildTangentCone(), and print(). 

Records number of times directions are generated using cddlib.
Definition at line 523 of file APPSPACK_Directions.hpp. Referenced by buildTangentCone(), and print(). 

Records the maximum number of directions used per iteration.
Definition at line 526 of file APPSPACK_Directions.hpp. Referenced by print(), and updateDirectionInfo(). 

Records the number of times appendNewDirections() is called and nontrivial directions added.
Definition at line 529 of file APPSPACK_Directions.hpp. Referenced by print(), and updateDirectionInfo(). 

Stores distance from current point to each boundary wrt Constraints::Linear::aHat.
Definition at line 532 of file APPSPACK_Directions.hpp. Referenced by computeNewDirections(), and updateConstraintState(). 
© Sandia Corporation  Site Contact  Privacy and Security
Generated on Fri Feb 16 10:33:36 2007 for APPSPACK 5.0.1 by 1.3.9.1 written by Dimitri van Heesch, © 19972002