Answers.Body: <p>After diving deeper into the material I am able to answer my own question:</p>
  <p><em>Simulated Annealing</em> tries to optimize a energy (cost) function by <em>stochastically</em> searching for minima at different temparatures via a <a href="https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo" rel="nofollow noreferrer">Markov Chain Monte Carlo</a> method. The stochasticity comes from the fact that we always accept a new state <span class="math-container">$c'$</span> with lower energy (<span class="math-container">$\Delta E &lt; 0$</span>), but a new state with higher energy (<span class="math-container">$\Delta E &gt; 0$</span>) only with a certain probability</p>
  <p><span class="math-container">$$p(c \to c') = \text{min}\{1, \exp(-\frac{\Delta E}{T}) \},$$</span>
  <span class="math-container">$$\Delta E = E(c') - E(c).$$</span></p>
  <p>Where we used the <a href="https://en.wikipedia.org/wiki/Gibbs_measure" rel="nofollow noreferrer">Gibbs distribution</a> <span class="math-container">$p(c) = \frac{1}{Z}\text{exp}(\frac{-E(c)}{T})$</span> to calculate probabilities for each state, with <span class="math-container">$Z$</span> being the partition sum. The temperature <span class="math-container">$T$</span> plays the role of a scaling factor for the probability distribution. If <span class="math-container">$T \to \infty $</span> we have a uniform distribution and all states are equally possible. If <span class="math-container">$T \to 0$</span> we have a Dirac delta function around the global optimum. By starting with a high <span class="math-container">$T$</span>, 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.</p>
  <p><em>Deterministic Annealing</em> on the other hand directly minimizes the <em>free energy</em> <span class="math-container">$F(T)$</span> of the system deterministically at each temperature, e.g. by Expectation-Maximization (<a href="https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_algorithm" rel="nofollow noreferrer">EM-algorithm</a>). 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 <a href="https://en.wikipedia.org/wiki/Homotopy" rel="nofollow noreferrer">homotopy</a>: <em>&quot;Two continuous functions [...] can be &quot;continuously deformed&quot; into each other.&quot;</em></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-07-19T14:58:25.713Z
Answers.LastActivityDate: 2020-07-19T14:58:25.713Z
Answers.UserDisplayName: Tinu
Body: <p>Not sure if this is the right place, but I was wondering if someone could briefly explain to me the <strong>differences &amp; similarities</strong> between <em>simulated annealing</em> and <em>deterministic annealing</em>?</p>
  
  <p>I know that both methods are used for optimization and both originate from statistical physics with the intuition of reaching a minimum energy (cost) configuration by <em>cooling</em> (i.e. slowly reducing the temperature in the Boltzmann distribution to calculate probabilities for configurations).</p>
  
  <p>Unfortunately, Wikipedia has no article about deterministic annealing and the one about <a href="https://en.wikipedia.org/wiki/Simulated_annealing" rel="nofollow noreferrer">simulated annealing</a> does not mention any comparison.</p>
  
  <p><a href="https://www.intechopen.com/books/computational-optimization-in-engineering-paradigms-and-applications/deterministic-annealing-a-variant-of-simulated-annealing-and-its-application-to-fuzzy-clustering" rel="nofollow noreferrer">This</a> resource has a brief comparison section between the two methods, however, I do not understand why the search strategy of DA is </p>
  
  <blockquote>
    <p>based on the <strong>steepest descent algorithm</strong> </p>
  </blockquote>
  
  <p>and how </p>
  
  <blockquote>
    <p>it searches the local minimum <strong>deterministically</strong> at each temperature.</p>
  </blockquote>
  
  <p>Any clarification appreciated.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-11T13:31:04.123Z
Comments.Text: In that article that you mention, they say that "Stochastic search based on the Metropolis algorithm". However, although I am familiar with SA, I don't recall having read that anywhere (but my memory isn't that good). So, even though SA may have been based on or inspired by another algorithm/method, that information isn't probably very useful, unless you are already familiar with the Metropolis algorithm. Similarly, although I am not familiar with DA, I suspect that, generally, it may not be very relevant if it's based on the steepest descent algorithm or not, as long as you know how DA works.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-06-11T13:51:40.803Z
Comments.Text: Furthermore, in the introduction section of the original paper that introduced DA, the authors say k-means is a "steepest descent" algorithm, in the sense that k-means always moves in some space that decreases the cost function (so it can be trapped in a local minimum). Again, I am familiar with k-means, but I've never heard of this interpretation, even though it kind of makes sense to me. So, DA is a "steepest descent" algorithm in the sense that it always moves in some search space so that to decrease the cost (or loss), but it probably can get trapped in a local minimum.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-07-19T16:14:41.243Z
Comments.Text: Thanks for you comment. After some time I came to an insightful explanation as well.
Comments.UserDisplayName: Tinu
Tags: <comparison><optimization><simulated-annealing><deterministic-annealing>
Title: What is the difference between simulated annealing and deterministic annealing?
UserDisplayName: Tinu
ThreadText: # What is the difference between simulated annealing and deterministic annealing?
  
  (Asked by: username_0 on 2020-06-09)
  
  Not sure if this is the right place, but I was wondering if someone could briefly explain to me the **differences & similarities** between *simulated annealing* and *deterministic annealing*?
  
  I know that both methods are used for optimization and both originate from statistical physics with the intuition of reaching a minimum energy (cost) configuration by *cooling* (i.e. slowly reducing the temperature in the Boltzmann distribution to calculate probabilities for configurations).
  
  Unfortunately, Wikipedia has no article about deterministic annealing and the one about [simulated annealing](https://en.wikipedia.org/wiki/Simulated_annealing) does not mention any comparison.
  
  [This](https://www.intechopen.com/books/computational-optimization-in-engineering-paradigms-and-applications/deterministic-annealing-a-variant-of-simulated-annealing-and-its-application-to-fuzzy-clustering) resource has a brief comparison section between the two methods, however, I do not understand why the search strategy of DA is
  
  > based on the **steepest descent algorithm**
  
  and how
  
  > it searches the local minimum **deterministically** at each temperature.
  
  Any clarification appreciated.
  
  **Tags:** comparison, optimization, simulated-annealing, deterministic-annealing
  > **Comments:**
  > **username_1**: In that article that you mention, they say that "Stochastic search based on the Metropolis algorithm". However, although I am familiar with SA, I don't recall having read that anywhere (but my memory isn't that good). So, even though SA may have been based on or inspired by another algorithm/method, that information isn't probably very useful, unless you are already familiar with the Metropolis algorithm. Similarly, although I am not familiar with DA, I suspect that, generally, it may not be very relevant if it's based on the steepest descent algorithm or not, as long as you know how DA works.  
  > **username_1**: Furthermore, in the introduction section of the original paper that introduced DA, the authors say k-means is a "steepest descent" algorithm, in the sense that k-means always moves in some space that decreases the cost function (so it can be trapped in a local minimum). Again, I am familiar with k-means, but I've never heard of this interpretation, even though it kind of makes sense to me. So, DA is a "steepest descent" algorithm in the sense that it always moves in some search space so that to decrease the cost (or loss), but it probably can get trapped in a local minimum.  
  > **username_0**: Thanks for you comment. After some time I came to an insightful explanation as well.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-07-19. Score: 1 | Accepted answer
  
  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](https://en.wikipedia.org/wiki/Markov_chain_Monte_Carlo) method. The stochasticity comes from the fact that we always accept a new state $c'$ with lower energy ($\Delta E < 0$), but a new state with higher energy ($\Delta E > 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](https://en.wikipedia.org/wiki/Gibbs_measure) $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](https://en.wikipedia.org/wiki/Expectation%E2%80%93maximization_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](https://en.wikipedia.org/wiki/Homotopy): *"Two continuous functions [...] can be "continuously deformed" into each other."*
  
  
  ---
  
  