---
title: "Grid Search Algorithm with a Zoom"
author: "Yukai Yang"
date: "`r Sys.Date()`"
output: rmarkdown::html_vignette
vignette: >
  %\VignetteIndexEntry{Grid Search Algorithm with a Zoom}
  %\VignetteEngine{knitr::rmarkdown}
  %\VignetteEncoding{UTF-8}
---

```{r setup, include = FALSE}
knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)
```


# zoomgrid version 1.1.0 (Red Grid)

The package implements 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 optimisers 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-dimensional arguments.


You can find the corresponding paper

[Modelling Nonlinear Vector Economic Time Series](https://pure.au.dk/ws/files/45638557/Yukai_Yang_PhD_Thesis.pdf) 

See section 1.5.4.

## How to install

You can either install the stable version from CRAN
```{r install1, eval=F}
install.packages("zoomgrid")
```
or install the development version from GitHub
```{r install2, eval=F}
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
```{r attach}
library(zoomgrid)
```

You can take a look at all the available functions and data in the package
```{r contents}
ls("package:zoomgrid")
```

### Motivation

Consider the two-dimensional **Rastrigin function**, which is a non-convex function widely used for testing optimisation algorithms.

![](figures/gif.latex.gif)

where $x_i \in [-5.12, 5.12]$ and $A = 10$. It has many local minima and its global minimum is at (0, 0) with the minimum value 0.

![Diegotorquemada [Public domain], from Wikimedia Commons](figures/Rastrigin_function.png)

Graph source: [Rastrigin function @ WIKIPEDIA](https://en.wikipedia.org/wiki/Rastrigin_function).

We give the function in R: 
```{r rastrigin}
# 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.
```{r optimize}
# 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
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
tmp2$par; tmp2$value
tmp3$par; tmp3$value
tmp4$par; tmp4$value
```
None of them are satisfactory...


### Build the grid

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

```{r show, eval=F}
?build_grid
```

We build the grid by running

```{r build}
# 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

```{r gs_nozoom}
# serial computation
ret1 = grid_search(Rastrigin, grid, silent=FALSE)
ret1$par
```

Then we run the parallel one. Parallel execution uses the future framework and works on all major platforms including Windows.

```{r pgs_nozoom}
# parallel computation
ret2 = grid_search(Rastrigin, grid, num=2, parallel=TRUE, silent=FALSE)
ret2$par
```

Try the grid search with a zoom!

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

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 \code{\link{grid_search}} on some super-computing server and need to know approximately how long 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
```{r pgs_check}
ret3 = grid_search_check(Rastrigin, grid, zoom=2, num=2, parallel=TRUE, silent=FALSE)
ret3 = grid_search(Rastrigin, grid, zoom=2, num=2, parallel=TRUE, silent=FALSE)
```