180 Beam-based Correction and Optimization for Accelerators
value such that the objective function is being reduced, hence k∆f n < 0, the
phase rotation will be slowed down and the objective function will continue
to decrease. It can be shown that in the limiting case of large ω i and small
∆, the average behavior of the knob parameters is to follow the direction of
gradient descent. If the extremum is reached, all knob parameters will continue
to rotate with a constant amplitude and rotation rate, at which point the α
parameter can be decreased or set to zero to effectively turn the algorithm off.
One advantage of the ES method is that it can be applied to an objective function that is dynamically varying, in which case the algorithm will
automatically chase the drifting extremum. This has been demonstrated in an
experiment on the SPEAR3 ring [107]. However, generally the ES method is
not very efficient. And for any application problem the algorithm parameters
need to be carefully adjusted in order for the method to work. Finding the
appropriate algorithm setting for a new application can be time consuming.
Newton method: Some algorithms require the calculation of the second
order derivatives, i.e., the Hessian matrix. These include the Newton method,
in which the step change from the present solution to the local minimum is
calculated using a quadratic approximation of the function, which gives
x i+1 = x i − A
−1
i ∇f (x i ).
(7.11)
The Newton method converges fast when the starting point is close to the
minimum. In the area where the quadratic approximation is not valid, the
predicted step change may be unreasonable. In such cases, modifications may
be made to Eq. (7.11). For example, the step change may be scaled down by a
factor λ i < 1, in which case the method is called the relaxed Newton method.
Another possible modification is to add a diagonal, positive definite matrix to
the Hessian, as is done in the Levenberg-Marquardt method,
x i+1 = x i − (A i + λ i I)
−1 ∇f (x i ),
(7.12)
where I is the unit matrix.
Quasi-Newton methods: Quasi-Newton methods use the Hessian matrix but do not require the explicit calculation of it. Instead, an approximate
Hessian matrix or its inverse is built up using the previous solutions and the
gradients. For example, for the Davidon-Fletcher-Powell (DFP) method, the
inverse Hessian matrix at iteration i + 1, H i+1 , is updated with [97]
H i+1 = H i +
∆x i+1 ∆x
T
i+1
∆x T
i+1 ∆g i+1
−
H i ∆g i+1 ∆g
T
i+1 H i
∆g T
i+1 H i ∆g i+1
,
(7.13)
where ∆x i+1 = x i+1 − x i and ∆g i+1 = ∇f (x i+1 ) − ∇f (x i ). Another widely
used quasi-Newton method is the BFGS algorithm, which uses a slightly different updating formula for H. Eq. (7.11) is used to update the solution,
with A
−1 replaced with H. The initial inverse Hessian matrix may be set to
the identity matrix. It can be shown that for quadratic functions, after some
iterations, H will be a good approximation of the inverse Hessian matrix.
value such that the objective function is being reduced, hence k∆f n < 0, the
phase rotation will be slowed down and the objective function will continue
to decrease. It can be shown that in the limiting case of large ω i and small
∆, the average behavior of the knob parameters is to follow the direction of
gradient descent. If the extremum is reached, all knob parameters will continue
to rotate with a constant amplitude and rotation rate, at which point the α
parameter can be decreased or set to zero to effectively turn the algorithm off.
One advantage of the ES method is that it can be applied to an objective function that is dynamically varying, in which case the algorithm will
automatically chase the drifting extremum. This has been demonstrated in an
experiment on the SPEAR3 ring [107]. However, generally the ES method is
not very efficient. And for any application problem the algorithm parameters
need to be carefully adjusted in order for the method to work. Finding the
appropriate algorithm setting for a new application can be time consuming.
Newton method: Some algorithms require the calculation of the second
order derivatives, i.e., the Hessian matrix. These include the Newton method,
in which the step change from the present solution to the local minimum is
calculated using a quadratic approximation of the function, which gives
x i+1 = x i − A
−1
i ∇f (x i ).
(7.11)
The Newton method converges fast when the starting point is close to the
minimum. In the area where the quadratic approximation is not valid, the
predicted step change may be unreasonable. In such cases, modifications may
be made to Eq. (7.11). For example, the step change may be scaled down by a
factor λ i < 1, in which case the method is called the relaxed Newton method.
Another possible modification is to add a diagonal, positive definite matrix to
the Hessian, as is done in the Levenberg-Marquardt method,
x i+1 = x i − (A i + λ i I)
−1 ∇f (x i ),
(7.12)
where I is the unit matrix.
Quasi-Newton methods: Quasi-Newton methods use the Hessian matrix but do not require the explicit calculation of it. Instead, an approximate
Hessian matrix or its inverse is built up using the previous solutions and the
gradients. For example, for the Davidon-Fletcher-Powell (DFP) method, the
inverse Hessian matrix at iteration i + 1, H i+1 , is updated with [97]
H i+1 = H i +
∆x i+1 ∆x
T
i+1
∆x T
i+1 ∆g i+1
−
H i ∆g i+1 ∆g
T
i+1 H i
∆g T
i+1 H i ∆g i+1
,
(7.13)
where ∆x i+1 = x i+1 − x i and ∆g i+1 = ∇f (x i+1 ) − ∇f (x i ). Another widely
used quasi-Newton method is the BFGS algorithm, which uses a slightly different updating formula for H. Eq. (7.11) is used to update the solution,
with A
−1 replaced with H. The initial inverse Hessian matrix may be set to
the identity matrix. It can be shown that for quadratic functions, after some
iterations, H will be a good approximation of the inverse Hessian matrix.