Given a target function $U$ to minimize on a finite state space
$\mathcal{X}$, a proposal chain with generator $Q$ and a cooling schedule
$T(t)$ that depends on time $t$, in this paper we study two types of simulated
annealing (SA) algorithms with generators $M_{1,t}(Q,U,T(t))$ and
$M_{2,t}(Q,U,T(t))$ respectively. While $M_{1,t}$ is the classical SA
algorithm, we introduce a simple and greedy variant that we call $M_{2,t}$
which provably converges faster. Under any $T(t)$ that converges to $0$ and
mild conditions on $Q$, the Markov chain generated by $M_{2,t}$ is weakly
ergodic. When $T(t) > c_{M_2}/\log(t+1)$ follows the logarithmic cooling
schedule, our proposed algorithm is strongly ergodic both in total variation
and in relative entropy, and converges to the set of global minima, where
$c_{M_2}$ is a constant that we explicitly identify. If $c_{M_1}$ is the
optimal hill-climbing constant that appears in logarithmic cooling of
$M_{1,t}$, we show that $c_{M_1} \geq c_{M_2}$ and give simple conditions under
which $c_{M_1} > c_{M_2}$. Our proposed $M_{2,t}$ thus converges under a faster
logarithmic cooling in this regime. The other situation that we investigate
corresponds to $c_{M_1} > c_{M_2} = 0$, where we give a class of fast and
non-logarithmic cooling schedule that works for $M_{2,t}$ (but not for
$M_{1,t}$). To the best of our knowledge this is the first instance where
strong ergodicity and convergence in relative entropy are proved for faster
than logarithmic cooling. Finally, we give an algorithm to simulate $M_{2,t}$
by uniformization of Markov chains.