Documentation

Abstract base class for line search routines. The purpose of a line search algorithm is to locate an approximate minimizer of a function . Such problems arise in certain algorithms for unconstrained and constrained optimization, where is a 1D "slice" of the objective or merit function. The is, the original problem is to minimizer some function , where is a Hilbert space, and is defined by , where and are vectors in .

The main method in a HCL_LineSearch_d class is Search, which is invoked as follows:

   MyFcnl f;  // MyFcnl must be derived from HCL_Functional_d
   MyVector x( "x0" ); // Assume MyVector has a constructor which
                       //reads from a file
   MyVector y( "direction" );
   MyVector * xnext = new MyVector( x );  // Assume MyVector has a copy
                                          // constructor.

   HCL_LineSearch_DS_d lsearch( "lsearch.dat" );  // Dennis-Schnabel
                                                  // line search
   HCL_EvaluateFunctional_d * eval = f.EvaluateGrad( x );
   HCL_EvaluateFunctional_d * evalnext 
                                  lsearch.Search( f,x,*xnext,y,eval );

Note that it is necessary to evaluate the functional at the initial point and pass this evaluation object to the Search method. The method attempts to locate a suitable point and return it in the vector pointed to by the pointer xnext. Also, the evaluation object of is the return value of the method.

Standard line search algorithms are usually based on one or two goals. Essentially all algorithms attempt to reduce the value of the function from , usually by satisfying a condition (the assumption is made that is negative). The number in the above inequality is a standard input parameter to a line search algorithm; in HCL this parameter is called FcnDecreaseTol. A second goal which is often sought is the reduction of the slope from : The tolerance in this condition is called SlopeDecreaseTol in HCL.

Other important parameters appearing in line search algorithms are MaxSample (the maximum number of times that the function can be sampled before the algorithm gives up), and MinStep and MaxStep (the smallest and largest allowable steps). For a complete list of algorithmic parameters, see the Input parameters documentation for the base class, and for each concrete derived class (note that a specific algorithm may use a parameter not mentioned in the base class).

Algorithmic parameters can be accessed or modified through the Parameters method of the class, which returns a reference to the parameter table (see the Table class for more details about parameter tables):

   lsearch.Parameters().GetValue( "MinStep",m ); // Gets the value of
                                                 // the parameter MinStep
                                                 // and puts it in m.
   lsearch.Parameters().PutValue( "MinStep",2*m ); // Sets the value of
                                                   // the parameter MinStep
                                                   // to 2*m.

In addition, derived line search classes should have constructors which take a file name and read parameters from that file (using the Table file format). All input parameters have default values which are given in the (derived) class documentation.

All line searchs are required to set two output parameters in the paramter table, TermCode and MaxTkn. The possible values of TermCode are given by the enum variable ErrorCodes. The documentation of ErrorCodes should be consulted for a complete list of codes, but the following convention is followed: 0 means a succesful completion, a positive values means that the algorithm succeeded in reducing the function value, although the termination criteria were not all satisfied, and a negative value indicates that the search was unable to reduce the function value. MaxTkn is a boolean integer variable; if it is set, this indicates that the step taken was of length MaxStep.