This R package provides an algorithm for nonlinear global optimization based on the variable neighbourhood trust region search (VNTRS) algorithm proposed by Bierlaire et al. (2009) “A Heuristic for Nonlinear Global Optimization”. The algorithm combines variable neighbourhood exploration with a trust-region framework to efficiently search the solution space. It can terminate a local search early if the iterates are converging toward a previously visited local optimum or if further improvement within the current region is unlikely. In addition to global optimization, the algorithm can also be applied to identify multiple local optima.
How to get started
Specify a function
fthat computes value, gradient, and Hessian of the objective to be optimized and returns them as a named list with elementsvalue,gradient, andhessian. Note thatgradientand/orhessiancan be unspecified, in which case finite differences are used.Call
vntrs::vntrs(f = f, npar = npar, minimize = minimize), where
nparis the number of parameters offandminimizedetermines whetherfshould be minimized (minimize = TRUE, the default) or maximized (minimize = FALSE).
Optionally, the algorithm can be tuned by setting dedicated control arguments (for example init_runs or neighbors, see help("vntrs") for details).
Example
The example below minimizes the well-known six-hump camel function, which has two global minima.
set.seed(1)
camel <- function(x) {
x1 <- x[1]
x2 <- x[2]
value <- (4 - 2.1 * x1^2 + x1^4 / 3) * x1^2 + x1 * x2 + (-4 + 4 * x2^2) * x2^2
gradient <- c(
8 * x1 - 8.4 * x1^3 + 2 * x1^5 + x2,
x1 - 8 * x2 + 16 * x2^3
)
hessian <- matrix(
c(
8 - 25.2 * x1^2 + 10 * x1^4, 1,
1, -8 + 48 * x2^2
),
nrow = 2,
byrow = TRUE
)
list(value = value, gradient = gradient, hessian = hessian)
}
vntrs::vntrs(
f = camel, # objective that supplies value, gradient, Hessian
npar = 2, # two variables (x1 and x2)
init_runs = 5, # start from 5 random points
neighborhoods = 5, # try 5 neighbourhood radii per trust region
neighbors = 5, # evaluate 5 trial points per neighbourhood
lower = c(-3, -2), # lower search bounds for x1 and x2
upper = c(3, 2), # upper search bounds for x1 and x2
collect_all = TRUE, # also look for local optima
quiet = FALSE # show status messages
)
#> Initialize VNTRS.
#> * Apply local search at 5 random starting points.
#> ** Run 1 [0 s] [found optimum] [optimum is unknown]
#> ** Run 2 [0 s] [found optimum]
#> ** Run 3 [0 s] [found optimum]
#> ** Run 4 [0 s] [found optimum]
#> ** Run 5 [0 s] [found optimum]
#> Start VNTRS.
#> * Select neighborhood 1.
#> ** Neighbor 1 [0 s]
#> ** Neighbor 2 [0 s] [found optimum] [optimum is unknown]
#> ** Neighbor 3 [0 s] [found optimum]
#> ** Neighbor 4 [0 s]
#> ** Neighbor 5 [0 s]
#> * Reset neighborhood, because better optimum was found.
#> * Select neighborhood 1.
#> ** Neighbor 1 [0 s]
#> ** Neighbor 2 [0 s] [found optimum]
#> ** Neighbor 3 [0 s] [found optimum]
#> ** Neighbor 4 [0 s] [found optimum]
#> ** Neighbor 5 [0 s] [found optimum]
#> * Select neighborhood 2.
#> ** Neighbor 1 [0 s] [found optimum]
#> ** Neighbor 2 [0 s]
#> ** Neighbor 3 [0 s]
#> ** Neighbor 4 [0 s] [found optimum]
#> ** Neighbor 5 [0 s] [found optimum]
#> * Select neighborhood 3.
#> ** Neighbor 1 [0 s] [found optimum] [optimum is unknown]
#> ** Neighbor 2 [0 s] [found optimum]
#> ** Neighbor 3 [0 s] [found optimum] [optimum is unknown]
#> ** Neighbor 4 [0 s] [found optimum]
#> ** Neighbor 5 [0 s] [found optimum]
#> * Select neighborhood 4.
#> ** Neighbor 1 [0 s] [found optimum]
#> ** Neighbor 2 [0 s] [found optimum]
#> ** Neighbor 3 [0 s] [found optimum]
#> ** Neighbor 4 [0 s] [found optimum]
#> ** Neighbor 5 [0 s] [found optimum]
#> * Select neighborhood 5.
#> ** Neighbor 1 [0 s] [found optimum] [optimum is unknown]
#> ** Neighbor 2 [0 s] [found optimum]
#> ** Neighbor 3 [0 s] [found optimum]
#> ** Neighbor 4 [0 s] [found optimum]
#> ** Neighbor 5 [0 s] [found optimum]
#> Done.
#> p1 p2 value global
#> 1 0.08984201 -0.7126564 -1.0316285 TRUE
#> 2 -0.08984201 0.7126564 -1.0316285 TRUE
#> 3 -1.70360672 0.7960836 -0.2154638 FALSE
#> 4 1.60710475 0.5686515 2.1042503 FALSE
#> 5 1.70360671 -0.7960836 -0.2154638 FALSE