The Effective Energy Transformation Scheme as a Special Continuation Approach to Global Optimization with Application to Molecular Conformation.
This paper discusses a generalization of the function transformation scheme used in Coleman, Shalloway, and Wu [Comput. Optim. Appl., 2 (1993), pp. 145--170; J. Global Optim., 4 (1994), pp. 171--185] and Shalloway [Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, 1992, pp. 433--477; Global Optim., 2 (1992), pp. 281--311] for global energy minimization applied to the molecular conformation problem. A mathematical theory for the method as a special continuation approach to global optimization is established. We show that the method can transform a nonlinear objective function into a class of gradually deformed, but ``smoother'' or ``easier'' functions. An optimization procedure can then be successively applied to the new functions to trace their solutions back to the original function. Two types of transformation are defined: isotropic and anisotropic. We show that both transformations can be applied to a large class of nonlinear partially separable functions, including energy functions  for molecular conformation. Methods to compute the transformation  for these functions are given.
Introduction
We are interested in solving the global minimization problem for molecular
conformation, especially protein folding.
How protein folds is one of the key biophysical problems of the decade.
Protein folding is fundamental for almost all theoretical studies of proteins
and protein-related life processes. It has many applications in the biotechnology
industry, notably, structure-based drug design for the treatment of
important diseases such as cancer and AIDS.
Optimization approaches to the protein folding problem are based on the
hypothesis that the protein native structure corresponds to the global minimum
of the protein energy. The problem can be attacked computationally
by minimizing the protein energy over all possible protein structures. The
structure with the lowest energy is presumed to be the most stable protein
structure.
Mathematically, for a protein molecule of n atoms, let
ng represent the molecular structure with each x i specifying the spatial
position of atom i. Then the energy minimization problem for protein folding
is to globally minimize a nonlinear function f(x) for all x 2 S, namely,
min x2S f(x); (1)
where S is the set of all possible molecular structures. The objective function
f(x) is the energy function for the protein. The usual form of f(x) is
is the pairwise energy function determined by
the distance between atoms i and j. A widely used pairwise energy
function is the Van der Waals energy function,
are all physical constants (see [2]).
Problem (1) is very difficult to solve in general. The reasons are as fol-
lows: First, in theory even simple versions of the problem have been proved
to be NP-complete [9]. Second, in practice the objective function often contains
exponentially many local minimizers; therefore, search for the global
minimizer can be computationally intractable. Third, the protein molecules
tend to be very large, typically containing O(10,000) atoms. For such large
problems, the required computation is unaffordable using general global optimization
methods.
However, because of its great practical importance, Problem (1) has been
studied intensively in many areas of computational science and optimiza-
tion. New algorithms on both sequential and parallel machines have been
developed; a variety of small to medium sizes of problems have been studied
[3, 4, 5, 6, 11, 12, 13, 14, 15, 17, 18, 19, 20]. In recent efforts smoothing
techniques are specifically designed for molecular conformation via global
minimization. Examples include the diffusion equation method [11, 14], the
packet annealing method [17, 18], as well as the effective energy simulated
annealing method [4, 5]. The basic idea behind these methods is to use special
techniques to smooth a given energy function so that search for a global
minimizer becomes more tractable. The methods usually use function transformation
schemes to transform a given energy function into a class of new
functions. A solution tracing procedure is then applied to the new functions
to locate a solution for the original function.
In this paper, we discuss an important generalization of the effective energy
transformation scheme introduced in [4, 5, 17, 18]. Instead of applying
the transformation to the probability distribution function, we now transform
the functions directly, generalizing the method to a broader class of
functions. More important, with this generalization, a mathematical theory
for the transformation as a special continuation approach to global optimization
is established. We show that the method can transform a nonlinear
objective function into a class of gradually deformed, but "smoother" or
"easier" functions. An optimization procedure can then be applied to the
new functions successively, to trace their solutions back to the original func-
tion. Two types of transformation are defined: isotropic and anisotropic.
We show that both transformation types can be applied to a large class of
nonlinear partially separable functions which includes typical energy functions
for molecular conformation. Methods to compute the transformation
for these functions are given.
The paper is organized as follows. Section 2 introduces the basic approach
and describes the function transformation method. Section 3 studies
the mathematical properties of the transformation as a special continuation
process. Section 4 characterizes the "smoothness" property and shows that
the transformed function becomes "smoother" in the sense that the small
high-frequency variations in the original function are averaged out after the
transformation. The numerical applicability of the transformation is discussed
in Section 5. The transformation is extended to the anisotropic type
in Section 6. The formulas to compute the transformation for molecular
conformation energy functions are derived. Finally, Section 7 contains concluding
remarks.
2 The Approach
In this section, we describe our function transformation idea which, in turn,
defines our basic approach to global optimization.
Suppose that we have a "poorly-behaved" nonlinear function with many
local minimizers. Because of "nonsmoothness," this type of function can be
very hard to minimize either locally or globally. To overcome this difficulty,
we suggest using a special technique to transform the objective function into
a class of gradually deformed, but "smoother" or "easier" functions. An optimization
procedure can then be applied to these new functions successively,
to trace their solutions back to the original function.
To deform the function, we define a parametrized integral transformation
as follows:
Given a nonlinear function f , the transformation
f is defined such that for all x,
Z
or equivalently;
Z
where - is a positive number and C - is a normalization constant such that
Z
Note that in contrast to the approaches in [4, 5, 17, 18], the transformation
here applies directly to the given function instead of its probability
distribution. This approach simplifies the transformation, and also makes it
much easier to compute and analyze.
To understand this transformation, consider that, given a random function
distribution function p(x 0 ) for the random variable
the expectation of the function g with respect to p is
Z
In light of (7), the transformation (4) yields a function value for
any x equal to the expectation for f sampled by a Gaussian distribution
function centered at x.
For example, consider the following nonlinear function:
which is a quadratic function augmented with a "noise" function. The transformation
for this function can be computed:
The function value fixed x is equal to the integration with
respect to the product of two functions, the original function f(x 0 ) and the
Gaussian distribution function p(x 0

Figure

(a)). The
parameter - determines the size of the dominant region of the Gaussian.
Since the most significant part of the integration is that within the dominant
region of the Gaussian, !f? - (x) can be viewed as the average value for the
original function f within a small -neighborhood around x. If - is equal to
zero, the transformed function is exactly the original function. For positive
-, the original function variations in small regions are averaged out, and the
transformed function will become "smoother" (Figure 1 (b)).

