Online optimization algorithms 183
1
2
3
r
e
ic
oc
3
′
2
′
Figure 7.2 Illustration of the downhill simplex method in the 2-dimensional case.
Function values on the vertices are ordered f1 ≤ f2 ≤ f3.
vertex is replaced with a new point, which is selected according to a series
of trial and comparison operations. The Nelder-Mead simplex method works
in most times and it is very efficient when it does. However, there are cases
when the method fails, with symptoms like slow convergence or premature
convergence to non-optimal points.
Direction search algorithms tend to be sensitive to the noise in the function
evaluations as they completely rely on the comparison results of function
values to make decisions on the search paths. The noise will likely change
the comparison results and hence in turn change the convergence path or
cause the algorithm to randomly wander around without converging.
Besides the direct search algorithms, other gradient-free deterministic algorithms use the numeric function values to guide the selection of new trial
solutions. This is done, for example, by modeling the objective function within
the neighborhood of the best solution. One such method is Powell’s conjugate
direction method [96].
Powell’s method: Powell’s method performs iterative one dimensional
optimization over a set of directions that are linearly independent and mutually conjugate. In the parameter space a direction is represented by a unit
vector. Two directions, u and v, are mutually conjugate for the optimization
problem if they satisfy
u
T Av = 0,
(7.15)
where A is the Hessian matrix. The benefit of searching along the conjugate
directions is that a move along one direction does not change the position
of the best solution in the other directions (to the extent that the quadratic
approximation of the objective function is valid). Suppose a step α is taken
to minimize the objective function along the u direction, after that a second
1
2
3
r
e
ic
oc
3
′
2
′
Figure 7.2 Illustration of the downhill simplex method in the 2-dimensional case.
Function values on the vertices are ordered f1 ≤ f2 ≤ f3.
vertex is replaced with a new point, which is selected according to a series
of trial and comparison operations. The Nelder-Mead simplex method works
in most times and it is very efficient when it does. However, there are cases
when the method fails, with symptoms like slow convergence or premature
convergence to non-optimal points.
Direction search algorithms tend to be sensitive to the noise in the function
evaluations as they completely rely on the comparison results of function
values to make decisions on the search paths. The noise will likely change
the comparison results and hence in turn change the convergence path or
cause the algorithm to randomly wander around without converging.
Besides the direct search algorithms, other gradient-free deterministic algorithms use the numeric function values to guide the selection of new trial
solutions. This is done, for example, by modeling the objective function within
the neighborhood of the best solution. One such method is Powell’s conjugate
direction method [96].
Powell’s method: Powell’s method performs iterative one dimensional
optimization over a set of directions that are linearly independent and mutually conjugate. In the parameter space a direction is represented by a unit
vector. Two directions, u and v, are mutually conjugate for the optimization
problem if they satisfy
u
T Av = 0,
(7.15)
where A is the Hessian matrix. The benefit of searching along the conjugate
directions is that a move along one direction does not change the position
of the best solution in the other directions (to the extent that the quadratic
approximation of the objective function is valid). Suppose a step α is taken
to minimize the objective function along the u direction, after that a second