Optimization algorithm: LineSearch. More...

#include <optimizerLineSearch.h>

Inheritance diagram for olb::opti::OptimizerLineSearch< S, C >:

Collaboration diagram for olb::opti::OptimizerLineSearch< S, C >:

Public Member Functions
	OptimizerLineSearch (int dimCtrl, S eps, int maxIt, S lambda, int maxStepAttempts, std::string stepCondition, bool verboseOn=true, const std::string fname="", const std::string logFileName="", bool withUpperBound=false, S upperBound=S(), bool withLowerBound=false, S lowerBound=S(), bool vectorBounds=false, S controlEps=S(std::numeric_limits< double >::epsilon()), bool failOnMaxIter=true, std::vector< OptimizerLogType > gplotAnalysis={})
	Construction of an OptimizerLineSearch.

virtual	~OptimizerLineSearch ()

virtual void	computeDirection ()=0

void	checkBound ()

void	boundControl ()

bool	smallerValue (const S &tempValue)

bool	noCondition (const S &tempValue)

bool	armijoWolfeConditions (const S &tempValue)

void	quadraticInterpolationStep (const S &tempValue)

void	backtrackingLineSearch (S &tempValue, S lambda, bool(OptimizerLineSearch::*condition)(const S &))

virtual void	optimizationStep ()
	Optimization step: line search.

Public Member Functions inherited from olb::opti::Optimizer< S, C >
	Optimizer (int dimCtrl, S eps, int maxIt, bool verboseOn=true, const std::string fname="", const std::string logFileName="", bool withUpperBound=false, S upperBound=S(), bool withLowerBound=false, S lowerBound=S(), bool vectorBounds=false, S controlEps=S(std::numeric_limits< double >::epsilon()), bool failOnMaxIter=true, std::vector< OptimizerLogType > gplotAnalysis={})

virtual	~Optimizer ()

void	maxIterationReached ()

virtual void	optimize ()

virtual void	optimize (OptiCase< S, C > &optiCase)

void	simulate ()

void	simulate (OptiCase< S, C > &optiCase)

void	evaluateObjective (const C &control, S &result)

void	computeDerivatives (const C &control, C &derivatives)

void	print (int it)
	Prints information of the current optimization step it.

void	setControl (C &control)

const C &	getControl () const

const C &	getDerivative () const

const S &	getObjective () const

int	getIteration () const

void	writeControlToFile (const std::string fname="control.dat")
	Writes the current control variables linewise into file fname.

void	readControlFromFile (const std::string fname="control.dat")
	Reads the latest control variables from file fname.

void	setStartValue (S startValue)

OptiCase< S, C > *	getOptiCase ()

void	setOptiCase (OptiCase< S, C > *optiCase)

void	setGnuplotData ()

void	setReferenceControl (C result)
	set the reference value for the control vector (exact solution)

Protected Attributes
S	_lambda
	Lambda start value.

C	_direction
	Search direction.

bool	_lowerBoundFlag

bool	_upperBoundFlag

int	_maxStepAttempts
	Maximal number of step attempts for conditioned line search.

C	_nextDerivative

bool	_nextDerivFlag

std::string	_stepCondition

bool(OptimizerLineSearch::*	_stepConditionFunction )(const S &)

void(OptimizerLineSearch::*	_stepLengthFunction )(const S &)

Protected Attributes inherited from olb::opti::Optimizer< S, C >
int	_dimCtrl
	Number of controlled variables.

C	_control
	Vector of controlled variables (size _dimCtrl)

S	_value
	Value of the objective functional evaluated for controlled variables saved in _control.

C	_derivative
	Vector of derivatives of the object functional with respect to the controlled variables.

int	_it
	Current iteration no.

int	_maxIt
	Maximal number of iteration.

bool	_failOnMaxIter
	Fail when max number of iteration reached.

S	_eps
	Optimizer stops if \|_derivatives\| < _eps.

bool	_verboseOn
	Verbose.

bool	_withUpperBound
	Bounded versions.

bool	_withLowerBound

bool	_vectorBounds

C	_boundedControl

