Back to Computational Biology page
Implementation of golden section search for extremumOn p. 272 of The Ecological Detective (Hilborn and Mangel 1997) the steps of a golden section search are described. The code below implements the first 25 steps of the search in R. This code could be modified to search until a tolerance level is reached for p1-p2. A plot of the steps is at the bottom of the page. Note that the function uses recursion rather than for() or while() control structures. In practice, the high-level optimize() function can be used for one-dimensional searches in R. The code below is meant only to illustrate the steps the algorithm takes. |
lambda<-(sqrt(5)-1)/2
golden.section<-function(f, pL, pU, p1, p2, top, result){
if (top==26){
return(result)
}
else if(top==1){
p1<-pL + (1-lambda)*(pU - pL)
p2<-pU - (1-lambda)*(pU - pL)
}
result[top,]<-c(p1,p2)
if(f(p2) < f(p1)){
pU<-p2
pL<-pL
p2<-p1
p1<-pL + (1-lambda)*(pU - pL)
} else if (f(p2) > f(p1)){
pU <- pU
pL <- p1
p1 <- p2
p2<-pU - (1-lambda)*(pU - pL)
}
result<-golden.section(f, pL, pU, p1, p2, top=top+1, result)
return(result)
}
result<-data.frame(p1=rep(NA, 25), p2=rep(NA, 25))
result<-golden.section(function(x) -(x - 1.235)^2 + 0.78 * x + 0.2,
-5, 5, NA, NA, 1, result)
x<-seq(-2,3,by=0.05)
plot(x, -(x - 1.235)^2 + 0.78 * x + 0.2, type="l")
segments(result$p1, seq(-10,-1,length.out=25),
result$p2, seq(-10,-1,length.out=25))
text(3, seq(-10,-1,length.out=25), labels=1:25, cex=0.8)
|
Plot of the quadratic function on which a maximum is found by the golden.section() function above. The horizontal lines connect the values of p1 and p2 at each of the twenty five steps of the algorithm. |