| 1 : |
agomez |
1 |
#ifndef paraminbfgs_h
|
| 2 : |
|
|
#define paraminbfgs_h
|
| 3 : |
|
|
|
| 4 : |
|
|
#include "paraminsearch.h" |
| 5 : |
|
|
#include "doublematrix.h"
|
| 6 : |
|
|
/**
|
| 7 : |
|
|
* \class ParaminBFGS
|
| 8 : |
|
|
* \brief BFGS
|
| 9 : |
|
|
*
|
| 10 : |
|
|
* ABSTRACT:
|
| 11 : |
|
|
* The BFGS-method is a gradient iterative method that work as follows: We start at some point and successively generate new points, so that the function value decreases in each iteration. This is done by choosing a direction that makes an angle greater than 90 degrees with the gradient of the function.
|
| 12 : |
|
|
*
|
| 13 : |
|
|
* Authors
|
| 14 : |
|
|
* Gunnar Stefansson
|
| 15 : |
|
|
* Kristjana Yr Jonsdottir
|
| 16 : |
|
|
* Thordis Linda Thorarinsdottir
|
| 17 : |
|
|
*
|
| 18 : |
|
|
* The BFGS-method is one of the Quasi-Newton methods. Quasi-Newton methods are iterative methods which approximate Newton's method without calculating second derivatives. They are of the form
|
| 19 : |
|
|
* x^k+1 = x^k + a^k * d^k,
|
| 20 : |
|
|
* d^k = -D^k \nabla f( x^k ),
|
| 21 : |
|
|
* where D^k is a positive definite matrix, updated using the BFGS updating formula. To find the value of a, an inexact linesearch called the Armijo rule is used. That method finds an a such that Armijo condition is satiefied, which is based on getting a function value that is some amount better than the best know function value. This is done by trying at first an initial stepsize an than reducing the stepsize until a value that satisfies the Armijo condition is found. For details, see D.P. Bertsekas, "Nonlinear Programming", Athena Scientific, Belmont, 1999. As the objective function is not necessarily differentiable, the gradient is calculted numerically.
|
| 22 : |
|
|
*/
|
| 23 : |
|
|
class ParaminBFGS : public ParaminSearch {
|
| 24 : |
|
|
private:
|
| 25 : |
|
|
/**
|
| 26 : |
|
|
* \brief This object handles the linesearch
|
| 27 : |
|
|
*/
|
| 28 : |
|
|
Armijo* lineS;
|
| 29 : |
|
|
/**
|
| 30 : |
|
|
* \brief This object computes the gradient at x
|
| 31 : |
|
|
*/
|
| 32 : |
|
|
NetGradient* grad;
|
| 33 : |
|
|
/**
|
| 34 : |
|
|
* \brief iteration number
|
| 35 : |
|
|
*/
|
| 36 : |
|
|
// int iter;
|
| 37 : |
|
|
/**
|
| 38 : |
|
|
* \brief stores the diagonal entry of the hessian matrix.
|
| 39 : |
|
|
*/
|
| 40 : |
|
|
DoubleVector diaghess;
|
| 41 : |
|
|
/**
|
| 42 : |
|
|
* \brief stores the inverse hessian matrix.
|
| 43 : |
|
|
*/
|
| 44 : |
|
|
// double** invhess;
|
| 45 : |
|
|
DoubleMatrix invhess;
|
| 46 : |
|
|
/**
|
| 47 : |
|
|
* \brief stores the gradient at xi
|
| 48 : |
|
|
*/
|
| 49 : |
|
|
DoubleVector gi;
|
| 50 : |
|
|
/**
|
| 51 : |
|
|
* \brief stores the gradient at xi-1
|
| 52 : |
|
|
*/
|
| 53 : |
|
|
DoubleVector gim1;
|
| 54 : |
|
|
/**
|
| 55 : |
|
|
* \brief direction vector used in line minimization.
|
| 56 : |
|
|
*/
|
| 57 : |
|
|
DoubleVector h;
|
| 58 : |
|
|
/**
|
| 59 : |
|
|
* \brief derivative used in line minimization.
|
| 60 : |
|
|
*/
|
| 61 : |
|
|
double dery;
|
| 62 : |
|
|
/**
|
| 63 : |
|
|
* \brief difference between current bestx and the one before
|
| 64 : |
|
|
*/
|
| 65 : |
|
|
DoubleVector deltax;
|
| 66 : |
|
|
/**
|
| 67 : |
|
|
* \brief norm of x
|
| 68 : |
|
|
*/
|
| 69 : |
|
|
double normx;
|
| 70 : |
|
|
/**
|
| 71 : |
|
|
* \brief norm of h (search direction)
|
| 72 : |
|
|
*/
|
| 73 : |
|
|
double normh;
|
| 74 : |
|
|
/**
|
| 75 : |
|
|
* \brief norm of the gradient
|
| 76 : |
|
|
*/
|
| 77 : |
|
|
double normgrad;
|
| 78 : |
|
|
/**
|
| 79 : |
|
|
* \brief norm of deltax
|
| 80 : |
|
|
*/
|
| 81 : |
|
|
double normdeltax;
|
| 82 : |
|
|
int get;
|
| 83 : |
|
|
/**
|
| 84 : |
|
|
* \brief an indicator of how many points are needed for the gradient calculations
|
| 85 : |
|
|
*/
|
| 86 : |
|
|
int difficultgrad;
|
| 87 : |
|
|
int armijoproblem;
|
| 88 : |
|
|
int initial_difficultgrad;
|
| 89 : |
|
|
int to_print;
|
| 90 : |
|
|
double s;
|
| 91 : |
|
|
/**
|
| 92 : |
|
|
* \brief if Shannon scaling is to be used
|
| 93 : |
|
|
*/
|
| 94 : |
|
|
int shannonScaling;
|
| 95 : |
|
|
// DoubleVector xopt;
|
| 96 : |
|
|
int bfgs_constant;
|
| 97 : |
|
|
double errortol;
|
| 98 : |
|
|
double xtol;
|
| 99 : |
|
|
int maxrounds; // There is a diff between bfgs.maxiter and maxronds
|
| 100 : |
|
|
int bfgsFail;
|
| 101 : |
|
|
double error;
|
| 102 : |
|
|
// AJ adding for testing
|
| 103 : |
|
|
int computedGrad;
|
| 104 : |
|
|
|
| 105 : |
|
|
public:
|
| 106 : |
|
|
/**
|
| 107 : |
|
|
* \brief the default constructor
|
| 108 : |
|
|
* \param netInt is a NetInterface to initialise ParaminSearch
|
| 109 : |
|
|
*/
|
| 110 : |
|
|
ParaminBFGS(NetInterface* netInt);
|
| 111 : |
|
|
/**
|
| 112 : |
|
|
* \brief The default destructor
|
| 113 : |
|
|
*/
|
| 114 : |
|
|
virtual ~ParaminBFGS();
|
| 115 : |
|
|
/**
|
| 116 : |
|
|
* \brief The BFGS file reader
|
| 117 : |
|
|
* \param infile is the CommentStream to read the optimisation parameters from
|
| 118 : |
|
|
* \param text is the latest entry from infile
|
| 119 : |
|
|
*/
|
| 120 : |
|
|
void read(CommentStream& infile, char* text);
|
| 121 : |
|
|
/**
|
| 122 : |
|
|
* \brief Does a BFGS search
|
| 123 : |
|
|
* \param startx is the starting point of the BFGS
|
| 124 : |
|
|
* \param startf is the f-value at startx
|
| 125 : |
|
|
*/
|
| 126 : |
|
|
// void doSearch(const DoubleVector& startx, double startf);
|
| 127 : |
|
|
void OptimiseLikelihood();
|
| 128 : |
|
|
/**
|
| 129 : |
|
|
* \brief Computes the gradient at x
|
| 130 : |
|
|
*/
|
| 131 : |
|
|
void ComputeGradient();
|
| 132 : |
|
|
void doLineseek();
|
| 133 : |
|
|
void iteration();
|
| 134 : |
|
|
void SetInitialValues();
|
| 135 : |
|
|
void UpdateValues();
|
| 136 : |
|
|
void ScaleDirectionVector();
|
| 137 : |
|
|
void ComputeDirectionVector();
|
| 138 : |
|
|
void DefineHessian();
|
| 139 : |
|
|
void UpdateXandGrad();
|
| 140 : |
|
|
int bfgsUpdate();
|
| 141 : |
|
|
double norm();
|
| 142 : |
|
|
void printGradient();
|
| 143 : |
|
|
void printInverseHessian();
|
| 144 : |
|
|
double GetS(int get);
|
| 145 : |
|
|
void Print(ofstream& outfile, int prec);
|
| 146 : |
|
|
// About termination criteria:
|
| 147 : |
|
|
// bfgsfail = -1 iff minimization will be continued.
|
| 148 : |
|
|
// bfgsfail = 0 iff error <= errortol
|
| 149 : |
|
|
// bfgsfail = 1 iff alpha < 0.
|
| 150 : |
|
|
// bfgsfail = 2 iff normdeltax < xtol.
|
| 151 : |
|
|
// bfgsfail = 4 iff dery > 0.
|
| 152 : |
|
|
// bfgsfail = 5 iff there's a instability error.
|
| 153 : |
|
|
// bfgsfail = 6 iff you couldn't get alpha from linesearch (alpha = 0).
|
| 154 : |
|
|
// bfgsfail = -2 iff you couldn get alpha from linesearch and you want to increase difficultgrad
|
| 155 : |
|
|
};
|
| 156 : |
|
|
|
| 157 : |
|
|
#endif
|
Parent Directory
Revision Log