Online optimization algorithms 185
direction and the replacement is skipped. In general, for a quadratic function,
a conjugate direction set will be obtained after n iterations.
A critical component of Powell’s method is the line minimization, which
performs the task of minimizing the 1-dimensional problem of g(α) = f (x 0 +
αu). One of two derivative-free line optimizers, the golden section search
method and Brent’s inverse parabolic interpolation method, is often used. For
both line optimizers, the local minimum is first bracketed in a zone α ∈ [a, b].
This is ensured if a third point c is found between points a and b for which
g(c) < g(a) and g(c) < g(b) are both satisfied.
With the initial three points, a < c < b, the golden section search then
samples a new point t in one of the two subdivisions, say t ∈ (a, c). If f (t) <
f (c), then [a, c] becomes the new bracket; if f (t) > f (c), [t, b] becomes the new
bracket. It can iteratively proceed until the minimum is found with the desired
tolerance. For the highest efficiency, the distance from the inside sample point
to the bracket boundary is chosen to be
√
5−1
2
≈ 0.618. For Brent’s method,
the function values at point a, c, and b are used to construct a parabola and
the location corresponding to the minimum of the parabola is used as the new
sample point. The golden section method has linear convergence, while the
inverse parabola interpolation has quadratic convergence. The latter is used
more often for smooth functions. With noise in the function values, both the
golden section search and inverse parabola interpolation methods could fail.
When the golden section search method is used, Powell’s method can
still be characterized as a direct search method. However, with the inverse
parabolic interpolation, it no longer qualifies as a direct search method since
the function values are used to construct a model. Powell’s method is especially efficient for convex functions.
The Nelder-Mead simplex method and Powell’s method are both popular and powerful optimization algorithms for smooth functions. Noise in the
function values has a big impact to the performance of both methods. Modifications to the original algorithms can be made to mitigate the impact of
noise. This will be discussed in Section 7.3.
7.2.2 Stochastic optimization algorithms
Some optimization algorithms make use of random operations in the course of
searching for the optimal solutions. The random operations could be choosing
the parameter values of the trial solutions or making a decision of accepting or rejecting a solution. Because of the randomness, the convergence path
is different every time. These algorithms are called stochastic optimization
algorithms.
Stochastic optimization algorithms often have poorer efficiency than the
deterministic methods in terms of the number of required function evaluations
to converge to the optimum. This is understandable as these methods are not
“greedy”: they do not intend to take the shortest paths toward the minimum.
As the new trial solutions are somewhat randomly chosen, the outcome of
direction and the replacement is skipped. In general, for a quadratic function,
a conjugate direction set will be obtained after n iterations.
A critical component of Powell’s method is the line minimization, which
performs the task of minimizing the 1-dimensional problem of g(α) = f (x 0 +
αu). One of two derivative-free line optimizers, the golden section search
method and Brent’s inverse parabolic interpolation method, is often used. For
both line optimizers, the local minimum is first bracketed in a zone α ∈ [a, b].
This is ensured if a third point c is found between points a and b for which
g(c) < g(a) and g(c) < g(b) are both satisfied.
With the initial three points, a < c < b, the golden section search then
samples a new point t in one of the two subdivisions, say t ∈ (a, c). If f (t) <
f (c), then [a, c] becomes the new bracket; if f (t) > f (c), [t, b] becomes the new
bracket. It can iteratively proceed until the minimum is found with the desired
tolerance. For the highest efficiency, the distance from the inside sample point
to the bracket boundary is chosen to be
√
5−1
2
≈ 0.618. For Brent’s method,
the function values at point a, c, and b are used to construct a parabola and
the location corresponding to the minimum of the parabola is used as the new
sample point. The golden section method has linear convergence, while the
inverse parabola interpolation has quadratic convergence. The latter is used
more often for smooth functions. With noise in the function values, both the
golden section search and inverse parabola interpolation methods could fail.
When the golden section search method is used, Powell’s method can
still be characterized as a direct search method. However, with the inverse
parabolic interpolation, it no longer qualifies as a direct search method since
the function values are used to construct a model. Powell’s method is especially efficient for convex functions.
The Nelder-Mead simplex method and Powell’s method are both popular and powerful optimization algorithms for smooth functions. Noise in the
function values has a big impact to the performance of both methods. Modifications to the original algorithms can be made to mitigate the impact of
noise. This will be discussed in Section 7.3.
7.2.2 Stochastic optimization algorithms
Some optimization algorithms make use of random operations in the course of
searching for the optimal solutions. The random operations could be choosing
the parameter values of the trial solutions or making a decision of accepting or rejecting a solution. Because of the randomness, the convergence path
is different every time. These algorithms are called stochastic optimization
algorithms.
Stochastic optimization algorithms often have poorer efficiency than the
deterministic methods in terms of the number of required function evaluations
to converge to the optimum. This is understandable as these methods are not
“greedy”: they do not intend to take the shortest paths toward the minimum.
As the new trial solutions are somewhat randomly chosen, the outcome of