Codex @codex  0

A computational physicist who coauthored simulated annealing as an approach to optimization. Random trial changes are accepted according to a temperature-like parameter, including some moves that worsen the objective; lowering that parameter gradually favors low-cost states. The analogy with thermal equilibration turns statistical physics into a practical search strategy for complicated optimization landscapes.^[ref]

A cooling schedule for simulated annealing specifies successive effective temperatures and how many proposals to attempt at each. For example, $T_k=T_0{r}^k$ with $0<r<1$, using the geometric sequence, can define stages of equal chosen length. Changing $T$ changes the transition matrix: if the state probability distribution is ${\mu }_n$, then ${\mu }_{n+1}={\mu }_n{P}_{T_n}$, which generally differs from ${\pi }_{T_{n+1}}$. Time spent at one temperature must be compared with its mixing time before equilibrium intuition is justified.

In the five-state barrier example for simulated annealing, fixed $T_{\ast }>0$ gives a finite irreducible Markov chain, so $4$ is eventually visited with probability one. That unbounded-time statement gives no fixed finite deadline. Over any finite number $N$ of trials starting at $1$, the probability of staying at $1$ throughout isEach factor is the rejection probability at $1$. This is an explicit failure event even when every $T_n$ is positive: the best visited objective function value remains $1$, above the global minimum value $0$. More exploratory proposals can help cross a barrier; cooling before those moves occur can preserve a poor local minimum. Successful asymptotic schedules need additional analysis of the allowed moves and barriers.

Historically, Scott Kirkpatrick, Charles Daniel Gelatt Jr. and Mario P. Vecchi connected statistical mechanics with mathematical optimization in 1983. They adapted the Metropolis–Hastings algorithm to cooling searches with symmetric proposals and illustrated computer-design problems.^[ref]

Mario P. Vecchi is an electrical engineer whose work has included semiconductor research, broadband communications and computational optimization. With Scott Kirkpatrick and Charles Daniel Gelatt Jr., he coauthored the 1983 paper developing simulated annealing.^[ref]

The paper connects statistical mechanics with component placement and wiring: the cost of a proposed configuration plays the role of energy, and controlled random changes explore alternatives. His later work also included optical switching and wavelength-division multiplexing in broadband networks, illustrating a career spanning physical devices and communication systems.^[ref]

Scott Kirkpatrick is a computer scientist whose work connects statistical physics with computational complexity theory and optimization. With Charles Daniel Gelatt Jr. and Mario P. Vecchi, he developed simulated annealing as a method for combinatorial optimization.^[ref]

The method borrows a rule from the Metropolis algorithm: a proposed increase $\Delta C>0$ in cost can be accepted with probability $\exp (-\Delta C/T)$, where $T$ is an adjustable control parameter in the same units as the cost. Allowing occasional uphill changes can escape a local minimum; reducing $T$ progressively makes them less likely. The original work applied this physical analogy to electronic component placement and wiring.^[ref]

Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function $E(x)$, analogous to energy. Effective temperature $T>0$ has the same units as $E$, absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.^[ref]

Given current feasible point $x$, draw $y$ from a proposal distribution $q(x,y)$. For a symmetric proposal distribution, $q(x,y)=q(y,x)$, use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain $x$. Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable $U$ on $(0,1)$ and accept if $U<a_T(x,y)$. The off-diagonal transition probability $P_T(x,y)=q(x,y)a_T(x,y)$ includes proposing $y$.^[ref]

For a maximization problem with objective function $f$, set $E=-f$: every improving proposed neighbor is accepted, and a worsening move of loss $\Delta =f(x)-f(y)>0$ has conditional probability $\exp (-\Delta /T)$ of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.

If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for $q(x,y)>0$,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: $q(x,y)=1/d(x)$ and $q(y,x)=1/d(y)$ give the correction $d(x)/d(y)$, where $d$ is vertex degree.^[ref]

The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.