grid_search: Carry out the grid search algorithm with a zoom.
In yukai-yang/zoomgrid: Grid Search Algorithm with a Zoom

Description Usage Arguments Details Value Author(s) See Also Examples

This function carries out the grid search algorithm with a zoom.

1 2	grid_search(FUN, grid, MoreArgs = NULL, zoom = 0, decay = 0.5, num = 1, parallel = FALSE, cores = NULL, silent = TRUE)

`FUN`	the target function to be minimized.
`grid`	an object of the class GRID from `build_grid`.
`MoreArgs`	a list of other arguments to `FUN`, see `mapply`.
`zoom`	number of (additional) rounds or layers of the zoom-in, 0 by default.
`decay`	a number in between 0 and 1 representing the decay rate of the grid sizes of the zoom.
`num`	number of points to return, i.e. the smallest `num` points, 1 by default the minimum.
`parallel`	a boolean indicating if the parallel computation is carried out, by default `FALSE`.
`cores`	The number of cores to use, i.e. at most how many child processes will be run simultaneously. For details, see `mcmapply` in `parallel` package.
`silent`	a boolean indicating if the information regarding the omputation is printed.

The target function FUN to be minimized is a scalar real valued function with multiple arguments. The maximization can be achieved by multiplying -1 to the original function, and then input the new function to FUN.

The grid must be created by using the function build_grid function in the package.

Any other invariant arugments to the function FUN can be specified in MoreArgs by using a list with variable names.

The common grid search first build a grid within some bounded area. And then the target function will be evaluated at each point in the grid. The points that produce the smallest num target function values shall be returned.

zoom = 0 implies that no zoom-in will be applied and the corresponding grid search is the common one introduced above, while any integer zoom > 0 implies that the zoom-in will be applied in the grid search. When a grid search with a zoom is applied, zoom > 0 is actually the number of rounds or layers of the algorithm, and therefore the grid search algorithm with a zoom consists of

n^{0} + n^{1} + n^{2} + ... + n^{z}

grid searches, where n = num and z = zoom.

As mentioned above, in each grid search, num is the number of points that will be returned. And therefore, in the end, there will be

n^{1} + n^{2} + n^{3} + ... + n^{z+1}

points returned, where n = num and z = zoom.

Each time when the algorithm zooms in, it will automatically build subgrids based on the points that have been found in the super gird search. Due to the exhaustive property of the grid search algorithm, it is desirable to make fewer points in the subgrid. The decay rate decay provides the opportunity to control the number of points in the subgrids. The number of points for each argument of the target function in the subgrid will be max [ Int (decay * N), 3 ].

Parallel computation is implemented in the function, which can be activated by setting parallel = TRUE.

cores, which represents the number of cores, works only when parallel = TRUE. By default cores=NULL implies that the function will detect the number of cores and use it.

The boolean silent controls if there will be output in the console.

a list containing the results from the grid search with a zoom.

The list contains the following components:

`par`	the approximate global minimizer
`points`	all the local minimizer points found by the grid search with a zoom

Yukai Yang, yukai.yang@statistik.uu.se

build_grid, grid_search_check

# Rastrigin function
ndim = 2 # number of dimension
nA = 10 # parameter A
# vx in [-5.12, 5.12]

# minimizer = rep(0, ndim)
# minimum = 0
Rastrigin <- function(vx) return(nA * ndim + sum(vx*vx - nA * cos(2*pi*vx)))


# set seed and initialize the initial or starting value
set.seed(1)
par = runif(ndim, -5.12, 5.12)
cat("start from", par)

# results from different optimization algorithms
optim(par = par, Rastrigin, method='Nelder-Mead')
optim(par = par, Rastrigin, method='BFGS')
optim(par = par, Rastrigin, method='L-BFGS-B')
optim(par = par, Rastrigin, method='SANN')


# a toy example
# build the grid first
bin = c(from=-5.12, to=5.12, by=.5)
grid = build_grid(bin,bin)
# so this is a relatively sparse grid

# serial computation
ret0 = grid_search(Rastrigin, grid, silent=FALSE)
ret0$par



# We can build a finer grid
bin = c(from=-5.12, to=5.12, by=.1)
grid = build_grid(bin,bin)

# serial computation
ret1 = grid_search(Rastrigin, grid, silent=FALSE)
ret1$par

# parallel computation
ret2 = grid_search(Rastrigin, grid, num=2, parallel=TRUE, silent=FALSE)
ret2$par

# grid search with a zoom!
ret3 = grid_search(Rastrigin, grid, zoom=2, num=2, parallel=TRUE, silent=FALSE)
ret3$par