47.1. Solver Routine

All TAO solvers have a routine that accepts a TAO structure and computes a solution. TAO will call this routine when the application program uses the routine TaoSolve() and pass to the solver information about the objective function and constraints, pointers to the variable vector and gradient vector, and support for line searches, linear solvers, and convergence monitoring. As an example, consider the following code which solves an unconstrained minimization problem using the Fletcher--Reeves conjugate gradient method.


static int TaoSolve_CG_FR(TAO_SOLVER tao, void *solver){ 
 
  TAO_CG  *cg = (TAO_CG *) solver; 
  TaoVec  *xx,*gg=cg->gg;    /* solution vector, gradient vector */ 
  TaoVec  *dx=cg->dx, *ww=cg->ww; 
  int     iter=0,lsflag=0,info; 
  double  gnormPrev,gdx,f,gnorm,step=0; 
  TaoTerminateReason reason; 
 
  TaoFunctionBegin; 
  info=TaoCheckFG(tao);CHKERRQ(info); 
  info=TaoGetSolution(tao,&xx);CHKERRQ(info); 
 
  info = TaoComputeMeritFunctionGradient(tao,xx,&f,gg);CHKERRQ(info); 
  info = gg->Norm2(&gnorm);  CHKERRQ(info); 
 
  info = dx->SetToZero(); CHKERRQ(info);  
 
  cg->beta=0; 
  gnormPrev = gnorm; 
 
  /* Enter loop */ 
  while (1){ 
 
    /* Test for convergence */ 
    info = TaoMonitor(tao,iter++,f,gnorm,0.0,step,&reason);CHKERRQ(info); 
    if (reason!=TAO_CONTINUE_ITERATING) break; 
 
    cg->beta=(gnorm*gnorm)/(gnormPrev*gnormPrev); 
    info = dx->Axpby(-1.0,gg,cg->beta); CHKERRQ(info); 
     
    info = dx->Dot(gg,&gdx); CHKERRQ(info); 
    if (gdx>=0){     /* If not a descent direction, use gradient */ 
      cg->beta=0.0; 
      info = dx->Axpby(-1.0,gg,cg->beta); CHKERRQ(info); 
      gdx=-gnorm*gnorm; 
    }  
 
    /* Line Search */ 
    gnormPrev = gnorm;  step=1.0; 
    info = TaoLineSearchApply(tao,xx,gg,dx,ww,&f,&step,&lsflag); 
    info = gg->Norm2(&gnorm);CHKERRQ(info); 
 
  } 
   
  TaoFunctionReturn(0); 
} 
The first line of this routine cast the second argument to a pointer to a TAO_CG data structure. This structure contains pointers to three vectors and a scalar which will be needed in the algorithm.

After declaring an initializing several variables, the solver first checks that the function and gradient have been defined using the routine TaoCheckFG(). Next, the solver gets the variable vector which was passed to TAO by the application program. Other solvers may also want to get pointers to Hessian matrices, Jacobian matrices, or vectors containing bounds on the variables. The commands for these routines are TaoGetSolution(), TaoGetVariableBounds(), TaoGetHessian(), and TaoGetJacobian().

This solver lets TAO evaluate the function and gradient at the current point in the using the routine TaoComputeFunctionGradient(). Other routines may be used to evaluate the Hessian matrix or evaluate constraints. TAO may obtain this information using direct evaluation of other means, but the these details do not affect our implementation of the algorithm.

The norm of the gradient is a standard measure used by unconstrained minimization solvers to define convergence. This quantity is always nonnegative and equals zero at the solution. The solver will pass this quantity, the current function value, the current iteration number, and a measure of infeasibility to TAO with the routine

   int TaoMonitor(TAO_SOLVER,int,double,double,double,double, 
                  TaoTerminateReason*); 
Most optimization algorithms are iterative in nature, and solvers should include this command somewhere in each iteration. This routine records this information, applies any monitoring routines and convergence tests set by default or the user.

In this routine, the second argument is the current iteration number, and the third argument is the current function value. The fourth argument is a nonnegative error measure associated with the distance between the current solution and the optimal solution. Examples of this measure are the norm of the gradient or the square root of a duality gap. The fifth measure is a nonnegative error that is nonnegative and usually represents a residual between the current function value and the optimal solution, such as the norm of the gradient. The sixth argument is a nonnegative steplength, or the multiple of the step direction added to the previous iterate. The results of the convergence test are returned in the last argument. If the termination reason is TAO_CONTINUE_ITERATING, the algorithm should continue.

After this monitoring routine, the solver computes a step direction using methods defined on the TaoVec object. These methods include adding vectors together and computing an inner product. A full list of these methods can be found in the manual pages.

Nonlinear conjugate gradient algorithms also require a line search. TAO provides several line searches and support for using them. The routine

   int TaoLineSearchApply(TAO_SOLVER tao, TaoVec *xx, TaoVec *gg, TaoVec *dx, 
                          TaoVec *ww, double *f, double *step, 
                          int*flag) 
passes the current solution, gradient, and objective value to the solver and returns a new solution, gradient, and objective value. More details on line searches can be found in the Section The details of this line search are should be specified elsewhere, when the line search is created.

TAO also includes support for linear solvers. Although this algorithm does not require one, linear solvers are an important part of many algorithms. Details on the use of these solvers can be found in Section .