I Optimization Techniques
677
I.2 Optimization Through Iterative Searches
It often occurs that the optimization of a function f (x 1 , x 2 , · · · , x N ) ≡ f (r) leads
to a system of equations that cannot be solved analytically. Also, the value of the
function may be only given at discrete points, and may exist over wide ranges of
numerous variables. In these cases, an iterative technique may be employed to find
the minima of the function. (The space spanned by the values of r will be called the
phase space of f .)
If f is known analytically, the process is simpler than the case of discrete data
for f . In fact, fitting the data first to a known analytic function can improve the
search, since the ‘true’ extrema of f may occur between points in the data set.
The choice of the fitting function should be based on any information known about
the nature of the data, or, if there is none, one can always represent the data as an
expansion into a series of orthonormal functions with the same boundary conditions
as the data. The expansion coefficients become the parameters of the fit.
Fitting is done by adjusting the parameters in the fitting function
ϕ(x 1 , x 2 , · · · , x N ; α 1 , α 2 , · · · , α n )
to minimize the sum of the square of the differences between the fit and the data
at the discrete locations where f is known, with each term in the sum weighted by
the square of the inverse of the standard deviations of the data. 1 If the number of
parameters n in the fitting function is far less than the number of data points, then we
say that the fit is a ‘good’ model of the data. Some caution must be observed in fitting
if the data has uncertainty: Forcing the fit to data not on a ‘smooth’ representation
of that same data may create unnatural kinks or even singularities in the fit between
the data.
If one wishes the ‘raw’ data to be searched, rather than first fitting that data,
then the derivatives indicated below should be replaced by their discrete expressions
across the known locations of the data. For example, ∇ i f ≈ (f (r + δ) − f (r))/δ i ,
where δ is a small displacement connecting two nearby points in the phase space.
The iteration idea is this:
1. Pick a likely point in the phase space to be near a minimum of f , or, if there
is no criteria to know of a likely point, use a ‘randomly’ picked position r =
[x 1 , x 2 , · · · , x N ].
2. Find ∇f (either analytically or numerically). If the gradient is zero to within a
selected tolerance, an extremum has been found. If not, shift to a new position r
toward −∇f , i.e. follow f ‘down hill’:
1 This ‘method of least squares’ was shown by Gauss to be optimal when the errors in the data
come from ‘random’ fluctuations.
677
I.2 Optimization Through Iterative Searches
It often occurs that the optimization of a function f (x 1 , x 2 , · · · , x N ) ≡ f (r) leads
to a system of equations that cannot be solved analytically. Also, the value of the
function may be only given at discrete points, and may exist over wide ranges of
numerous variables. In these cases, an iterative technique may be employed to find
the minima of the function. (The space spanned by the values of r will be called the
phase space of f .)
If f is known analytically, the process is simpler than the case of discrete data
for f . In fact, fitting the data first to a known analytic function can improve the
search, since the ‘true’ extrema of f may occur between points in the data set.
The choice of the fitting function should be based on any information known about
the nature of the data, or, if there is none, one can always represent the data as an
expansion into a series of orthonormal functions with the same boundary conditions
as the data. The expansion coefficients become the parameters of the fit.
Fitting is done by adjusting the parameters in the fitting function
ϕ(x 1 , x 2 , · · · , x N ; α 1 , α 2 , · · · , α n )
to minimize the sum of the square of the differences between the fit and the data
at the discrete locations where f is known, with each term in the sum weighted by
the square of the inverse of the standard deviations of the data. 1 If the number of
parameters n in the fitting function is far less than the number of data points, then we
say that the fit is a ‘good’ model of the data. Some caution must be observed in fitting
if the data has uncertainty: Forcing the fit to data not on a ‘smooth’ representation
of that same data may create unnatural kinks or even singularities in the fit between
the data.
If one wishes the ‘raw’ data to be searched, rather than first fitting that data,
then the derivatives indicated below should be replaced by their discrete expressions
across the known locations of the data. For example, ∇ i f ≈ (f (r + δ) − f (r))/δ i ,
where δ is a small displacement connecting two nearby points in the phase space.
The iteration idea is this:
1. Pick a likely point in the phase space to be near a minimum of f , or, if there
is no criteria to know of a likely point, use a ‘randomly’ picked position r =
[x 1 , x 2 , · · · , x N ].
2. Find ∇f (either analytically or numerically). If the gradient is zero to within a
selected tolerance, an extremum has been found. If not, shift to a new position r
toward −∇f , i.e. follow f ‘down hill’:
1 This ‘method of least squares’ was shown by Gauss to be optimal when the errors in the data
come from ‘random’ fluctuations.