---

armijo.h

// Emacs will be in -*- Mode: c++ -*-
//
// ************ DO NOT REMOVE THIS BANNER ****************
//
//  Nicolas Di Cesare <Nicolas.Dicesare@free.fr>
//  http://acm.emath.fr/~dicesare
//
//********************************************************
//
//  Armijo Line Search
//
//********************************************************
#ifndef _armijo_h_
#define _armijo_h

#include <linesearch.h>
#include <optimizer.h>

template <class V>
class ArmijoLineSearch : public LineSearch<V> {
public:
  typedef double value_type;
protected:  
  double alpha_, beta_;
public:
  ArmijoLineSearch(double eps = 1e-8,double alpha = 0.5, double beta = 0.65)
    : LineSearch<V>(eps), alpha_(alpha), beta_(beta)  { }
  virtual ~ArmijoLineSearch() {}

  virtual value_type operator() (OptimizationProblem<V>& P, // Optimization problem 
                 value_type t_ini,          // initial value of line-search step
                 value_type q0,             // function value
                 value_type qp0)            // squared norm of gradient vector
  {
    bool maxIter = false;
    qt_ = q0; qpt_ = qp0;
    double qtold, qptnew, t = t_ini;
    int loopNumber = 0;

    OptimizationMethod<V> & method = P.optimisationMethod();
    V & x = method.x();
    V & d = method.searchDirection();

    // Initialize gradient
    gradient_ = V(x.size());
    // Compute new point
    xtd_ = x + t * d;
    // Compute function value at the new point
    qt_ = P.value(xtd_);

    // Enter in the loop if the criterion is not satisfied
#ifdef DEBUG_ARMIJO
    std::cout << "qt_ - q0 = " << (qt_ - q0) << ", - alpha_ * t * qpt_ = " << (- alpha_ * t * qpt_) << std::endl;
#endif

    if ((qt_ - q0) > - alpha_ * t * qpt_ ) {
      do {
    loopNumber++;
    // Decrease step
    t *= beta_;
    // Store old value of the function
    qtold = qt_;
    // New point value
    xtd_ = x + t * d;
    // Compute function value at the new point
    qt_ = P.value(xtd_);
    P.firstDerivative(gradient_,xtd_);
    // and it squared norm
    qptnew = DotProduct(gradient_,gradient_);
#ifdef DEBUG_ARMIJO
    std::cout << loopNumber << ", qt_ - q0 = " << (qt_ - q0) << ", - alpha_ * t * qpt_ = " << (- alpha_ * t * qpt_) << std::endl;
    std::cout << "qtold - q0 = " << (qtold - q0) << ", - alpha_ * t * qpt_ / beta_ = " << (- alpha_ * t * qpt_ / beta_) << std::endl;
#endif
    maxIter = P.optimisationMethod().endCriteria().checkIterationNumber(loopNumber);
      } // Armijo criteria
      while ( 
         ( ( (qt_ - q0) > (-alpha_ * t * qpt_) ) 
           || ((qtold - q0) <= (-alpha_ * t * qpt_ / beta_)) ) 
         && (!maxIter)
         );
    }
  
    if ( maxIter ) {
      succeed_ = false;
    }

    // Compute new gradient
    P.firstDerivative(gradient_,xtd_);
    // and it squared norm
    qpt_ = DotProduct(gradient_,gradient_);

    // Return new step value
    return t;
  }

};


#endif

---