  In this paper, we propose new Metropolis-Hastings and simulated annealing
algorithms on finite state space via modifying the energy landscape. The core
idea of landscape modification rests on introducing a parameter $c$, in which
the landscape is modified once the algorithm is above this threshold parameter
to encourage exploration, while the original landscape is utilized when the
algorithm is below the threshold for exploitation purpose. We illustrate the
power and benefits of landscape modification by investigating its effect on the
classical Curie-Weiss model with Glauber dynamics and external magnetic field
in the subcritical regime. This leads to a landscape-modified mean-field
equation, and with appropriate choice of $c$ the free energy landscape can be
transformed from a double-well into a single-well, while the location of the
global minimum is preserved on the modified landscape. Consequently, running
algorithms on the modified landscape can improve the convergence to the
ground-state in the Curie-Weiss model. In the setting of simulated annealing,
we demonstrate that landscape modification can yield improved or even
subexponential mean tunneling time between global minima in the low-temperature
regime by appropriate choice of $c$, and give convergence guarantee using an
improved logarithmic cooling schedule with reduced critical height. We also
discuss connections between landscape modification and other acceleration
techniques such as Catoni's energy transformation algorithm, preconditioning,
importance sampling and quantum annealing. The technique developed in this
paper is not only limited to simulated annealing and is broadly applicable to
any difference-based discrete optimization algorithm by a change of landscape.