Figure

shows how the function behaves with increasing
-. Observe that when 0:0, the function is the original function; when
we increase - to 0.1, the function becomes "smoother;" when - is increased
further to 0.2, the function becomes entirely "smooth."

Figure

3 illustrates what the transformation implies for optimization. A
standard optimization procedure, the quasi-Newton method, is applied to
(a)

Figure

1: A one dimensional transformation example

Figure

2: A class of gradually deformed functions
the three functions in Figure 2. Figure 3 (a), (b), and (c) contain the corresponding
solutions x   obtained with different choices of initial guesses x ffi .
Although globally convergent, the method may not find the right solution
if the "noise" is large. So for the function in Figure 2 (c), the method converged
to the right solution only when the initial guess was close enough to
the solution. When the initial guess was far from the solution, the method
failed to find the right solution (Figure 3 (c)). For the function in Figure 2
(b), although it is "smoother," the behavior of the method is essentially
unchanged. However, for the function in Figure 2 (a), the method always
converged to the right solution (Figure 3 (a)). If we apply the procedure to
the functions in Figure 2 (a) to (c) successively, and at each step take the
solution for the previous function as the starting point, the solutions for all
these functions can then be obtained.
The experiment above suggests a general global optimization method: to
optimize a difficult function, use the transformation technique to deform the
function into a class of "smoother" or "easier" functions, and then apply an
optimization procedure to the functions successively, to trace their solutions
back to the original function.
Continuation
What is the difference between the suggested approach and general homotopy
methods? The answer is that this approach is indeed a special type of
homotopy method. But the transformation is different from conventional ho-
motopies, and has the following three special features: First, the transformed
functions are not arbitrarily deformed functions. They all are approximations
to the original function in the sense that they are coarse estimates. Second,
the transformation is defined by a special parametrized integral transforma-
tion. If we increase the value of the parameter, the transformed function
will become "smoother" with small variations gradually removed, but maintaining
the overall function structure. Finally, if we apply an optimization
procedure to a transformed function, the obtained solution usually is close to
the solution for the original function. All these features are good for global
optimization (also for robust local optimization), but are not necessarily the
properties of conventional homotopies.
We show in the following that the proposed transformation is indeed
x*
(a)
x*
(b)
x*
(c)

