library(plot3D)
# 1. Zero-order Coordinate Search
# (a)
random_search <- function(g,alpha=1,max_its,w0,tol) {
w <- matrix(w0, nrow=1)
p <- 5
i <- 1
g.min <- g(w[i,1],w[i,2])
while (TRUE) { # do-while
alpha <- 1/sqrt(i)
i <- i + 1
w <- rbind(w, w[i-1,])
for (j in 1:p) {
   d <- runif(2,-1,1); d <- d / norm(d, '2') # step direction
   w.candidate <- w[i,1:2] + alpha * d
   if (g(w.candidate[1], w.candidate[2]) < g.min) {
   w[i,] <- w.candidate
   g.min <- g(w[i,1], w[i,2])
   }
}
if (abs(g(w[i-1,1],w[i-1,2]) - g.min) < tol || i > max_its) {
   break
}
}
weight_history <- w
cost_history <- g(w[,1],w[,2])
return(list(weight_history=weight_history,cost_history=cost_history))
}
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
# coordinate_search(g,alpha,max_iteration,w0,tolerance)
# initialize w.current, i: current iteration <- 1
# Repeat:
# evaluate 4 directions along each coordinate to at the distance alpha
# w.next is the point evaluated to give the smallest g.value.
# record w.next
# if (i > max_iteration or |g(w.next)-g(w.current)| < tolerance):
# break the repeat
# else:
# w.current <- w.next, i <- i + 1
#
# return recorded w, and g(recorded w)
# # # # # # # # # # # # # # # # # # # # # # # # # # # # # # #
coordinate_search <- function(g,alpha_choice=1,max_its=100,w0,tol=1e-5) {
if (alpha_choice=="diminishing") {
return(random_search(g,alpha=1,max_its,w0,tol))
} else { # alpha_choice is numeric
alpha <- alpha_choice
}
w <- matrix(w0, nrow=1)
i <- 1
d <- matrix(c(-1,1,0,0,0,0,-1,1),4,2)
g.min <- g(w[i,1],w[i,2])
while (TRUE) {
i <- i + 1
w <- rbind(w, w[i-1,])
for (j in 1:4) {
   w.candidate <- w[i-1,] + alpha * d[j,]
   if (g(w.candidate[1], w.candidate[2]) < g.min) {
   w[i,] <- w.candidate
   g.min <- g(w[i,1], w[i,2])
   }
}
if (abs(g(w[i-1,1],w[i-1,2]) - g.min) < tol || i > max_its) {
   break
}
}
weight_history <- w
cost_history <- g(w[,1],w[,2])
return(list(weight_history=weight_history,cost_history=cost_history))
}
# (b)
g <- function(w1, w2) {
w1^2 + w2^2 + 2
}

w0 <- c(4,4)
result <- coordinate_search(g,alpha_choice=1,max_its=100,w0,tol=1e-8)
w <- result$weight_history
cost_history <- result$cost_history

ygrid <- seq(-4,4,length=1000)
xgrid <- seq(-4,4,length=1000)
g_out <- outer(xgrid, ygrid, FUN = g)
contour(x=xgrid,
   y=ygrid,
   z=g_out) +
points(w[1:dim(w)[1],1],
      w[1:dim(w)[1],2],
      type = "b", cex=0.5, col="blue")

plot(cost_history, type='l',ylab="cost", main="coordinate search")

# (c)
result <- coordinate_search(g,alpha_choice='diminishing',max_its=1000,w0,tol=1e-16)
w <- result$weight_history
cost_history <- result$cost_history

Use the following dataset 'Crime in Major Cites', to compare crime...