/////////////////////////////////////////////////////////////////////////////
//
// Headerfile for the optimization base classes
//
// Copyright © 2000
//
// IMM, Department of Mathematical Modelling
// Technical University of Denmark, Building 321
// DK-2800 Lyngby, Denmark
// http://www.imm.dtu.dk/~diva
//
// author: Rune Fisker 
//
// Disclaimer:
//
// No guarantees of performance accompany this software,
// nor is any responsibility assumed on the part of the author(s).
// The software has been tested extensively and every effort has been
// made to insure its reliability.
//
// This software is provided by IMM and the contributor(s) ``as is'' and
// any express or implied warranties, including, but not limited to, the
// implied warranties of merchantability and fitness for a particular purpose
// are disclaimed.  In no event shall IMM or the contributor(s) be liable
// for any direct, indirect, incidental, special, exemplary, or consequential
// damages (including, but not limited to, procurement of substitute goods
// or services; loss of use, data, or profits; or business interruption)
// however caused and on any theory of liability, whether in contract, strict
// liability, or tort (including negligence or otherwise) arising in any way
// out of the use of this software, even if advised of the possibility of
// such damage.
//
// This software is partly based on the Microsoft Vision Software Developers 
// Kit VisSDK and CLAPACK.
//
/////////////////////////////////////////////////////////////////////////////

#if !defined(CD_OPTIMIZE_BASE)
#define CD_OPTIMIZE_BASE

#ifndef DIVAOptExport
#define DIVAOptExport __declspec(dllimport)
#define EXPIMP extern
#endif // DIVAOptExport

#include "DMatrix.h"
#include <vector>


/*

  DLL issues:

  http://support.microsoft.com/support/kb/articles/Q168/9/58.ASP

*/

//disable warnings on extern before template instantiation
#pragma warning (disable : 4231)
#pragma warning (disable : 4091)

class CDVector;
// EXPIMP class DIVAOptExport CDVector;
// EXPIMP template class DIVAOptExport std::vector<CDVector>;




/////////////////////////////////////////////////////////////////////////////////
//
//							Function Evaluation Base Class
//
//	This abstract class is used to interface between the optimization class/functions 
//	and the classes, which contains the problem to be optimized (see Rosenbrock test example  
//	in the bottom of this file)
//
//	author: Rune Fisker, 28/5-1999
//
/////////////////////////////////////////////////////////////////////////////////

class DIVAOptExport CDOptimizeFuncBase
{
public:

	// evaluates the function value at postion vX
	virtual double EvalFunction(CDVector& vX) = 0;

	// evaluates the analytic gradient at postion vX (if exists)
	virtual void EvalGradient(CDVector& vX, CDVector& vGradient) { throw("Analytic gradient not defined"); }

	// function used to update e.g. interface
	virtual void Update(CDVector& vX) {};
};

// methods for estimating the gradient nummericaly
DIVAOptExport enum ENumGrad 
{ 
	ForwardDifference, 
	CentralDifference, 
	FitLine 
};

// optimization methods
DIVAOptExport enum EOptMethod
{
	eoptUnknown				= 0,
	eoptSteepestDescent		= 1,
	eoptConjugateGradient	= 2,
	eoptBFGS				= 3,
	eoptSimulatedAnnealing	= 4,
	eoptPatternSearch		= 5
};

// termination code
DIVAOptExport enum ETermCode
{
	etermNoStop				= 0,	// no stop
	etermGradTol			= 1,	// abs max gradient defined as max_i( abs( g[i]*xplus[i]/f(xplus) )) < m_dGradTol
	etermStepTol			= 2,	// step tolerance defined as max_i( abs( (xplus[i] - x[i])/xplus[i] )) < m_dStepTol
	etermLineSearch			= 4,	// termination from line search
	etermConsecMaxStepMax	= 8,	// max number of conseccutive past steps whose scaled length was equal to maxstep
	etermDeltaFuncVal		= 16,	// change in function value defined as (abs(f - fplus) < m_dDeltaFuncVal)
	etermMaxFuncEval		= 32,	// max number of function evaluations
	etermMaxIterations		= 64,	// max iterations
	etermUnknown			= 128	// unknow stop
};

/////////////////////////////////////////////////////////////////////////////////
//
//							Optimization base class
//
//	This abstract class is the base class for all classes implementing specific
//	optimization  procedures.
//
//	author: Rune Fisker, 26/1-1999
//
/////////////////////////////////////////////////////////////////////////////////
class DIVAOptExport CDOptimizeBase
{

public:
	// constructor/destructor
	CDOptimizeBase();
	~CDOptimizeBase(){};

	// the Minimize function using analytic gradient
	virtual ETermCode Minimize(CDVector& x,CDOptimizeFuncBase* pFuncEvalBase) = 0; 

	// the Minimize function using nummerical gradient
	virtual ETermCode MinimizeNum(CDVector& x,CDOptimizeFuncBase* pFuncEvalBase ,CDVector& vMethodPar); 

	// name of optimization methode
	virtual CString Name() {return "Unknown method";}
	virtual EOptMethod OptMethod() {return eoptUnknown;}

	// function and gradient evaluation methods
	double EvalFunction(CDVector& x) { assert(m_pFuncEvalBase); m_nFuncEval++; return m_pFuncEvalBase->EvalFunction(x);}
	void EvalGradient(CDVector& x, CDVector& gc, const double dFuncVal) { assert(m_pFuncEvalBase); if (m_fAnalyticGrad) m_pFuncEvalBase->EvalGradient(x,gc); else NumGrad(x,gc,dFuncVal); m_nGradEval++;}

