an R package implementing the grid search optimization algorithm with a zoom
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
.github/ISSUE_TEMPLATE Update issue templates Dec 28, 2018
R Add files via upload Jan 2, 2019
man
CODE_OF_CONDUCT.md Create CODE_OF_CONDUCT.md Dec 29, 2018
DESCRIPTION Add files via upload Jan 2, 2019
LICENSE Initial commit Dec 27, 2018
NAMESPACE Add files via upload Jan 2, 2019
NEWS.md Add files via upload Dec 27, 2018
README.md Add files via upload Jan 3, 2019
_config.yml Set theme jekyll-theme-minimal Jan 2, 2019

README.md

zoomgrid version 1.0.0 (Red Grid)

CRAN_Status_Badge

The package implements provides the grid search algorithm with a zoom. The grid search algorithm with a zoom aims to help solving difficult optimization problem where there are many local optimizers inside the domain of the target function. It offers suitable initial or starting value for the following optimization procedure, provided that the global optimum exists in the neighbourhood of the initial or starting value. The grid search algorithm with a zoom saves time tremendously in cases with high-dimenstional arguments.

You can also find the package on CRAN, see

zoomgrid@CRAN

and the corresponding paper

Modelling Nonlinear Vector Economic Time Series

See section 1.5.4.

How to install

You can either install the stable version from CRAN

install.packages("zoomgrid")

or install the development version from GitHub

devtools::install_github("yukai-yang/zoomgrid")

provided that the package "devtools" has been installed beforehand.

Example

After installing the package, you need to load (attach better say) it by running the code

library(zoomgrid)

You can take a look at all the available functions and data in the package

ls( grep("zoomgrid", search()) ) 
#> [1] "build_grid"        "grid_search"       "grid_search_check"

Motivation

Consider the two-dimensional Rastrigin function is a non-convex function which is widely used for testing the performances of some optimization algorithms.

where xi ∈ [ − 5.12, 5.12] and A = 10. It has many local minimum and its global minimum is at (0, 0) with the minimum value 0. Rastrigin function

Graph source: Rastrigin function @ WIKIPEDIA.

We give the function in R:

# 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)))

Then let us try the optimization algorithms available in the optim function.

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

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

tmp1$par; tmp1$value
#> [1] -1.9899136 -0.9949483
#> [1] 4.97479
tmp2$par; tmp2$value
#> [1] -0.9949586  0.9949586
#> [1] 1.989918
tmp3$par; tmp3$value
#> [1] -1.989912e+00  2.913338e-09
#> [1] 3.979831
tmp4$par; tmp4$value
#> [1] 0.97915333 0.01486102
#> [1] 1.088185

None of them are satisfactory...

Build the grid

We need to build grid first for the grid search. For details, see

?build_grid

We build the grid by running

# build the grid
bin = c(from=-5.12, to=5.12, by=.1)
grid = build_grid(bin,bin)

Grid search

We can first try the sequential (no parallel) grid search

# serial computation
ret1 = grid_search(Rastrigin, grid, silent=FALSE)
#> ###########################################################################
#> zoomgrid version 1.0.0 (Red Grid)
#> ---------------------------------------------------------------------------
#> The Grid Search of 0 zoom-in layers with 1 points each gives 1 results.
#> The minimizer is believed to be in the neighbourhood of -0.02 -0.02.
#> ---------------------------------------------------------------------------
#>    user  system elapsed 
#>   8.621   0.039   8.713 
#> ###########################################################################
ret1$par
#> [1] -0.02 -0.02

Then we run the parallel one

# parallel computation
ret2 = grid_search(Rastrigin, grid, num=2, parallel=TRUE, silent=FALSE)
#> ###########################################################################
#> zoomgrid version 1.0.0 (Red Grid)
#> ---------------------------------------------------------------------------
#> Parallel computation runs with 4 cores.
#> The Grid Search of 0 zoom-in layers with 2 points each gives 2 results.
#> The minimizer is believed to be in the neighbourhood of -0.02 -0.02.
#> ---------------------------------------------------------------------------
#>    user  system elapsed 
#>  14.504   0.437   4.159 
#> ###########################################################################
ret2$par
#> [1] -0.02 -0.02

Try the grid search with a zoom!

# grid search with a zoom!
ret3 = grid_search(Rastrigin, grid, zoom=2, num=2, parallel=TRUE, silent=FALSE)
#> ###########################################################################
#> zoomgrid version 1.0.0 (Red Grid)
#> ---------------------------------------------------------------------------
#> Parallel computation runs with 4 cores.
#> The Grid Search of 2 zoom-in layers with 2 points each gives 14 results.
#> The minimizer is believed to be in the neighbourhood of 5.590496e-05 5.590496e-05.
#> ---------------------------------------------------------------------------
#>    user  system elapsed 
#>  27.881   1.945   9.325 
#> ###########################################################################
ret3$par
#> [1] 5.590496e-05 5.590496e-05

Sometimes it is strongly recommended to check the time consumed by running the grid search first. This is extremely useful when the user is going to run on some super-computing server and need to know approximately how long time it will take in order to specify the corresponding settings according to some batch system like SLURM for example. So you can do as follows

ret3 = grid_search_check(Rastrigin, grid, zoom=2, num=2, parallel=TRUE, silent=FALSE)
#> ###########################################################################
#> zoomgrid version 1.0.0 (Red Grid)
#> ---------------------------------------------------------------------------
#> Parallel computation runs with 4 cores.
#> The expected time consumed by running the grid search is around 9.557705 seconds.
#> ###########################################################################
ret3 = grid_search(Rastrigin, grid, zoom=2, num=2, parallel=TRUE, silent=FALSE)
#> ###########################################################################
#> zoomgrid version 1.0.0 (Red Grid)
#> ---------------------------------------------------------------------------
#> Parallel computation runs with 4 cores.
#> The Grid Search of 2 zoom-in layers with 2 points each gives 14 results.
#> The minimizer is believed to be in the neighbourhood of 5.590496e-05 5.590496e-05.
#> ---------------------------------------------------------------------------
#>    user  system elapsed 
#>  26.975   1.591  10.203 
#> ###########################################################################