4
$\begingroup$

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!


EDIT:

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.

$\endgroup$
6
$\begingroup$

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

  • $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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tim Dec 4 '10 at 0:05
  • 1
    $\begingroup$ @Tim As I wrote, MH is only a way of accepting steps -- SA is also MH. Yet you can hold the temperature constant to make it just 'plain MH'. $\endgroup$ – user88 Dec 4 '10 at 0:08
  • 2
    $\begingroup$ Simulated annealing is an adaption of the Metropolis-Hastings algorithm (as mentioned in the Wikipedia link). You could always ask whoever set the assignment whether SA was what he/she had in mind. $\endgroup$ – Dikran Marsupial Dec 4 '10 at 0:08
3
$\begingroup$

If you want to find the global minimum of a function, simulated annealing would be the algorithm to look at, in which case there is no need to view the function as an unnormalised density of any kind and no need to transform the function.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tim Dec 4 '10 at 0:05
0
$\begingroup$

Yes, simulated annealing is also an instance of Metropolis Hasting sampling. Just set the unnormalized density function as $e^{-f(x)/T}$ and use symmetric proposal distribution (which also makes Metropolis Hasting sampling as Metropolis sampling).

So, the acceptance probability is $min(1, \dfrac{e^{-f(x')/T}}{e^{-f(x)/T}})=min(1,e^{-(f(x')-f(x))/T})$. Yeah! simulated annealing!

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.