What is the difference between simulated annealing and deterministic annealing?
After diving deeper into the material I am able to answer my own question:
Simulated Annealing tries to optimize a energy (cost) function by stochastically searching for minima at different temparatures via a Markov Chain Monte Carlo method. The stochasticity comes from the fact that we always accept a new state $c'$ with lower energy ($\Delta E &lt; 0$), but a new state with higher energy ($\Delta E &gt; 0$) only with a certain probability
$$p(c \to c') = \text{min}\{1, \exp(-\frac{\Delta E}{T}) \},$$
$$\Delta E = E(c') - E(c).$$
Where we used the Gibbs distribution $p(c) = \frac{1}{Z}\text{exp}(\frac{-E(c)}{T})$ to calculate probabilities for each state, with $Z$ being the partition sum. The temperature $T$ plays the role of a scaling factor for the probability distribution. If $T \to \infty $ we have a uniform distribution and all states are equally possible. If $T \to 0$ we have a Dirac delta function around the global optimum. By starting with a high $T$, sampling states and gradually decreasing it, we can make sure to sample enough states from the state space and accepting energetic higher states in order to escape local minima on the way to the global optimum. After sampling long enough while slowly decreasing the temperature, we theoretically arrive at the global optimum.
Deterministic Annealing on the other hand directly minimizes the free energy $F(T)$ of the system deterministically at each temperature, e.g. by Expectation-Maximization (EM-algorithm). The intuition behind it is that we like to find an optimum at a high temperature (where it is easier to find one because there are fewer local minima), accept this as intermediate solution, lower the temperature, thus scaling the cost function such it is more peaked around it's optima (making optimization a bit more difficult) and start deterministically looking for an optimum again. This is repeated until the temperature is low enough and we (hopefully) found a global solution to our problem. Major drawback is that there is no guarantee to arrive at a global optimum in contrast to simulated annealing. The whole idea of scaling the energy function is based on the concept of homotopy: &quot;Two continuous functions [...] can be &quot;continuously deformed&quot; into each other.&quot;