This R package implements the variable neighborhood trust region search (VNTRS) algorithm for nonlinear global optimization, following Bierlaire et al. (2009) “A Heuristic for Nonlinear Global Optimization”. The method combines neighborhood exploration with a trust-region framework to search the solution space efficiently. It can terminate a local search early when the iterates converge toward a previously visited local optimum or when further improvement within the current region is unlikely. The algorithm can also be used to identify multiple local optima.
How to get started
Specify a function
fthat computes the objective value. It may also return the gradient and Hessian. Return either a numeric value or a named list withvalue,gradient, andhessiancomponents. Omitted derivatives are approximated by finite differences.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 supplies value, gradient, Hessian
npar = 2, # two variables (x1 and x2)
init_runs = 5, # start from 5 random points
neighborhoods = 5, # try 5 neighborhood radii per trust region
neighbors = 5, # evaluate 5 trial points per neighborhood
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