	// line search algorithms
	int LineSearch(const CDVector& xc, const double fc, const CDVector& g, const CDVector& p,CDVector& xplus, double& fplus, bool& maxtaken, bool fSoft = true);

	// nummerical gradient function
	virtual void NumGrad(CDVector& x, CDVector& gradient, const double dFuncVal);
	CDVector& MethodPar() {return m_vMethodPar;}
	void SetMethodPar(const CDVector& vMethodPar) { m_vMethodPar = vMethodPar; } 

	// stopping functions 
	ETermCode UmStop0(CDVector& x0, const double functionValue, CDVector& gradient);
	ETermCode UmStop(const CDVector& x,const CDVector& xplus,const double f, const double fplus,const CDVector& g, const int retcode, const bool maxtaken);

	// other functions	
	void SetMachineEps();

	// set/get limit for the number of iterations
	void SetMaxIterations(const int nMaxIterations); 
	int MaxIterations() const { return m_nMaxIterations;} 

	// set/get limit for the number of function evaluations
	void SetMaxFuncEval(const int nMaxFuncEval); 
	int MaxFuncEval() const { return m_nMaxFuncEval;} 
	
	// set/get point to func eval. base.
	void SetFuncEvalBase(CDOptimizeFuncBase* pFuncEval) {m_pFuncEvalBase = pFuncEval;}
	CDOptimizeFuncBase* SetFuncEvalBase() const { return m_pFuncEvalBase;}

	// Machine precision 
	double	m_dMachEps;    

	// positive scalar estimating the magnitude of f(x) near he minimizer x-star. 
	// It is only used in the gradient stopping condition given below. typf should be
	// approximately |f(x*)|
	double	m_dTypF; 

	/* A positive integer specifying the number of reliable
	digits returned by the objective function FN.
	fdigits is used to set the parameter n (eta) that
	is used in the code to specify the relative noise
	in f(x); the main use of eta is in calculation
	finite difference step size. eta is set to macheps
	if fdigits = -1. If f(x) is suspected to be noisy
	but the approximate value of fdigits is unknown,
	it should be estimated be the routine of
	Hamming[1973] given in Gill, Murray and Wright[1981] */
	int	m_nFDigits;
	
	/* A positive scalar giving the maximum allowable
	scaled steplength at any iteration. maxstep is
	used to prevent steps that would cause the
	optimazation algorithm to overflow or leave the
	domain of interest, as well as to detect divergence.
	It should be chosen small enough to prevent the first
	two of these occurrences but larger than any
	anticipated reasonable stepsize. The algorithm will
	halt if it takes steps of length maxstep on m_nConsecMaxStepMax
	conseccutive iterations  */
	double	m_dMaxStep;   

	// Number of conseccutive past steps whose scaled length was equal to maxstep
	int	m_nConsecMax;  
		
	// ?
	double	m_dEta ;       
	
	// flag indicating if the gradient is to be calc. analyticaly or nummericaly
	bool m_fAnalyticGrad;

	// methods for estimating the gradient nummericaly
	ENumGrad m_eNumGrad;

	////////////////////////////// public stop criteria pars. ///////////////

	// holds the stop criteria in use, e.g m_iStopCriteria = 
	// etermMaxFuncEval | etermMaxIterations
	int m_iStopCriteria;
		
	// A positive scalar giving the tolerance at which the
	// scaled gradient in considered close enough to zero
	// to terminate the algorithme
	double	m_dGradTol;
	
	// A positive scalar giving the tolerance at which
	// the scaled distance between two successive iterated
	// is considered close enough to zero to terminate
	// the algorithm 
	double	m_dStepTol;

	// max number of conseccutive past steps whose scaled 
	// length was equal to maxstep to terminate
	int	m_nConsecMaxStepMax;  

	// value for stop criterion: abs(f - fplus) < m_dDeltaFuncVal
	double m_dDeltaFuncVal;

	////////////////////////////// logged function value pars. ///////////////

	// counter to the number of iterations
	int	m_nIterations;   
	
	// counter to the number of function evaluations
	int m_nFuncEval;

	// counter to the number of gradient evaluations
	int m_nGradEval;

	// Logical variable which determines whether function 
	// parameters and corresponding return values should
	// be stored for later analysis.
	bool m_fLogFuncValues;

	// vectors for saving the FuncVal, parameter values and 
	// the corresponding number of func evaluations 
	CDVector m_vFuncVal;
	CDVector m_vNFuncEval;
	std::vector<CDVector> m_vvFuncParm;

	////////////////////////////// private functions ///////////////

private:
	
	// line search algorithms
	int SoftLineSearch(const CDVector& xc, const double fc, const CDVector& g, const CDVector& sn,CDVector& xplus, double& fplus, bool& maxtaken);
	int ExactLineSearch(const CDVector& xc, const double fc, const CDVector& g, const CDVector& p,CDVector& xplus, double& fplus, bool& maxtaken);

	// pointer to the function to be minimized
	CDOptimizeFuncBase* m_pFuncEvalBase;

	// special parameters used by each optimization method
	// e.g. step size used for calc. nummerical gradient
	CDVector m_vMethodPar;

	////////////////////////////// public stop criteria pars. ///////////////

	// A positive integer specifying the maximum number
	// of iterations that may be performed before the
	// algorithme is halted. Appropriate values depend
	// strongly on the dimension and difficulty of the
	// problem, and the cost of evaluating the nonlinear function
	int	m_nMaxIterations;   

	// limit for number of function evaluations
	int m_nMaxFuncEval;

};


#endif // CD_OPTIMIZE_BASE