% proposal.tex
% LaTeX template for REU93 proposals
% 1993 npac reu program
% 22 june 1993

\documentstyle[leqno,twoside,11pt,ltexproc]{article}
\setlength{\oddsidemargin}{+1in}
\setlength{\evensidemargin}{+.6in}
\setlength{\topmargin}{+5mm}
\raggedbottom

\begin{document}
\cleardoublepage
\pagestyle{myheadings}


\title{\bf Efficient Global Optimization Using Simulated Annealing and
Simulated Tempering 
\thanks{
 Project proposed as part of the 1993 Research Experiences for 
 Undergraduates (REU) Program
 in High-Performance Computing conducted by the Northeast Parallel
 Architectures Center (NPAC) at Syracuse University.  The National
 Science Foundation provides primary funding for the 1993 NPAC REU
 Program, through NSF Grant CDA-9200577.  Additional funding is provided by
 the GE Foundation Faculty for the Future Program; the
 Vice President for Research and Computing, the Dean of the
 College of Engineering and Computer Science, the Dean of the
 College of Arts and Sciences, and NPAC, Syracuse University.}}

\author{Matthew Shore\thanks{Research Apprentice, 1993 NPAC REU Program;
Majors: Computer Science, Music, Florida State University.}
\and Paul Coddington\thanks{Project Leader, Northeast Parallel
Architectures Center (NPAC), Syracuse, NY.}}
\date{\it Proposal for a 1993 NPAC REU Project}
\maketitle

% The following places author's name next to page number on even pages and
% title on odd pages.
\markboth{Shore \& Coddington}{Efficient Global Optimization using
Simulated Annealing and Simulated Tempering}

\begin{abstract}

An investigation of efficient global optimization schemes for systems
with many coexisting states is proposed.  A special class of
algorithms will be examined based on a technique known as {\em
simulated annealing}.  Particular consideration will be given to {\em
simulated tempering}, a novel algorithm with promising performance
capabilities.  A broad testbed of relevant optimization problems,
including the Traveling Salesman Problem and the the Ising Spin Glass
Model, will be provided for a thorough evaluation of the resulting
optimization methods.

\end{abstract}


\section{Introduction}

Global optimization, also known as multivariate and combinatorial
optimization, is a technique for minimizing complex functions
dependent on many parameters.  The tremendous amount of attention
given to this problem is not surprising in light of its significance
for a vast array of disciplines \cite{Ingber}.  {\em Simulated
annealing} is one approach to evolve from this influx of
research.  It was introduced as a Monte Carlo method for evaluating
large--dimensional integrals arising in statistical physics problems
\cite{Metropolis} and later generalized for optimization.  (See
\cite{Ingber} for an overview of applications.)

The premise for {\em simulated annealing} is a detailed analogy with
annealing in solids.  The physical process involves first heating a
substance, e.g. steel, and then slowly cooling it to prevent cracking.
{\em Simulated annealing} introduces a symbolic temperature scale,
sometimes known as an annealing schedule, according to which the
system is ``cooled'' with minimal deviations from equilibrium.  (The
term {\em system} is used loosely, as this methodology is, in fact, a
general one.  For example, it can refer to a collection of cities in
the Traveling Salesman Problem or to a group of units in complex
circuit design.)  The algorithm is straightforward and can be
summarized as follows.

\pagebreak
%\vspace{0.3in}
\begin{quote}
{\em
Initialize state of system at ``time'' t, X(t) \\
\begin{enumerate}
  \item Randomly choose a new configuration $\eta$ 
  \item Compute energy change 
	$\Delta\varepsilon = \varepsilon(\eta) - \varepsilon(X(t))$ 
  \item Compute probability distribution 
	$q = \frac{\pi(\eta)}{\pi(X(t))} = e^{-\beta\Delta\varepsilon}$ 
  \item If $q > 1$ then \{X(t+1) = $\eta$; thermalize\footnote{{\em
Thermalization} refers to the process of returning the system to
equilibrium.}  system \}
  \item Else accept $\eta$ with probability $q$
  \item go to 1.
\end{enumerate}}