C	_upperBound

C	_lowerBound

bool	_controlsConverged
	For setting tolerance of controls.

S	_controlEps

OptiCase< S, C > *	_optiCase
	Provides the Optimizer with methods to evaluate the value of an object functional and compute derivatives.

C	_referenceControl
	control vector to compare with (for numerical evaluation)

Additional Inherited Members
Public Attributes inherited from olb::opti::Optimizer< S, C >
Gnuplot< S >	gplot

std::vector< OptimizerLogType >	_gplotAnalysis
	For defining what kind of gnuplot analysis is wanted, if empty vector - no analysis, value, control and derivative are the possible options.

Detailed Description

template<typename S, typename C>
class olb::opti::OptimizerLineSearch< S, C >

Optimization algorithm: LineSearch.

OptimizerLineSearch optimizes an optimization problem which is given in OptiCase. OptiCase provides therefore methods to evaluate an object functional and compute derivatives. LineSearch searches along a particular direction to find a lower value of the evaluated object functional.

This class is intended to be derived from.

Definition at line 51 of file optimizerLineSearch.h.

Constructor & Destructor Documentation

◆ OptimizerLineSearch()

template<typename S , typename C >

olb::opti::OptimizerLineSearch< S, C >::OptimizerLineSearch	(	int	dimCtrl,
		S	eps,
		int	maxIt,
		S	lambda,
		int	maxStepAttempts,
		std::string	stepCondition,
		bool	verboseOn = true,
		const std::string	fname = "",
		const std::string	logFileName = "",
		bool	withUpperBound = false,
		S	upperBound = S(),
		bool	withLowerBound = false,
		S	lowerBound = S(),
		bool	vectorBounds = false,
		S	controlEps = S(std::numeric_limits<double>::epsilon() ),
		bool	failOnMaxIter = true,
		std::vector< OptimizerLogType >	gplotAnalysis = {} )

inline

Construction of an OptimizerLineSearch.

Define step conditions and step length calculation

Definition at line 77 of file optimizerLineSearch.h.

                                                                  {})
    : Optimizer<S,C>(dimCtrl, eps, maxIt, verboseOn, fname, logFileName, withUpperBound, upperBound, withLowerBound,
                   lowerBound, vectorBounds, controlEps, failOnMaxIter, gplotAnalysis),
      clout(std::cout,"OptimizerLineSearch")
  {
    _lambda = lambda;
    _direction = util::ContainerCreator<C>::create(dimCtrl);
    _nextDerivative = util::ContainerCreator<C>::create(dimCtrl);
    _maxStepAttempts = maxStepAttempts;
    _stepCondition = stepCondition;
    _lowerBoundFlag = false;
    _upperBoundFlag = false;
    _nextDerivFlag = false;
 
    // No Condition
    if (_stepCondition == "None") {
      _stepConditionFunction = &OptimizerLineSearch::noCondition;
      _stepLengthFunction = nullptr;
      // Smaller objective function
    }
    else if (_stepCondition == "Smaller") {
      _stepConditionFunction = &OptimizerLineSearch::smallerValue;
      _stepLengthFunction = &OptimizerLineSearch::quadraticInterpolationStep;
      // Armijo, Wolfe and Strong Wolfe conditions
    }
    else if (_stepCondition == "Armijo" || _stepCondition == "Wolfe" || _stepCondition == "StrongWolfe") {
      _stepConditionFunction = &OptimizerLineSearch::armijoWolfeConditions;
      _stepLengthFunction = &OptimizerLineSearch::quadraticInterpolationStep;
    }
    else {
      clout << "No step condition chosen! Exiting..." << std::endl;
      exit(1);
    }
 
  };

◆ ~OptimizerLineSearch()

template<typename S , typename C >

virtual olb::opti::OptimizerLineSearch< S, C >::~OptimizerLineSearch ( )

inlinevirtual

Definition at line 119 of file optimizerLineSearch.h.

119{ };

Member Function Documentation

◆ armijoWolfeConditions()

template<typename S , typename C >

