MC Optimization

Recursive Integration
Monte Carlo Maximization
EM Algorithm
Simulated Annealing
Fundamental idea: A change of scale, called temperature, allows for faster moves on the surface of the function of hhh
 to maximize, whose negative is called energy.
It is important to note that if the larger TTT
 is, accepting one decreasing is more likely.
Example: To maximize h(x)=[cos⁡(50x)+sin⁡(20x)]2h(x)=[\cos(50x)+\sin(20x)]^2h(x)=[cos(50x)+sin(20x)]2
.
We can use the following Julia code to solve this problem:
1
r = 0.5
2
function T(t)
3
    return 1/log(t)
4
end
5
# target function
6
function h(x)
7
    return (cos(50x) + sin(20x))^2
8
end
9
​
10
N = 2500
11
x = ones(N)
12
y = ones(N)
13
for t = 1:(N-1)
14
    # step 1
15
    at = max(x[t]-r, 0)
16
    bt = min(x[t]+r, 1)
17
    u = rand() * (bt - at) + at 
18
    # step 2
19
    rho = min(exp( (h(u) - h(x[t])) / T(t) ), 1)
20
    if rand() < rho
21
        x[t+1] = u
22
        y[t+1] = h(u)
23
    else
24
        x[t+1] = x[t]
25
        y[t+1] = y[t]
26
    end
27
end
Copied!
The trajectory of 2500 pairs (x(t),y(t))(x^{(t)}, y^{(t)})(x(t),y(t))
 is

Rao-Blackwellization

MCMC

Last modified 3yr ago

Copy link

Contents

Recursive Integration

Monte Carlo Maximization

EM Algorithm

Simulated Annealing