Solved – Minimization of a function by Metropolis-Hastings algorithms

When minimizing a function by general Metropolis-Hastings algorithms, the function is viewed as an unnormalized density of some distribution.

(1) As density functions are required to be nonnegative, I was wondering if there is some restriction on functions that can be minimized by Metropolis-Hastings algorithms?

(2) To minimize the following function:

$f(x) = 10 sin(0.3x) sin(1.3x^2) + 0.001 x^4 + 0.2 x+ 80.$

How do I transform it into some other function before I can apply Metropolis-Hastings algorithms?

Thanks and regards!


Thanks! I agree Simulated Annealing might better handling such situation, but this is an assignment that requires to use Metropolitan-Hastings algorithms. So I am afraid I have not other choice.

You are rather looking for a simulated annealing, which is easier to understand when formulated in the original, physics way:

  • $x$ is a state of the system
  • $f(x)$ is an energy of the system; energy is defined up to addition of a constant, so there is no problem with it being negative or positive — the only constraint is the-lower-the-better
  • $T$ is a temperature of the system, and $kT$ is this temperature expressed in energy units

the MH algorithm, formulated as

  1. $x'=x+text{random change}$
  2. if $big{exp{frac{f(x)-f(x')}{kT}}>R(0;1)big}$ than $x=x'$
  3. goto 1

recreates the same occupancy of particular states (values of $x$) as for a system placed in temperature $T$, as shown by Metropolis in his pioneer work.

Physical systems tend to spontaneously go into the lowest energy state and stay there, so after initial relaxation $x$ should generally oscillate around minimum. Those oscillations' amplitude depends on temperature, so simulated annealing reduces $T$ during run to reduce them and make more accurate localisation of minimum. Initially high temperature is required to prevent the system from landing and staying stuck for a very long time in some local minimum.

EDIT: If you were told that you should use just Metropolis-Hastings, it most probably means you should do this this way, only with constant temperature (constantly deceasing temperature is the only thing that simulated annealing adds to MH). Then you will need to make few experiments to figure out a good temperature, so that there will be quite good accuracy no stucking in the local minima.

Similar Posts:

Rate this post

Leave a Comment