bool olb::opti::OptimizerLineSearch< S, C >::armijoWolfeConditions ( const S & tempValue )

inline

Definition at line 203 of file optimizerLineSearch.h.

  {
    S c1 = 1e-4;
    S c2 = 0.9; // 0.9 for (quasi)Newton; else 0.1
    S dir = 0.;
    S dirNext = 0.;
 
    // \nabla f_k \dot p_k
    for (int i=0; i<this->_dimCtrl; i++) {
      dir += this->_direction[i] * this->_derivative[i];
    }
 
    // Armijo rule
    if (!(tempValue <= this->_value + c1*this->_lambda*dir)) {
      if (this->_verboseOn) {
        clout << "Armijo failed!" << std::endl;
      }
      // Decrease step length
      (this->*_stepLengthFunction)(tempValue);
      //this->_lambda *= .5;
      return false;
    }
    // (strong) Wolfe conditions (curvature condition)
    if ( _stepCondition == "Wolfe" || _stepCondition == "StrongWolfe") {
      // Compute derivative for the changed control and store it in nextDerivative
      // Set nextDerivFlag to true to prevent the optiCase to redo this process
      this->computeDerivatives(this->_control, _nextDerivative);
      _nextDerivFlag = true;
      // \nabla f_{k+1} \dot p_k
      for (int i=0; i<this->_dimCtrl; i++) {
        dirNext += this->_direction[i]*_nextDerivative[i];
      }
      bool curvature = ( dirNext <= c2*dir );
      if (_stepCondition == "StrongWolfe") {
        curvature = ( util::abs(dirNext) <= c2*util::abs(dir) );
      }
 
      if (!curvature) {
        if (this->_verboseOn) {
          clout << "Curvature failed!" << std::endl;
        }
        // Increase step length
        this->_lambda *= 2.1;
        return false;
      }
    }
    return true;
  }

Here is the call graph for this function:

◆ backtrackingLineSearch()

template<typename S , typename C >

void olb::opti::OptimizerLineSearch< S, C >::backtrackingLineSearch	(	S &	tempValue,
		S	lambda,
		bool(OptimizerLineSearch< S, C >::*)(const S &)	condition )

inline

Definition at line 276 of file optimizerLineSearch.h.

  {
 
    // Save this->_lambda so that it is unchanged after the line search
    S startLambda = this->_lambda;
    int refinementStep = 0;
    // Do line search until the condition is fullfilled
    // the step size (this->_lambda) will be changed in the condition
    while ( !(this->*condition)(tempValue) ) {
      if ( util::abs(lambda/this->_value) < std::numeric_limits<double>::epsilon() ) {
        clout << "Excessive refinement steps (too small step size).\nProgram terminated." <<std::endl;
        exit(1);
      }
      refinementStep++;
 
      // Leave program if maximum number of step attempts is exceeded.
      if ( refinementStep >= _maxStepAttempts ) {
        clout << "Excessive refinement steps (maxStepAttempts exeeded).\nProgram terminated." <<std::endl;
        exit(1);
      }
 
      S newLambda = this->_lambda;
      bool notSensible = true;
      for (int iDim=0; iDim<this->_dimCtrl; iDim++) {
        // Go back (newLambda-lambda) from previous control(=control-lambda*direction),
        // therefore this produces a step of newLambda*direction
        S tmp  = (newLambda-lambda)*this->_direction[iDim];
        this->_control[iDim] -= tmp;
        // is this move larger than machine precision wrt control
        if (util::abs(this->_control[iDim]) > 0 && util::abs(tmp) > 0) {
          notSensible &= ( util::nearZero(tmp/this->_control[iDim]) );
        }
      }
      // stop excessive refinement steps when values become no longer sensible
      if (notSensible) {
        clout << "Excessive refinement steps (not sensible).\nProgram terminated." <<std::endl;
        exit(1);
      }
 
      if (this->_withUpperBound||this->_withLowerBound) {
        boundControl();
      }
 
      if (this->_verboseOn) {
        clout << "[Step " << this->_it << "][Ref " << refinementStep << "] <<<<<<<<<< lambda=" << newLambda << " <<<<<<<<<<" << std::endl;
      }
 
      if (this->_withUpperBound||this->_withLowerBound) {
        this->evaluateObjective(this->_boundedControl, tempValue);
      }
      else {
        this->evaluateObjective(this->_control, tempValue);
      }
      lambda = newLambda;
    }
    this->_lambda = startLambda;
  };

