Simulated annealing aims at a series of target distributions $$\pi_T(x)\propto\exp\{T\,H(x)\}$$ to find the maximum of the function $H$ and its argument $$\arg_x\max_{x\in \mathfrak X} H(x)$$ if the temperature $T$ increases slowly enough. When $\mathfrak X$ is of large dimension, it is usual to apply a Gibbs sampler to divide the simulation from $\exp\{T\,H(x)\}$ into smaller dimension targets.

Consider now solving the saddle-point problem $$\arg_{(x_1,x_2)}\max_{x_1\in \mathfrak X_1}\min_{x_2\in \mathfrak X_2} H(x_1,x_2)$$ One can attempt a Gibbs sampling strategy with an increasing sequence of temperatures $T$ by simulating successively $$X_2^{(t)}|X_1^{(t)}=x_1^{(t)}\sim \exp\{-T\,H(x_1^{(t)},x_2)\}$$ and $$X_1^{(t+1)}|X_2^{(t)}=x_2^{(t)}\sim \exp\{+T\,H(x_1,x_2^{(t)})\}$$ but I wonder at the justification (and convergence) of this strategy given that the two Gibbs conditionals are not compatible with a joint but instead antagonistic.

  • 1
    $\begingroup$ scicomp.stackexchange.com/questions/3372/… $\endgroup$ – Mark L. Stone Apr 2 at 1:32
  • $\begingroup$ @MarkL.Stone: thank you for the link. Downhill simulated annealing is essentially the same as uphill simulated annealing, while saddlepoint simulated annealing remains a mystery (to me at least). $\endgroup$ – Xi'an Apr 2 at 6:18

Your Answer

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

Browse other questions tagged or ask your own question.