Online optimization algorithms 197
starting point and the minimum is more complex, a small noise level could
suffice to defeat the algorithm.
7.3.2 RCDS algorithm
Powell’s method is powerful for the optimization of smooth functions. However, its performance is sensitive to noise, as seen in Figure 7.7. A close examination of the algorithm reveals that the negative impact of noise comes
in through the 1-dimensional optimizer. For both the golden section method
and the inverse quadratic interpolation method, the first step is to bracket the
minimum within a finite zone. The bracketing procedure relies on the comparison of function values at the boundary points and a point inside. Noise
in the function values can change the comparison results and lead to a false
bracket. Noise can also change the next step of the 1-dimensional optimizer.
For the golden section method, it changes the selection of the subdivision to
move in; for the inverse interpolation method, it changes both the prediction
of the trial solution and the selection of the subdivision.
The 1-dimensional optimizers suffer from noise because they have no consideration of the existence of the noise. Small changes to the optimizers could
significantly suppress the noise effect. The robust conjugate direction search
(RCDS) [57] algorithm makes the 1-dimensional optimizer aware of the noise
level and takes measures to ensure the decisions in the bracketing and interpolation steps are valid under noise. The resulting 1-dimensional optimizer is
called the robust line optimizer. It is substantially more robust against noise.
Starting from the present solution, g 0 = g(α = 0), the robust line optimizer first finds the boundary in one direction (say, the positive direction)
by sampling new solutions with increasingly longer steps. The step length is
increased by a factor of 1.618 after each new data point, but is capped at
a certain level, say, 0.1 (note normalized coordinates are used). During the
search it keeps updating the current minimum, g min . The search continues
until the boundary of the parameter range is reached, or a point α = b is
found which satisfies
g(b) > g min + κσ,
(7.32)
where σ is the noise sigma and κ represents the required confidence level,
which can usually be chosen to be 3. After the bracket boundary at the positive
direction is determined, it then starts from α = α min and goes in the opposite
direction to find the lower bracket end, a.
After the minimum is bracketed, all the sample points on the line are fitted
to a parabola. If very large steps are taken and hence there are large gaps between the sample points, intermediate points inside the gaps can be evaluated.
The fitted parabola is used to predict the position of the minimum, which is
then sampled as the next trial solution. Figure 7.9 illustrates the procedure
executed by the robust 1-dimensional optimizer, in which the indices beside
the sample points indicate the order in which the date points are evaluated.
starting point and the minimum is more complex, a small noise level could
suffice to defeat the algorithm.
7.3.2 RCDS algorithm
Powell’s method is powerful for the optimization of smooth functions. However, its performance is sensitive to noise, as seen in Figure 7.7. A close examination of the algorithm reveals that the negative impact of noise comes
in through the 1-dimensional optimizer. For both the golden section method
and the inverse quadratic interpolation method, the first step is to bracket the
minimum within a finite zone. The bracketing procedure relies on the comparison of function values at the boundary points and a point inside. Noise
in the function values can change the comparison results and lead to a false
bracket. Noise can also change the next step of the 1-dimensional optimizer.
For the golden section method, it changes the selection of the subdivision to
move in; for the inverse interpolation method, it changes both the prediction
of the trial solution and the selection of the subdivision.
The 1-dimensional optimizers suffer from noise because they have no consideration of the existence of the noise. Small changes to the optimizers could
significantly suppress the noise effect. The robust conjugate direction search
(RCDS) [57] algorithm makes the 1-dimensional optimizer aware of the noise
level and takes measures to ensure the decisions in the bracketing and interpolation steps are valid under noise. The resulting 1-dimensional optimizer is
called the robust line optimizer. It is substantially more robust against noise.
Starting from the present solution, g 0 = g(α = 0), the robust line optimizer first finds the boundary in one direction (say, the positive direction)
by sampling new solutions with increasingly longer steps. The step length is
increased by a factor of 1.618 after each new data point, but is capped at
a certain level, say, 0.1 (note normalized coordinates are used). During the
search it keeps updating the current minimum, g min . The search continues
until the boundary of the parameter range is reached, or a point α = b is
found which satisfies
g(b) > g min + κσ,
(7.32)
where σ is the noise sigma and κ represents the required confidence level,
which can usually be chosen to be 3. After the bracket boundary at the positive
direction is determined, it then starts from α = α min and goes in the opposite
direction to find the lower bracket end, a.
After the minimum is bracketed, all the sample points on the line are fitted
to a parabola. If very large steps are taken and hence there are large gaps between the sample points, intermediate points inside the gaps can be evaluated.
The fitted parabola is used to predict the position of the minimum, which is
then sampled as the next trial solution. Figure 7.9 illustrates the procedure
executed by the robust 1-dimensional optimizer, in which the indices beside
the sample points indicate the order in which the date points are evaluated.