Here is the call graph for this function:

Here is the caller graph for this function:

◆ boundControl()

template<typename S , typename C >

void olb::opti::OptimizerLineSearch< S, C >::boundControl ( )

inline

Definition at line 161 of file optimizerLineSearch.h.

  {
    for (int iDim=0; iDim<this->_dimCtrl; iDim++) {
      this->_boundedControl[iDim] = this->_control[iDim];
      const int i = (this->_vectorBounds) ? iDim : 0;
      if (this->_withUpperBound) {
        const S tmp = this->_upperBound[i];
        if (this->_control[iDim] > tmp ||
            (std::isnan(this->_control[iDim])
             && !std::signbit(this->_control[iDim])) ) {
          this->_boundedControl[iDim] = tmp;
        }
      }
      if (this->_withLowerBound) {
        const S tmp = this->_lowerBound[i];
        if (this->_control[iDim] < tmp ||
            (std::isnan(this->_control[iDim])
             && std::signbit(this->_control[iDim])) ) {
          this->_boundedControl[iDim] = tmp;
        }
      }
    }
  };

References olb::opti::Optimizer< S, C >::_boundedControl, olb::opti::Optimizer< S, C >::_control, olb::opti::Optimizer< S, C >::_dimCtrl, olb::opti::Optimizer< S, C >::_lowerBound, olb::opti::Optimizer< S, C >::_upperBound, olb::opti::Optimizer< S, C >::_vectorBounds, olb::opti::Optimizer< S, C >::_withLowerBound, and olb::opti::Optimizer< S, C >::_withUpperBound.

Here is the caller graph for this function:

◆ checkBound()

template<typename S , typename C >

void olb::opti::OptimizerLineSearch< S, C >::checkBound ( )

inline

Definition at line 123 of file optimizerLineSearch.h.

  {
    if (this->_withUpperBound) {
      bool atUpper = true;
      for (int iDim=0; iDim<this->_dimCtrl; ++iDim) {
        const int i = (this->_vectorBounds) ? iDim : 0;
        atUpper &= (util::nearZero(this->_boundedControl[iDim] - this->_upperBound[i]));
      }
      if (atUpper) {
        if (_upperBoundFlag) {
          clout << "Control stuck at upper bound: " <<  std::string(this->_upperBound.begin(), this->_upperBound.end()) << std::endl;
          exit(1);
        }
        _upperBoundFlag = true;
      }
      else {
        _upperBoundFlag = false;
      }
    }
    if (this->_withLowerBound) {
      bool atLower = true;
      for (int iDim=0; iDim<this->_dimCtrl; ++iDim) {
        const int i = (this->_vectorBounds) ? iDim : 0;
        atLower &= (util::nearZero(this->_boundedControl[iDim] - this->_lowerBound[i]));
      }
      if (atLower) {
        if (_lowerBoundFlag) {
          clout << "Control stuck at lower bound: " << std::string(this->_lowerBound.begin(), this->_lowerBound.end()) << std::endl;
          exit(1);
        }
        _lowerBoundFlag = true;
      }
      else {
        _lowerBoundFlag = false;
      }
    }
  };

References olb::opti::Optimizer< S, C >::_boundedControl, olb::opti::Optimizer< S, C >::_dimCtrl, olb::opti::Optimizer< S, C >::_lowerBound, olb::opti::OptimizerLineSearch< S, C >::_lowerBoundFlag, olb::opti::Optimizer< S, C >::_upperBound, olb::opti::OptimizerLineSearch< S, C >::_upperBoundFlag, olb::opti::Optimizer< S, C >::_vectorBounds, olb::opti::Optimizer< S, C >::_withLowerBound, olb::opti::Optimizer< S, C >::_withUpperBound, and olb::util::nearZero().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ computeDirection()

