Exercise "Minimization"

1. (6 points) Quasi-Newton method with numerical gradient, back-tracking linesearch, and rank-1 update

   Implement the quasi-Newton minimization method with numerical gradient, back-tracking linesearch, and a rank-1 update.

   The interface to the function could be like this,

   void qnewton(
   	double F(vector* x), /* objective function */
   	vector* x, /* on input: starting point, on exit: approximation to root */
   	double eps /* accuracy goal, on exit |gradient| should be <eps */
   )
   

   Start with the unity inverse Hessian matrix and then apply the updates. If the update diverges, or minimial step-size is reached, reset the inverse Hessian matrix to unity and continue.

   Find a minimum of the Rosenbrock's valley function, f(x,y)=(1-x)2+100(y-x2)2.

   Find a minimum of the Himmelblau's function, f(x,y)=(x2+y-11)2+(x+y2-7)2.

   Record the number of steps it takes for the algorithm to reach the minimum.

2. (3 points) Higgs discovery

   In 2012 CERN announced the discovery of a previously unknown boson with mass 125.3±0.6 GeV/c² [Wikipedia].

   In one of the experiments a certain cross-section involving Higgs was measured and the data with subtracted noise (that's why some data are negative) is given as [arxiv:1207.7235]

   # c.m. energy E[GeV], cross-section σ(E)[certain units], error δσ [same units]
   101 -0.25 2.0
   103 -0.30 2.0
   105 -0.15 1.9
   107 -1.71 1.9
   109  0.81 1.9
   111  0.65 1.9
   113 -0.91 1.9
   115  0.91 1.9
   117  0.96 1.6
   119 -2.52 1.6
   121 -1.01 1.6
   123  2.01 1.6
   125  4.83 1.6
   127  4.58 1.6
   129  1.26 1.3
   131  1.01 1.3
   133 -1.26 1.3
   135  0.45 1.3
   137  0.15 1.3
   139 -0.91 1.3
   141 -0.81 1.1
   143 -1.41 1.1
   145  1.36 1.1
   147  0.50 1.1
   149 -0.45 1.1
   151  1.61 1.1
   153 -2.21 1.1
   155 -1.86 0.9
   157  1.76 0.9
   159 -0.50 0.9
   

   Fit the Breit-Wigner function

   F(E|m,Γ,A)=A/((E-m)²+Γ²/4)
   

   (where A is a scale-factor, m is the mass and Γ is the widths of the sought resonance) to the data and determine the mass and the width of the Higgs boson.

   You fit the data by minimizing the deviation function

   D(m,Γ,A)=Σi(F(Ei|m,Γ,A)-σi)²/δσi²
   

3. (1 point) Implement the downhill simplex method