Figure

3: The solutions for the functions in Figure 2 obtained by the quasi-Newton
method with different initial guesses
a well-defined homotopy and determines for any initial solution a unique
solution curve containing the stationary points for the transformed functions.
Assumption 1 The objective function f is twice continuously differentiable,
and the transformation (4) is well defined for the function as well as all its
derivatives.
Assumption 2 Let g be the gradient of f , and \Delta the Laplace operator
Then the operation \Delta can be applied to g, and the transformation (4) is well
defined for all derivatives involved. Also, \Deltag(x) is uniformly bounded and
satisfies a Lipschitz condition:
Assumption 3 The transformation !r 2 f ? - (x) satisfies a Lipschitz condition

and its inverse is uniformly bounded.
Note that to guarantee Assumptions 1 to 3, a sufficient condition on
f is that f and its derivatives are all integrable in terms of parametrized
integration (4).
We first state two sets of standard results for the proposed transformation
in the following lemmas without proof.
Assumption 1, 8-; x,
Assumption 1, 8x,
lim
lim
lim
For convenience, we define a function h(-; x), - 2 \Gamma, and x 2 S such that
is a vector space. With this
definition, the condition for x to be a stationary point of
x
Theorem 1 and h be defined as in (18). Then under
Assumptions 1 and 2, h 00
x-
exists and is uniformly bounded for all
and x 2 S, and also satisfies a Lipschitz condition in x:
In addition,
x-
Proof: Let p(-; x) be the Gaussian distribution function defined as follows:
-). Then by the definition of !f? - ,
Z
By Lemma 1,
x
Z
After differentiating (24) with respect to -, it follows that
Z
\Gamma-
Z
where
Z
Z
It is easy to verify that
Also note that
Z
Z
Therefore,
Replacing by (31), we see that
By Assumption 2, ! f 000 ? - (x) is well defined and uniformly bounded.
x-
exists and is uniformly bounded for all
f 000 (x) satisfies a Lipschitz condition by Assumption 2,
satisfies a Lipschitz condition:
immediately. So h 00
x-
(-; x) satisfies a Lipschitz
condition in x. 2
Theorem 2 Let f : R n ! R and h be defined as in (18). Then under
Assumptions 1 and 2, h 00
x-
exists and is uniformly bounded for all
and x 2 S, and also satisfies a Lipschitz condition in x:
In addition,
x-
\Deltag ? -
Proof: Let p n (-; x) be the Gaussian distribution function
where c n
-) n . Then by the definition of !f ? - ,
Z
By Lemma 1,
x
Z
Differentiate (38) with respect to - to obtain
Z
where
Z
Z
Z
Z
Z
where
Z
Z
From the proof of Theorem 1,
Substitute (44) back into (41) to obtain
Then
n- 2!g? - (x) (46)
and
Similar to the proof of Theorem 1, it follows immediately that h 00
x-
exists and is uniformly bounded for all - 2 \Gamma and x 2 S, and also satisfies a
Lipschitz condition in x. 2
Finally, we state and prove the main theorem in this section as follows:
Theorem 3 Let f be a function for which Assumptions 1, 2, and 3 all hold.
Then for any stationary point x 0 of there is a continuous and
differentiable curve x(- 2 \Gamma, such that x
stationary point of !f? - . The curve x(-) is also the unique solution of the
initial value problem
Proof: Since x 0 is a stationary point of !f? - 0
By Assumptions 1, 2, 3, Lemmas 1, 2, and Theorem 2, function h 0
x
is continuously
differentiable at all (-; S. So by the Implicit Function
Theorem, there is a continuously differentiable function x(-) at a neighborhood
of - 0 , such that x
x
for all - in the neighborhood.
We now show that x(-) also is defined uniquely in \Gamma.
By differentiating (51), we see that x(-) is a solution to the initial value
problem:
xx
x-
which, by Lemma 1 and Theorem 2, is equivalent to the problem (48)-(49).
Then it suffices to show that the right-hand side of (52) satisfies a Lipschitz
condition in x on \Gamma \Theta S, which guarantees a unique solution x(-) in \Gamma by
standard ordinary differential equation theory [10].
Under Assumption 3, for h 00
xx
xx
By Theorem 2, for h 00
x-
x-
Let
xx
x-
Then it is easy to verify that G(-; x) satisfies a Lipschitz condition in x on
with which completes the proof. 2
4 Smoothness
In Section 2 we illustrated that the transformed functions are "smoother"
than the original function in the sense that they vary slower and may even
have fewer local minimizers. In the following, we characterize more rigorously
the "smoothness" of the transformation.
f be the Fourier transformation for function f , and d
!f? - for function
Recall that the transformation !f ? - for f is just a convolution of
f and p, where p is the Gaussian distribution function
Therefore, the Fourier transformation of ! f ? - is equal to the product of
the Fourier transformations of f and p. The Fourier transformation of the
Gaussian distribution function is
where ! is the frequency. So, we have
d
We see from (62) that if - ! 0, then d
converges to -
f , and
converges to f . This is exactly the fact we stated in Lemma 2.
Also by (62), d
will be very small if ! is large and - is fixed.
This implies that high-frequency components of the original function become
very small after the transformation. This is why the transformed function is
"smoother." In addition, for larger - values, wider ranges of high-frequency
components of the original function practically vanish after the transforma-
tion, and therefore the transformed function becomes increasingly smooth as
increases. We state these properties formally in the following theorem.
Theorem 4 Let f , -
all be given and well defined.
fixed -, such that 8! with k!k ? ffi,
f (!)j
fixed -, let
(1=")=-. Then 8! with
": (64)From this theorem we learn that the relative size of d
can be
made arbitrarily small for all ! with k!k greater than a small value ffi. Since ffi
is inversely proportional to -, high-frequency components are removed when
- is large.
5 Numerical Applicability
The definition of the transformation (4) involves high-dimensional integration
which cannot be computed in general (except perhaps by the Monte Carlo
method, which is not appropriate for our purposes because it is too expen-
sive). So the transformation may not be applicable to arbitrary functions, at
least numerically. However, this transformation is computationally feasible
for a large class of nonlinear partially separable functions, and especially to
typical molecular conformation and protein-folding energy functions.
We state several useful properties of the transformation in the following:
First, for the sum of functions
the transformation of f is equal to the sum of the transformations of the f i 's:
Second, for the product of functions
Y
where the g i 's do not share common variables, the transformation of g is
equal to the product of the transformations of the g i 's:
Y
Finally, for a large subclass of nonlinear partially separable functions,
called the generalized multilinear functions,
Y
where the g i
j 's are one-dimensional nonlinear functions, we have
Y
involves only one-dimensional
integration, the transformation for a generalized multilinear function can be
computed using a standard quadrature rule.
In particular, let us consider a typical n-atom molecular conformation
energy function,
ng and h ij is the pairwise energy function
determined by the distance between atoms i and j. By (66), the
transformation of this energy function is equal to the sum of the transformations
of the pairwise energy functions. However, the computation for the
transformation still cannot be carried out directly, because there is
still more than one variable in each term. Nevertheless, the following theorem
provides a feasible way to compute the molecular energy transformation:
Theorem 5 Let f be defined as in (71). Then the transformation of f can
be computed using the formula
Z
Proof: We show the case when x 8i. The general case can be proved
similarly.
By the definition of !f? - , in form (5), for any x,
Z
where c - is such that
Z
Make the following variable transformation:
Then it is easy to verify that
Z
-Z
Z
(77)The integral for
involves only variable r ij and can be
computed with a standard numerical integration technique; therefore, the
transformation !f ? - (x) can be computed in this fashion.
Note that the integral for !f ? - (x) must exist, for otherwise the transformation
will have no definition. In practice, if the integral for a given f
does not exist, a modified function may need to be considered instead. For
example, the energy function given in (3) cannot be integrated directly because
the function goes to infinity when r ij becomes very small. Usually, this
can be cured by replacing the function for small r ij with finite interpolation
(see [4, 11, 17]).
Note also that the result in Theorem 5 applies only to energy functions
that can be formulated in form (71). Most popularly used energy functions
for molecular conformation and protein folding can be expressed as pairwise
forms, for example, the Lennard-Jones potential, the electrostatic potential,
the interaction potential for bonded atoms, etc. [2, 16]. However, some energy
functions do contain terms that are not pairwise distance functions; for
instance, the torsional potential usually is given as a function of the dihedral
angle. Special approximation techniques may be needed to transform this
type of function, We will not address this issue in this work.
6 Anisotropic vs. Isotropic
The transformation we have discussed so far is of the isotropic type in the
sense that it averages function variations equally along all directions in the
variable space. In practice, we might wish to average different sizes of function
variations along different directions (i.e., use different - values for different
variables) in order to obtain a more accurate overall structure of the
function. For this purpose, we can define a more general transformation,
called the anisotropic transformation.
Given a nonlinear function f , the anisotropic transformation
!f?   for f is defined such that for all x,
Z
or equivalently;
Z
where   is a diagonal matrix with positive diagonal elements:
and C
with c - i
determined such that
Z
Note also that in this definition,
From this definition, we see that the anisotropic transformation will be
reduced to the isotropic transformation when the diagonal elements of   are
all identical.
Many of the important properties of the isotropic transformation carry
over to the anisotropic case. We state these properties in the following:
First, for the sum of the functions
we have
Second, for the product of the functions
Y
where the g i 's do not share common variables, we have
Y
where   i 's are small diagonal matrices. If g i is a function of j variables
positive numbers - i
.
Third, for the generalized multilinear functions,
Y
where the g i
j 's are one dimensional nonlinear functions, we have
Y
We can also derive a simple formula to compute the anisotropic transformation
for the molecular conformation energy function:
Theorem 6 Let f be defined as in (71). Then the anisotropic transformation
of f can be computed using the formula
Z
k)e
Proof: We show only the case when x 8i. The general case can be
proved similarly.
By the definition of !f?   , in form (79), for any x,
Z
is such that
Z
Make the following variable transformation:
Then we have
Using these relations we can verify that
Z
Z
which completes the proof. 2
The anisotropic transform determines for any initial solution a unique
solution function x(-) for the transformed functions, and therefore can also
be used as a continuation process for optimization, more general and powerful
than the isotropic transform. We state these results in Theorem 7 and 8. The
details for the proof are quite similar to those for Theorem 2 and 3, so we
will not present them.
Parallel to Assumptions 1, 2 and 3 for Theorem 2 and 3, we make the
following assumptions:
Assumption 4 The objective function f is twice continuously differentiable,
and transformation (78) is well defined for the function as well as its derivatives

Assumption 5 Let g be the gradient of f , and \Psi an operator,
Then the operation \Psi can be applied to g, and \Psig is a matrix with
Transformation (78) is well defined for all derivatives involved in \Psig. Also,
\Psig(x) is uniformly bounded and satisfies a Lipschitz condition:
Assumption 6 The transformation !r 2 f ?   (x) satisfies a Lipschitz condition

and its inverse is uniformly bounded.
Let S be a vector space, and for a positive vector -
we define function h(-; x) such that 8(-;
where - is the diagonal vector of  , that is,
Theorem 7 Let f be a given function and h be defined as in (101). Then
under Assumptions 4 and 5, h 00
x-
exists and is uniformly bounded for all
also satisfies a Lipschitz condition in x:
x-
x-
In addition,
x-

Theorem 8 Let f be a function for which Assumptions 4, 5, and 6 all hold.
Then for any stationary point x 0 of there is a
continuous and differentiable function x(- 2 \Gamma, such that x
is a stationary point of !f ?   . The function x(-) is also the
unique solution of the initial value problem

7 Concluding Remarks
In this paper, we have discussed a generalization of the effective energy transformation
scheme used in [4, 5, 17, 18] for the global energy minimization
applied to molecular conformation. Instead of applying the transformation
to the probability distribution, here we transform the functions directly, generalizing
the scheme in [4, 5, 17, 18] to a broader class of functions. A
mathematical theory for the transformation as a special continuation approach
to global optimization is established. We have established that the
proposed method transforms a given nonlinear objective function into a class
of gradually deformed, but "smoother" or "easier" functions. A continuation
procedure can then be applied to these "smoother" or "easier" functions, to
trace their solutions back to the original function. Two types of transformation
are defined: isotropic and anisotropic. We have demonstrated that both
transformation types can be applied to a large sub-class of nonlinear partially
separable functions, and in particular, the energy functions for molecular con-
formation. Methods to compute the transformation for these functions are
given.
We believe that the proposed method provides a powerful and effective
tool for global or robust local optimization. We can see this partially from the
work in [4, 5], which can be viewed as a special application of the method.
In [4, 5], the transformation method, combined with simulated annealing,
was applied to the global energy minimization problem for molecular confor-
mation. Promising results were observed even if only simple algorithms and
approximated transformation were implemented.
More numerical work will be done in our future research. We will implement
a group of algorithms based on the theory presented in this paper.
While the transformation can now be computed with provided formulas, tracing
the solution curve can be carried out using advanced numerical methods.
There are at least three choices for the implementation of the tracing procedures

1. Use a general random search procedure to trace the changes of the
global solution when the transformed function is gradually changed
back to the original function.
2. Apply only local optimization procedures to each transformed function
to trace a set of solution curves, and choose the best among all solutions
obtained.
3. Solve the initial value problems for a set of solution curves, and choose
the best solution.
The first method is similar to the approach in [4, 5] where a simulated
annealing procedure was applied to the transformed functions. This method
converges to the global solution with certain probability, but a large number
of random trials usually are required to obtain the convergence. The
second approach is the most simple and efficient method, but the solution
curves to be traced must be selected cleverly, for otherwise the global solution
will not be guaranteed. The third method provides a more accurate and
reliable way to trace the solution curves. As we have shown in this paper,
the curves are solutions to well defined initial value problems. So standard
numerical IVP-methods can be used (e.g., predictor-corrector methods) [1].
The implementation of all three tracing procedures and the numerical comparison
among them will be of great interest for the further development of
the algorithms.
We are especially interested in applying these methods to the global energy
minimization problems for molecular conformation, especially protein
folding. A set of test problems will be considered including the Lennard-Jones
microcluster conformation problem, the distance geometry problem,
and several protein conformation problems.
While searching for native structures of protein molecules is certainly
very important, the proposed methods can also provide information about
the paths that solutions follow. Such information may contain insights about
how protein molecules change from arbitrary configurations to their native
structures.

Acknowledgments

This research was supported partially by the Cornell Theory Center, which
receives funding from members of its Corporate Research Institute, the National
Science Foundation (NSF), the Advanced Research Projects Agency
(ARPA), the National Institutes of Health (NIH), New York State, and IBM
Corporation.
The author thanks Lizhi Liao, Michael Todd, Lloyd Trefethen, and Wei
Yuan for constructive suggestions. He especially thanks Thomas Coleman
for many discussions relating to this work and for his helpful comments and
suggestions on the manuscript, and David Shalloway for many discussions on
the protein-folding problem as well as the original effective energy transformation
ideas.



--R

Allgower and Kurt Georg
Brooks III


David Shalloway and Zhijun Wu
David Shalloway and Zhijun Wu




David Kincaid and Ward Cheney







David Shalloway
David Shalloway


--TR

--CTR
Olivier Chapelle , Mingmin Chi , Alexander Zien, A continuation method for semi-supervised SVMs, Proceedings of the 23rd international conference on Machine learning, p.185-192, June 25-29, 2006, Pittsburgh, Pennsylvania
Jorge J. Mor , Zhijun Wu, Distance Geometry Optimization for Protein Structures, Journal of Global Optimization, v.15 n.3, p.219-234, October 1999
Mark S. Lau , C. P. Kwong, A Smoothing Method of Global Optimization that Preserves Global Minima, Journal of Global Optimization, v.34 n.3, p.369-398, March     2006
Jack Dongarra , Ian Foster , Geoffrey Fox , William Gropp , Ken Kennedy , Linda Torczon , Andy White, References, Sourcebook of parallel computing, Morgan Kaufmann Publishers Inc., San Francisco, CA,
integral transformation;global/local minimization;continuation methods;molecular conformation