template<typename S , typename C >

virtual void olb::opti::OptimizerLineSearch< S, C >::computeDirection ( )

pure virtual

Implemented in olb::opti::OptimizerBarzilaiBorwein< S, C >, olb::opti::OptimizerLBFGS< S, C >, and olb::opti::OptimizerSteepestDescent< S, C >.

Here is the caller graph for this function:

◆ noCondition()

template<typename S , typename C >

bool olb::opti::OptimizerLineSearch< S, C >::noCondition ( const S & tempValue )

inline

Definition at line 196 of file optimizerLineSearch.h.

  {
    return true;
  }

◆ optimizationStep()

template<typename S , typename C >

virtual void olb::opti::OptimizerLineSearch< S, C >::optimizationStep ( )

inlinevirtual

Optimization step: line search.

Implements olb::opti::Optimizer< S, C >.

Definition at line 336 of file optimizerLineSearch.h.

  {
    // Compute search direction
    if (this->_verboseOn) {
      clout << "Computing directions..." << std::endl;
    }
 
    // Use given optimization algorithm to get direction:
    // Steepest Descent, LBFGS or Barzilai-Borwein
    computeDirection();
 
    _upperBoundFlag = false;
    _lowerBoundFlag = false;
    checkBound();
 
    // save initial control
    const C initialControl = this->_control;
 
    // Search along line to find new control
    for (int iDim=0; iDim<this->_dimCtrl; iDim++) {
      this->_control[iDim] -= this->_lambda*_direction[iDim];
    }
 
    if (this->_withUpperBound||this->_withLowerBound) {
      boundControl();
      checkBound();
    }
 
    if (this->_verboseOn) {
      clout << "[Step " << this->_it << "] <<<<<<<<<< lambda=" << this->_lambda << " <<<<<<<<<<" << std::endl;
    }
 
    S tempValue = S();
    if (this->_withUpperBound||this->_withLowerBound) {
      this->evaluateObjective(this->_boundedControl, tempValue);
    }
    else {
      this->evaluateObjective(this->_control, tempValue);
    }
 
    // Backtracking line search with step condition
    backtrackingLineSearch(tempValue, this->_lambda, _stepConditionFunction);
 
    if (this->_withUpperBound||this->_withLowerBound) {
      if (this->_verboseOn) {
        clout << "Bounding control" << std::endl;
      }
      for (int iDim=0; iDim<this->_dimCtrl; iDim++) {
        this->_control[iDim] = this->_boundedControl[iDim];
      }
    }
 
    // Update value of the objective functional
    this->_value = tempValue;
    // Update step no.
    this->_it++;
 
    // check if control have changed sufficiently or break from optimisation
    this->_controlsConverged = true;
    for (int iDim=0; iDim<this->_dimCtrl; ++iDim) {
      S ave = 0.5 * (initialControl[iDim] + this->_control[iDim]);
      if (util::abs(ave) > 0) {
        if (util::abs( (initialControl[iDim] - this->_control[iDim]) / ave) >= this->_controlEps) {
          this->_controlsConverged = false;
          break;
        }
      }  // else control diff is zero anyway
    }
    if (this->_verboseOn) {
      clout << "Controls converged within " << this->_controlEps << ": " << ((this->_controlsConverged) ? "true" : "false") << std::endl;
    }
  };

Here is the call graph for this function:

◆ quadraticInterpolationStep()

template<typename S , typename C >

void olb::opti::OptimizerLineSearch< S, C >::quadraticInterpolationStep ( const S & tempValue )

inline

Definition at line 253 of file optimizerLineSearch.h.

  {
    S newLambda = S();
    S dir = S();
    if (std::isnan(tempValue) ) {
      newLambda = this->_lambda/2.;
    }
    else {
      for (int iDim=0; iDim<this->_dimCtrl; iDim++) {
        dir += this->_derivative[iDim]*this->_direction[iDim];
      }
      newLambda = dir*this->_lambda*this->_lambda / (2.*(tempValue - this->_value + dir*this->_lambda));
      // Step size control
      if (newLambda < this->_lambda*.1 ) {
        newLambda = this->_lambda*.1;
      }
      if (newLambda > this->_lambda*.5 ) {
        newLambda = this->_lambda*.5;
      }
    }
    this->_lambda = newLambda;
  }

