184 Beam-based Correction and Optimization for Accelerators
step β along v is made, the function is approximately
f (x 0 + αu + βv) ≈ f (x 0 + αu) + βb
T v +
1
2
β
2 v
T Av,
(7.16)
where we have used the fact that the gradient at x 0 + αu is b + αA · u and
the conjugate condition, Eq. (7.15). It is clear that the minimum in the u
direction is not changed after the step along v. On the other hand, if the two
directions are not conjugate, then an additional term αβu
T Av will appear
on the right hand side of Eq. (7.16), which will change the minimum in one
direction after a step is made on another.
This is illustrated in Figure 7.3 for a 2-dimensional case. Starting from
point 0, if the search is along orthogonal, but non-conjugate directions, for
example, x 1 and x 2 , the convergence path will consist of many small segments
in the corridor leading to the minimum. However, if the search is along the
conjugate directions, u 1 and u 2 , the minimum will be found in only two steps.
If the Hessian matrix can be calculated and is positive definite, the conjugate directions can be determined from its eigenvectors. If the conjugate
directions cannot be calculated, Powell’s method can construct the conjugate
direction set from the successive line minimizations with a non-degenerate initial direction set. The initial directions may be simply the unit vectors along
the parameter axes. Suppose at the beginning of an iteration, the solution is
labeled x 0 and f 0 = f (x 0 ), and the directions are u k , k = 1, 2, · · · , n. During
the iteration, the algorithm executes the following steps [97],
1. Perform line minimizations along all n directions and record the biggest
function value drop during one line minimization, call it ∆ and mark
the corresponding direction u d . The final new solution is labeled x m ,
with f m = f (x m ).
2. Evaluate the function value at the extension point, x t = 2x m − x 0 , with
f t = f (x t ).
3. If f t > f 0 or 2(f 0 + f t − 2f m )(f 0 − f m − ∆)
2 > ∆(f 0 − f t )
2 , terminate the
iteration without replacing a direction; otherwise, replace the direction
u d with the new direction u m =
xm−x0
||xm−x0|| . Perform the line minimization
along u m and terminate the iteration.
Replacing a direction with the direction that goes from the initial solution
to the final solution is desired because the latter is likely a more efficient
search direction. For example, in Figure 7.3, the direction from point 0 to 2
is much better aligned with the corridor leading to the local minimum. The
direction with the largest function value drop is chosen to be replaced because
it is likely to have a large overlap with the new direction; removing it from the
direction set reduces the likelihood of introducing degeneracy. In Step 2 the
extension point is evaluated as a way to check the validity of the new direction.
If either of the two conditions in Step 3 is met, there is not much to gain in this
step β along v is made, the function is approximately
f (x 0 + αu + βv) ≈ f (x 0 + αu) + βb
T v +
1
2
β
2 v
T Av,
(7.16)
where we have used the fact that the gradient at x 0 + αu is b + αA · u and
the conjugate condition, Eq. (7.15). It is clear that the minimum in the u
direction is not changed after the step along v. On the other hand, if the two
directions are not conjugate, then an additional term αβu
T Av will appear
on the right hand side of Eq. (7.16), which will change the minimum in one
direction after a step is made on another.
This is illustrated in Figure 7.3 for a 2-dimensional case. Starting from
point 0, if the search is along orthogonal, but non-conjugate directions, for
example, x 1 and x 2 , the convergence path will consist of many small segments
in the corridor leading to the minimum. However, if the search is along the
conjugate directions, u 1 and u 2 , the minimum will be found in only two steps.
If the Hessian matrix can be calculated and is positive definite, the conjugate directions can be determined from its eigenvectors. If the conjugate
directions cannot be calculated, Powell’s method can construct the conjugate
direction set from the successive line minimizations with a non-degenerate initial direction set. The initial directions may be simply the unit vectors along
the parameter axes. Suppose at the beginning of an iteration, the solution is
labeled x 0 and f 0 = f (x 0 ), and the directions are u k , k = 1, 2, · · · , n. During
the iteration, the algorithm executes the following steps [97],
1. Perform line minimizations along all n directions and record the biggest
function value drop during one line minimization, call it ∆ and mark
the corresponding direction u d . The final new solution is labeled x m ,
with f m = f (x m ).
2. Evaluate the function value at the extension point, x t = 2x m − x 0 , with
f t = f (x t ).
3. If f t > f 0 or 2(f 0 + f t − 2f m )(f 0 − f m − ∆)
2 > ∆(f 0 − f t )
2 , terminate the
iteration without replacing a direction; otherwise, replace the direction
u d with the new direction u m =
xm−x0
||xm−x0|| . Perform the line minimization
along u m and terminate the iteration.
Replacing a direction with the direction that goes from the initial solution
to the final solution is desired because the latter is likely a more efficient
search direction. For example, in Figure 7.3, the direction from point 0 to 2
is much better aligned with the corridor leading to the local minimum. The
direction with the largest function value drop is chosen to be replaced because
it is likely to have a large overlap with the new direction; removing it from the
direction set reduces the likelihood of introducing degeneracy. In Step 2 the
extension point is evaluated as a way to check the validity of the new direction.
If either of the two conditions in Step 3 is met, there is not much to gain in this