Description
For the next major release of iminuit, I finally implemented the ability to scan the function for a minimum using a brute-force grid search in N dimensions. This is very inefficient, but still a feature that users regularly request and there has been an open issue in iminuit about it for a long time, now closed.
Originally this was supposed to use MnScan from C++ Minuit2, but I found some severe problems with MnScan. I would like to discuss what we want MnScan to do, then I would be happy to work on a patch.
What MnScan currently does
It does a 1D scan with 41 steps for each parameter in sequence, so it is not actually scanning the full hypercube. It first scans one parameter, then starts the scan of the second parameter from the best value of the first and so on. Instead of a full 2D scan, it does something like this:
y
B
y
xxxxxxxxxxxxxxxxxx A xxxxxx
y
y
where A and B are the minima along the x and y axis respectively. This approach has the advantage that the number of function evaluations scales like with k * n, where k is the number of dimensions and n the number of steps per dimension, while a full grid search scales like n ^ k. However, this approach will fail miserably when x and y are correlated, trying this on the Rosenbrock function for instance gives terrible results (basically no improvement with respect to the starting value).
What to do?
The current behavior of MnScan is not what people usually consider a scan, which most people understand as a full grid search over the whole N-dimensional space. It seems that MnScan is not really used in ROOT, but I may be mistaken.
If it is not really used, I would suggested to keep the name MnScan and change the implemenation to do a full hypercube scan. I am strongly convinced that MnScan should do a full grid search instead of what it currently does, because the current implementation is fairly pointless for most real-world functions which have correlations.
If MnScan has a use case that I am not aware of, then I propose to add a new Minimizer, MnHyperScan (or similar name), which implements the full scan.
Other issues with current MnScan
- One cannot configure the number of steps taken per dimension when MnScan is called through the minimizer interface (MnApplication). The maxcalls option should be used for this.
- A gradient and second derivatives are computed for the starting values, only to be discarded. This is wasteful.
- The scan returns EDM = 0, which is very misleading. It should either return inf or NaN, to indicate that the EDM is invalid. Ideally, a proper EDM should be calculated for the obtained minimum after the scan.
- MnScan always builds a vector of all the (parameter, function value) pairs obtained during the scan, but that vector is discarded after the run. This is wasteful.