678
I Optimization Techniques
r
= r −
∇f
|∇f |
δ.
(I.9)
The value of δ should be taken small enough that one does not ‘overshoot’ the
minimum, such as δ = (1/2)|∇f |/(|∇ 2 f | + ε 2 |.
3. Repeat the δ shifts until the gradient ∇f is with a specified tolerance of zero or a
boundary of the function is reached. If not a boundary point, test that ∇ 2 f > 0.
If a boundary has been reached, test if f at the boundary point, f B , is smaller
than f B + |∇f |δ. If so, the boundary location is a minimum point of f .
4. Record the minimum position r m , and also the value of f m = f (r m ) there.
5. Repeat this process for other locations in the phase space, either picked with
some foreknowledge, such as with a known probability distribution for r across
phase space, or at ‘random’ positions. 2
6. When the tests have densely ‘peppered’ the phase space, stop.
7. Now compare the values of f at its minima to see which one (or ones) is (or are)
smaller than the rest.
When the number of possible configurations of a system we want to optimize is
astronomically large, we are driven to formulate optimization strategies. The folding
of proteins is a good example, because the number of possible bond rotations and
bond flexing can be in the googols. In the ‘extreme optimization’ scheme, 3 searches
for the minimum energy configurations are narrowed by knowledge of the energy
of backbone configurations and of various rotamer possibilities for segments of
the protein. The presence of steric or chemical catalytic agents, such as particular
molecules, ions, or surfaces, may strongly limit possibilities. Also, the path a
particular natural amino-acid chain follows from secondary to tertiary structure has
an evolutionary history. More complex structures may have evolved from simpler
ones, or iteration of simpler ones. In searches for these natural cases, the full phase
space of possible configurations does not need to be explored, but only those paths
near those discovered by natural systems in biological evolution.
An any case, choices for changes in the next configuration to be tested can come
from a power-law probability distribution of the largest to the smallest local energies
along the protein chain.
2 A random selection produces the so-called Monte Carlo method.
3 See, for example, Naigong Zhang and Chen Zeng, Reference Energy Extremal Optimization as a
Stochastic Search Algorithm Applied to Computational Protein Design, Journal of Computational
Chemistry 29:11, 1762–1771 (2008).
I Optimization Techniques
r
= r −
∇f
|∇f |
δ.
(I.9)
The value of δ should be taken small enough that one does not ‘overshoot’ the
minimum, such as δ = (1/2)|∇f |/(|∇ 2 f | + ε 2 |.
3. Repeat the δ shifts until the gradient ∇f is with a specified tolerance of zero or a
boundary of the function is reached. If not a boundary point, test that ∇ 2 f > 0.
If a boundary has been reached, test if f at the boundary point, f B , is smaller
than f B + |∇f |δ. If so, the boundary location is a minimum point of f .
4. Record the minimum position r m , and also the value of f m = f (r m ) there.
5. Repeat this process for other locations in the phase space, either picked with
some foreknowledge, such as with a known probability distribution for r across
phase space, or at ‘random’ positions. 2
6. When the tests have densely ‘peppered’ the phase space, stop.
7. Now compare the values of f at its minima to see which one (or ones) is (or are)
smaller than the rest.
When the number of possible configurations of a system we want to optimize is
astronomically large, we are driven to formulate optimization strategies. The folding
of proteins is a good example, because the number of possible bond rotations and
bond flexing can be in the googols. In the ‘extreme optimization’ scheme, 3 searches
for the minimum energy configurations are narrowed by knowledge of the energy
of backbone configurations and of various rotamer possibilities for segments of
the protein. The presence of steric or chemical catalytic agents, such as particular
molecules, ions, or surfaces, may strongly limit possibilities. Also, the path a
particular natural amino-acid chain follows from secondary to tertiary structure has
an evolutionary history. More complex structures may have evolved from simpler
ones, or iteration of simpler ones. In searches for these natural cases, the full phase
space of possible configurations does not need to be explored, but only those paths
near those discovered by natural systems in biological evolution.
An any case, choices for changes in the next configuration to be tested can come
from a power-law probability distribution of the largest to the smallest local energies
along the protein chain.
2 A random selection produces the so-called Monte Carlo method.
3 See, for example, Naigong Zhang and Chen Zeng, Reference Energy Extremal Optimization as a
Stochastic Search Algorithm Applied to Computational Protein Design, Journal of Computational
Chemistry 29:11, 1762–1771 (2008).