References olb::opti::Optimizer< S, C >::_derivative, olb::opti::Optimizer< S, C >::_dimCtrl, olb::opti::OptimizerLineSearch< S, C >::_lambda, and olb::opti::Optimizer< S, C >::_value.

◆ smallerValue()

template<typename S , typename C >

bool olb::opti::OptimizerLineSearch< S, C >::smallerValue ( const S & tempValue )

inline

Definition at line 185 of file optimizerLineSearch.h.

  {
    if (!(tempValue > this->_value || std::isnan(tempValue))) {
      return true;
    }
    else {
      (this->*_stepLengthFunction)(tempValue);
      return false;
    }
  }

References olb::opti::OptimizerLineSearch< S, C >::_stepLengthFunction, and olb::opti::Optimizer< S, C >::_value.

Member Data Documentation

◆ _direction

template<typename S , typename C >

C olb::opti::OptimizerLineSearch< S, C >::_direction

protected

Search direction.

Definition at line 60 of file optimizerLineSearch.h.

◆ _lambda

template<typename S , typename C >

S olb::opti::OptimizerLineSearch< S, C >::_lambda

protected

Lambda start value.

Definition at line 58 of file optimizerLineSearch.h.

◆ _lowerBoundFlag

template<typename S , typename C >

bool olb::opti::OptimizerLineSearch< S, C >::_lowerBoundFlag

protected

Definition at line 62 of file optimizerLineSearch.h.

◆ _maxStepAttempts

template<typename S , typename C >

int olb::opti::OptimizerLineSearch< S, C >::_maxStepAttempts

protected

Maximal number of step attempts for conditioned line search.

Definition at line 65 of file optimizerLineSearch.h.

◆ _nextDerivative

template<typename S , typename C >

C olb::opti::OptimizerLineSearch< S, C >::_nextDerivative

protected

Definition at line 67 of file optimizerLineSearch.h.

◆ _nextDerivFlag

template<typename S , typename C >

bool olb::opti::OptimizerLineSearch< S, C >::_nextDerivFlag

protected

Definition at line 68 of file optimizerLineSearch.h.

◆ _stepCondition

template<typename S , typename C >

std::string olb::opti::OptimizerLineSearch< S, C >::_stepCondition

protected

Definition at line 71 of file optimizerLineSearch.h.

◆ _stepConditionFunction

template<typename S , typename C >

bool(OptimizerLineSearch::* olb::opti::OptimizerLineSearch< S, C >::_stepConditionFunction) (const S &)

protected

Definition at line 72 of file optimizerLineSearch.h.

◆ _stepLengthFunction

template<typename S , typename C >

void(OptimizerLineSearch::* olb::opti::OptimizerLineSearch< S, C >::_stepLengthFunction) (const S &)

protected

Definition at line 73 of file optimizerLineSearch.h.

◆ _upperBoundFlag

template<typename S , typename C >

bool olb::opti::OptimizerLineSearch< S, C >::_upperBoundFlag

protected

Definition at line 63 of file optimizerLineSearch.h.

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

src/optimization/optimizerLineSearch.h

Public Member Functions

Protected Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ OptimizerLineSearch()

◆ ~OptimizerLineSearch()

Member Function Documentation

◆ armijoWolfeConditions()

◆ backtrackingLineSearch()

◆ boundControl()

◆ checkBound()

◆ computeDirection()

◆ noCondition()

◆ optimizationStep()

◆ quadraticInterpolationStep()

◆ smallerValue()

Member Data Documentation

◆ _direction

◆ _lambda

◆ _lowerBoundFlag

◆ _maxStepAttempts

◆ _nextDerivative

◆ _nextDerivFlag

◆ _stepCondition

◆ _stepConditionFunction

◆ _stepLengthFunction

◆ _upperBoundFlag