[R] non-linear integer optimization?

[Hans W Borchers]

darckeen <darckeen <at> hotmail.com> writes:

> This is an example of the type of problem, and how i'm currently using
> optim() to solve it.


I would classify this as an integer programming (IP) problem, it is not 
even non-linear, as there are no continuous variables. Your approach with 
optim() will not work, especially not with method 'L-BFGS-B' for numerical
optimization. Maybe it's worth to try method 'SANN'.

Integer programming needs special techniques. If you don't know more about
your function, it may boil down to an exhaustive discrete search that will
be slow anyway. 

Hans Werner

Example: With

    set.seed(8232); mydata <- runif(500,-1,1)   # fix these parameters

the 'optim()' approach finds a minimum of 0.9887148 with "L-BFGS-B" and
0.9139314 with method "SANN", while the global minimum is 0.7360688 in your
constraint area. DEoptim (in package DEoptim) returns 0.750277. The minimum
is more difficult to find in this example as it appears on the boundary.


> mydata <- runif(500,-1,1)
> 
> myfunc <- function(p,d)
> {
> 	print(p <- floor(p))
> 	ws <- function(i,n,x) sum(x[i-n+1]:x[i])
> 	ws1 <- c(rep(NA,p[1]-1),sapply(p[1]:NROW(d),ws,p[1],d))
> 	ws2 <- c(rep(NA,p[2]-1),sapply(p[2]:NROW(d),ws,p[2],d))
> 	ws3 <- c(rep(NA,p[3]-1),sapply(p[3]:NROW(d),ws,p[3],d))
> 	var(ws1+ws2+ws3,na.rm=TRUE)
> }
> 
> opt <- optim(c(25,50,150),myfunc,method="L-BFGS-B",
> 		control=list(fnscale=-1,parscale=c(1,1,1),factr=1,ndeps=c(5,5,5)),
> 		lower=t(c(1,51,101)),upper=t(c(50,100,200)),d=mydata)
> 
> print(floor(opt$par))
> print(myfunc(opt$par,mydata))
> 
> So the parameters to the function to be optimized are parameters to
> functions that only accept integer values.  All of the paramters to be
> optimized are integers that are subject to upper lower bound constraints. 
> This was the solution I came up with after checking CRAN, searching nabble
> etc.  
> 
> It runs but not very efficiently, and does not seem to really explore the
> sample space very well before focusing on a local minimum.  I also looked at
> the constrOptim function but I couldn't figure out how to implement two
> sided constraints with it.