greedySearch: Greedy Search

In enricoschumann/NMOF: Numerical Methods and Optimization in Finance

Greedy Search

Description

Greedy Search

Usage

greedySearch(OF, algo, ...)

Arguments

OF	The objective function, to be minimised. Its first argument needs to be a solution; ... arguments are also passed.
algo	List of settings. See Details.
...	Other variables to be passed to the objective function and to the neighbourhood function. See Details.

Details

A greedy search works starts at a provided initial solution (called the current solution) and searches a defined neighbourhood for the best possible solution. If this best neighbour is not better than the current solution, the search stops. Otherwise, the best neighbour becomes the current solution, and the search is repeated.

Value

A list:

xbest	best solution found.
OFvalue	objective function value associated with best solution.
Fmat	a matrix with two columns. Fmat[ ,1L] contains the proposed solution over all iterations; Fmat[ ,2L] contains the accepted solutions.
xlist	a list
initial.state	the value of .Random.seed when the function was called.
x0	the initial solution
iterations	the number of iterations after which the search stopped

Author(s)

Enrico Schumann

References

Gilli, M., Maringer, D. and Schumann, E. (2019) Numerical Methods and Optimization in Finance. 2nd edition. Elsevier. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1016/C2017-0-01621-X")}

Schumann, E. (2023) Financial Optimisation with R (NMOF Manual). http://enricoschumann.net/NMOF.htm#NMOFmanual

See Also

LSopt

Examples

na <- 100
inc <- 5
R <- randomReturns(na = na,
                   ns = 1000,
                   sd = seq(0.01, 0.02, length.out = 100),
                   rho = 0.5)
S <- cov(R)
OF <- function(x, S, ...) {
    w <- 1/sum(x)
    sum(w * w * S[x, x])
}

x <- logical(na)
x[1:inc] <- TRUE


all.neighbours <- function(x, ...) {
    true  <- which( x)
    false <- which(!x)
    ans <- list()
    for (i in true) {
        for (j in false) {
            ans1 <- x
            ans1[i] <- !x[i]
            ans1[j] <- !x[j]
            ans <- c(ans, list(ans1))
        }
    }
    ans
}

algo <- list(loopOF = TRUE,
             maxit = 1000,
             all.neighbours = all.neighbours,
             x0 = x)

system.time(sol.gs <- greedySearch(OF, algo = algo, S = S))
sqrt(sol.gs$OFvalue)

enricoschumann/NMOF documentation built on April 13, 2024, 12:16 p.m.