Steps 3 and 4 can be restated in an intuitive fashion.  If the energy
of the system in a new configuration, $\varepsilon(\eta)$, is less
than the energy at {\em X(t)}, $\varepsilon(X(t))$, the new
configuration is accepted.  Otherwise, its acceptance is determined
probabilistically.  This sequence is especially significant, as it is
responsible for keeping the sampling scheme from getting stuck in
local minima.

\end{quote}
\vspace{0.3in}

Theoretically, {\em simulated annealing} presents a truly salient
attribute -- a probabilistic guarantee of an optimal solution
\cite{Geman}.  Unfortunately, one is forced to adhere to a logarithmic
annealing schedule, i.e. decrease the temperature logarithmically,
which in practice is seldom feasible (due to large problem size, for
instance).  A common practice is to employ an exponential annealing
schedule instead, even though the possibility of obtaining an optimal
solution is greatly reduced.  At any rate, the underlying concepts
behind {\em simulated annealing} are encouraging and merit further
investigation. 

Several attempts have been made to produce better {\em simulated
annealing}--type algorithms.  {\em Simulated tempering}
\cite{Marinari}, for instance, appears to be especially promising.
The characteristic feature of this approach is that it eliminates the
need for thermalization, as the system remains in equilibrium as the
``cooling'' process takes place.  This is achieved by enlarging the
system configuration, {\em X}, by introducing a new discrete variable
{\em m}.  The probability distribution {\em P(X,m)} retains the nature
of the original distribution as the following formulation suggests.

\vspace{0.15in}
\begin{center} $P(X,m) \propto e^{-H(X,m)}$, \end{center}
\hspace{2in} where \\
\begin{center} $H(X,m) \equiv \beta_{m}H(X) - g_{m}$. \end{center}
\vspace{0.15in}

It is important to note that $\beta$'s can take arbitrary values which
are assigned {\em a priori}.  Thus, with a reasonable acceptance rate,
a broader exploration of local minima is allowed \cite{Marinari}.
Several issues still require consideration, however.  For instance,
{\em Simulated tempering} requires initial parameters which are
currently obtained using the relatively slow {\em simulated annealing}
method.  In addition, this approach has been tested in a very limited
scope \cite{Marinari} and subsequent analysis is necessary to determine
whether it can be generalized to other problems.


\section{Proposed Work}

Three general avenues of research are proposed.  Firstly, considerable
effort will be devoted for the enhancement of the existing {\em
simulated annealing} algorithm.  We propose to develop a faster
algorithm, which will, in fact, generate an optimal solution.
Secondly, an in--depth study of the {\em simulated tempering} approach
will be conducted.  New methods for acquiring initial parameters are
strong candidates for investigation.  One possibility is a
probabilistic technique for accurate prediction of the cost function,
$\beta_{m+1}${\em H(X)}, based on previous $\beta$ values,
$\beta_{0},\beta_{1},\dots,\beta_{m}$.  Furthermore, since the
underlying premise of {\em simulated tempering} is to preserve the
equilibrium of the system, it is quite likely that a rigorous proof to
show that an otimal solution is reachable can be developed.  Indeed,
this would provide working guidelines for future implementation and
study.  Finally, these algorithms will be implemented on a massively
parallel supercomputer (DECmpp) and a testbed of {\em large}
optimization problems will be examined (e.g. the Traveling Salesman
Problem with several thousand cities and the Ising Spin Glass Model on
a 256x256 lattice).


\begin{thebibliography}{99}

\bibitem{Geman}
Geman, S. and Geman, D. {\em Stochastic Relaxation, Gibbs Distribution
and the Bayesian Restoration in images}, IEEE Trans. Patt. Anal. Mac.
Int., vol. 6, 721--741, 1984.

\bibitem{Ingber}
Ingber, L. {\em Simulated annealing: Practice versus theory},
Statistics and Computing, 1993.

\bibitem{Marinari}
Marinari, E. and Parisi, G. {\em Simulated tempering: A new Monte
Carlo scheme}, Europhys. Lett., vol. 19, 451, 1992.

\bibitem{Metropolis}
Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, E. {\em
Equation of state   calculation be fast computing machines}, J. Chem.
Phys., vol. 21, 1087--1092, 1953.

\end{thebibliography}

\end{document}



