Homepage > MCMC

Searching for Maxima

Let $ f(x)$ be a nonnegative objective function on the interval $ [a,b]$. First we consider the following algorithm searching for maxima:
  1. Choose the initial state $ X_0$ at time $ t = 0$.
  2. Suppose that $ X_t = x$ at time $ t$. Then pick the next move $ \Delta x$ randomly and set $ y = x + \Delta x$.
  3. If $ a\le y \le b$ and $ f(y) > f(x)$ then set $ X_{t+1} = y$.
  4. Otherwise, stay $ X_{t+1} = x$ at time $ t+1$.

Explore it. Download nm.r and search.r into your own machine. Use the normal mixture density function on the interval $ [0,1]$ as the objective function of choice, and see if the algorithm achieves the global maximum.

> source("nm.r")
> source("search.r")
> search(ff=nm)

Random ascending rule. Next we consider the following algorithm searching for maxima:

  1. Choose the initial state $ X_0$ at time $ t = 0$.
  2. Suppose that $ X_t = x$ at time $ t$. Then pick the next move $ \Delta x$ randomly and set $ y = x + \Delta x$.
  3. Generate a uniform random variable $ U$ on $ [0,1]$
  4. If $ 0\le y \le 1$ and $ f(y)/f(x) > U$ then set $ X_{t+1} = y$.
  5. Otherwise, stay $ X_{t+1} = x$ at time $ t+1$.

Explore it. See how differently the algorithm behaves.

> par(mfrow=c(2,1))
> xx = search(ff=nm, random=T, save.time=0,run.time=1000)
> plot(0:1000, xx, type="l", main="Trajectory Data", xlab="time", ylab="state")
> xx = search(ff=nm, random=T, save.time=0,run.time=1000)
> hist(xx, freq=F, breaks=seq(0,1,by=0.05), col="blue", main="Trajectory Data", xlab="state")
> xx = search(ff=nm, random=T, save.time=4000,run.time=5000)
> hist(xx, freq=F, breaks=seq(0,1,by=0.05), col="blue", main="Trajectory Data", xlab="state")

Programming note. The set-parameter function par(mfrow=c(2,1)) set mfrow=c(2,1), and splits the multiple graphics to assign 2 figures horizontally and one vertically. hist() is used to create the histogram of the data, and the optional arguments ``freq=F'' and ``breaks=seq(0,1,by=0.05)'' are specified. Here these options request ``relative frequency histogram'' with given class intervals $ (0.00,0.05)$, $ (0.05,0.10)$, $ \ldots$, $ (0.95,1.00)$.


© TTU Mathematics