Logo ROOT  
Reference Guide
NegativeG2LineSearch.cxx
Go to the documentation of this file.
1 // @(#)root/minuit2:$Id$
2 // Authors: M. Winkler, F. James, L. Moneta, A. Zsenei 2003-2005
3 
4 /**********************************************************************
5  * *
6  * Copyright (c) 2005 LCG ROOT Math team, CERN/PH-SFT *
7  * *
8  **********************************************************************/
9 
11 #include "Minuit2/MnFcn.h"
12 #include "Minuit2/MinimumState.h"
15 #include "Minuit2/MnLineSearch.h"
18 #include "Minuit2/MnPrint.h"
19 
20 #include <cmath>
21 
22 namespace ROOT {
23 
24 namespace Minuit2 {
25 
27 operator()(const MnFcn &fcn, const MinimumState &st, const GradientCalculator &gc, const MnMachinePrecision &prec) const
28 {
29 
30  // when the second derivatives are negative perform a line search along Parameter which gives
31  // negative second derivative and magnitude equal to the Gradient step size.
32  // Recalculate the gradients for all the Parameter after the correction and
33  // continue iteration in case the second derivatives are still negative
34  //
35  MnPrint print("NegativeG2LineSearch");
36 
37  bool negG2 = HasNegativeG2(st.Gradient(), prec);
38  if (!negG2)
39  return st;
40 
41  unsigned int n = st.Parameters().Vec().size();
42  FunctionGradient dgrad = st.Gradient();
43  MinimumParameters pa = st.Parameters();
44  bool iterate = false;
45  unsigned int iter = 0;
46  do {
47  iterate = false;
48  for (unsigned int i = 0; i < n; i++) {
49 
50  print.Debug("negative G2 - iter", iter, "param", i, pa.Vec()(i), "grad2", dgrad.G2()(i), "grad",
51  dgrad.Vec()(i), "grad step", dgrad.Gstep()(i), "step size", pa.Dirin()(i));
52 
53  if (dgrad.G2()(i) <= 0) {
54 
55  // check also the gradient (if it is zero ) I can skip the param)
56 
57  if (std::fabs(dgrad.Vec()(i)) < prec.Eps() && std::fabs(dgrad.G2()(i)) < prec.Eps())
58  continue;
59  // if(dgrad.G2()(i) < prec.Eps()) {
60  // do line search if second derivative negative
61  MnAlgebraicVector step(n);
62  MnLineSearch lsearch;
63 
64  if (dgrad.Vec()(i) < 0)
65  step(i) = dgrad.Gstep()(i); //*dgrad.Vec()(i);
66  else
67  step(i) = -dgrad.Gstep()(i); // *dgrad.Vec()(i);
68 
69  double gdel = step(i) * dgrad.Vec()(i);
70 
71  // if using sec derivative information
72  // double g2del = step(i)*step(i) * dgrad.G2()(i);
73 
74  print.Debug("step(i)", step(i), "gdel", gdel);
75  // std::cout << " g2del " << g2del << std::endl;
76 
77  MnParabolaPoint pp = lsearch(fcn, pa, step, gdel, prec);
78 
79  print.Debug("Line search result", pp.X(), "f(0)", pa.Fval(), "f(1)", pp.Y());
80 
81  step *= pp.X();
82  pa = MinimumParameters(pa.Vec() + step, pp.Y());
83 
84  dgrad = gc(pa, dgrad);
85 
86  print.Debug("Line search - iter", iter, "param", i, pa.Vec()(i), "step", step(i), "new grad2",
87  dgrad.G2()(i), "new grad", dgrad.Vec()(i), "grad step", dgrad.Gstep()(i));
88 
89  iterate = true;
90  break;
91  }
92  }
93  } while (iter++ < 2 * n && iterate);
94 
96  for (unsigned int i = 0; i < n; i++)
97  mat(i, i) = (std::fabs(dgrad.G2()(i)) > prec.Eps2() ? 1. / dgrad.G2()(i) : 1.);
98 
99  MinimumError err(mat, 1.);
100  double edm = VariableMetricEDMEstimator().Estimate(dgrad, err);
101 
102  if (edm < 0) {
104  }
105 
106  return MinimumState(pa, err, dgrad, edm, fcn.NumOfCalls());
107 }
108 
110 {
111  // check if function gradient has any component which is neegative
112 
113  for (unsigned int i = 0; i < grad.Vec().size(); i++)
114 
115  if (grad.G2()(i) <= 0) {
116 
117  return true;
118  }
119 
120  return false;
121 }
122 
123 } // namespace Minuit2
124 
125 } // namespace ROOT
ROOT::Minuit2::MnParabolaPoint
A point of a parabola.
Definition: MnParabolaPoint.h:36
ROOT::Minuit2::MnMachinePrecision::Eps2
double Eps2() const
eps2 returns 2*sqrt(eps)
Definition: MnMachinePrecision.h:41
n
const Int_t n
Definition: legend1.C:16
ROOT::Minuit2::MnFcn
Wrapper class to FCNBase interface used internally by Minuit.
Definition: MnFcn.h:30
GradientCalculator.h
ROOT::Minuit2::MnFcn::NumOfCalls
unsigned int NumOfCalls() const
Definition: MnFcn.h:39
VariableMetricEDMEstimator.h
ROOT::Minuit2::MinimumState
MinimumState keeps the information (position, Gradient, 2nd deriv, etc) after one minimization step (...
Definition: MinimumState.h:29
MnMachinePrecision.h
ROOT::Minuit2::LAVector
Definition: LAVector.h:32
ROOT::Minuit2::MnPrint::Debug
void Debug(const Ts &... args)
Definition: MnPrint.h:138
ROOT::Minuit2::MinimumState::Gradient
const FunctionGradient & Gradient() const
Definition: MinimumState.h:55
ROOT::Minuit2::LASymMatrix
Class describing a symmetric matrix of size n.
Definition: LASymMatrix.h:45
ROOT::Minuit2::MinimumParameters::Vec
const MnAlgebraicVector & Vec() const
Definition: MinimumParameters.h:38
ROOT::Minuit2::VariableMetricEDMEstimator
Definition: VariableMetricEDMEstimator.h:20
ROOT::Minuit2::FunctionGradient::Vec
const MnAlgebraicVector & Vec() const
Definition: FunctionGradient.h:41
ROOT::Minuit2::FunctionGradient
Definition: FunctionGradient.h:21
ROOT::Minuit2::BasicMinimumError::MnNotPosDef
Definition: BasicMinimumError.h:33
MnFcn.h
ROOT::Minuit2::FunctionGradient::G2
const MnAlgebraicVector & G2() const
Definition: FunctionGradient.h:45
ROOT::Minuit2::MinimumParameters::Fval
double Fval() const
Definition: MinimumParameters.h:40
ROOT::Minuit2::MnMachinePrecision::Eps
double Eps() const
eps returns the smallest possible number so that 1.+eps > 1.
Definition: MnMachinePrecision.h:38
NegativeG2LineSearch.h
MnParabolaPoint.h
ROOT::Minuit2::NegativeG2LineSearch::operator()
MinimumState operator()(const MnFcn &, const MinimumState &, const GradientCalculator &, const MnMachinePrecision &) const
Definition: NegativeG2LineSearch.cxx:27
ROOT::Math::fabs
VecExpr< UnaryOp< Fabs< T >, VecExpr< A, T, D >, T >, T, D > fabs(const VecExpr< A, T, D > &rhs)
Definition: UnaryOperators.h:131
ROOT::Minuit2::MinimumParameters
Definition: MinimumParameters.h:21
size
size_t size(const MatrixT &matrix)
retrieve the size of a square matrix
ROOT::Minuit2::NegativeG2LineSearch::HasNegativeG2
bool HasNegativeG2(const FunctionGradient &, const MnMachinePrecision &) const
Definition: NegativeG2LineSearch.cxx:109
ROOT::Minuit2::MnMachinePrecision
Sets the relative floating point (double) arithmetic precision.
Definition: MnMachinePrecision.h:32
ROOT::Minuit2::MinimumParameters::Dirin
const MnAlgebraicVector & Dirin() const
Definition: MinimumParameters.h:39
ROOT::Minuit2::VariableMetricEDMEstimator::Estimate
double Estimate(const FunctionGradient &, const MinimumError &) const
Definition: VariableMetricEDMEstimator.cxx:20
ROOT::Minuit2::FunctionGradient::Gstep
const MnAlgebraicVector & Gstep() const
Definition: FunctionGradient.h:46
ROOT::Minuit2::MnLineSearch
Implements a 1-dimensional minimization along a given direction (i.e.
Definition: MnLineSearch.h:40
ROOT::Minuit2::MnParabolaPoint::Y
double Y() const
Accessor to the y (second) coordinate.
Definition: MnParabolaPoint.h:70
ROOT::Minuit2::LAVector::size
unsigned int size() const
Definition: LAVector.h:227
ROOT::Minuit2::MinimumError
MinimumError keeps the inv.
Definition: MinimumError.h:26
ROOT::Minuit2::MinimumState::Parameters
const MinimumParameters & Parameters() const
Definition: MinimumState.h:50
MnLineSearch.h
ROOT::Minuit2::MnParabolaPoint::X
double X() const
Accessor to the x (first) coordinate.
Definition: MnParabolaPoint.h:60
MnPrint.h
ROOT::Minuit2::GradientCalculator
interface class for gradient calculators
Definition: GradientCalculator.h:23
iterate
int iterate(rng_state_t *X)
Definition: mixmax.icc:34
ROOT
tbb::task_arena is an alias of tbb::interface7::task_arena, which doesn't allow to forward declare tb...
Definition: EExecutionPolicy.hxx:4
MinimumState.h
ROOT::Minuit2::MnPrint
Definition: MnPrint.h:73