Online optimization algorithms 179
the present solution can be approximated by
f (x) ≈ f (x 0 ) + b
T ∆x +
1
2
∆x
T A∆x,
(7.8)
where ∆x = x − x 0 , b ≡ ∇f (x)| x=x0 is the gradient at x 0 and A is the
Hessian matrix, with A ij =
∂
2 f
∂xi∂xj | x=x0 . The derivatives provide information
of the function distribution around the present solution and hence can be used
to guide the search for the minimum.
Gradient-descent: Some methods use only the first order derivatives, i.e.
the gradient. One example is the steepest descent algorithm, also known as the
gradient descent algorithm. Starting from an initial solution x 0 , it looks for the
minimum iteratively. At each iteration, it performs a line minimization along
the gradient direction, −∇f (x i ), i.e., to find α i such that f (x i − α i ∇f (x i ))
is minimized, and makes a step change to the new solution from the present
solution x i ,
x i+1 = x i − α i ∇f (x i ).
(7.9)
The line minimization needs not to be exact; it suffices to find a step that considerably reduces the objective function and the gradient. The gradient descent
method guarantees the convergence toward the local minimum. However, for
nonlinear functions, the local gradient direction is often not the shortest direction to the local minimum. Therefore, the method may result in a zig-zag
convergence path with many small steps, which could be very inefficient.
Extremum Seeking (ES): Extremum Seeking is a group of adaptive control methods that attempt to optimize the performance of a dynamic system
and maintain a steady state on the extremum [113]. The ES methods optimize functions by approximating the gradients through function evaluations,
although the gradients are not formally computed.
In an ES scheme that has recently found applications in the accelerator
community, the knob parameters are varied from iteration n to iteration n + 1
by adding an oscillatory term that is modulated by the objective function [108,
107],
x i (n + 1) = x i (n) + ∆
√
αω i cos(ω i n∆ + kf (x n )),
(7.10)
where ∆, α, k, and ω i , i = 1–N , are parameters that control the behavior of
the algorithm. ω i is the rotation rate of parameter x i . Each knob parameter
should have a different ω i value. ∆ is a small number that can be considered
as the step size. A typical choice of its value may be ∆ =
2π
20 max(ωi) , such
that it takes at least 20 iterations to complete one rotation if the objective
function is at the extremum. k > 0 is required for a minimization problem
and its value should be chosen according to the objective function value and
the step size. α controls the rotation amplitude of the knob parameters.
For the knob parameter x i , the oscillation phase increment in iteration n
is ω i ∆ + k∆f n , where ∆f n = f (x n+1 ) − f (x n ). If the phase is in a proper
the present solution can be approximated by
f (x) ≈ f (x 0 ) + b
T ∆x +
1
2
∆x
T A∆x,
(7.8)
where ∆x = x − x 0 , b ≡ ∇f (x)| x=x0 is the gradient at x 0 and A is the
Hessian matrix, with A ij =
∂
2 f
∂xi∂xj | x=x0 . The derivatives provide information
of the function distribution around the present solution and hence can be used
to guide the search for the minimum.
Gradient-descent: Some methods use only the first order derivatives, i.e.
the gradient. One example is the steepest descent algorithm, also known as the
gradient descent algorithm. Starting from an initial solution x 0 , it looks for the
minimum iteratively. At each iteration, it performs a line minimization along
the gradient direction, −∇f (x i ), i.e., to find α i such that f (x i − α i ∇f (x i ))
is minimized, and makes a step change to the new solution from the present
solution x i ,
x i+1 = x i − α i ∇f (x i ).
(7.9)
The line minimization needs not to be exact; it suffices to find a step that considerably reduces the objective function and the gradient. The gradient descent
method guarantees the convergence toward the local minimum. However, for
nonlinear functions, the local gradient direction is often not the shortest direction to the local minimum. Therefore, the method may result in a zig-zag
convergence path with many small steps, which could be very inefficient.
Extremum Seeking (ES): Extremum Seeking is a group of adaptive control methods that attempt to optimize the performance of a dynamic system
and maintain a steady state on the extremum [113]. The ES methods optimize functions by approximating the gradients through function evaluations,
although the gradients are not formally computed.
In an ES scheme that has recently found applications in the accelerator
community, the knob parameters are varied from iteration n to iteration n + 1
by adding an oscillatory term that is modulated by the objective function [108,
107],
x i (n + 1) = x i (n) + ∆
√
αω i cos(ω i n∆ + kf (x n )),
(7.10)
where ∆, α, k, and ω i , i = 1–N , are parameters that control the behavior of
the algorithm. ω i is the rotation rate of parameter x i . Each knob parameter
should have a different ω i value. ∆ is a small number that can be considered
as the step size. A typical choice of its value may be ∆ =
2π
20 max(ωi) , such
that it takes at least 20 iterations to complete one rotation if the objective
function is at the extremum. k > 0 is required for a minimization problem
and its value should be chosen according to the objective function value and
the step size. α controls the rotation amplitude of the knob parameters.
For the knob parameter x i , the oscillation phase increment in iteration n
is ω i ∆ + k∆f n , where ∆f n = f (x n+1 ) − f (x n ). If the phase is in a proper