Univariate Optimization

One approach to calculus-based optimization is to perform sequential optimizations of the cost function by treating each parameter in turn as a univariate minimization problem. This approach, combined with heuristic rules for selecting a good sequence of parameters to minimize, was shown to be fast and accurate for registration of PET and MRI images [14,21]. Univariate minimization is based on a quadratic (i.e., parabolic) approximation of the cost function in the region where the parameter is near the cost function's minimum (Fig. 2). If

FIGURE 2 The cost function is represented on the vertical axis and a parameter that needs to be adjusted to minimize the cost function is shown on the horizontal axis. Calculus-based univariate minimization uses the first and second derivatives of the cost function at a given point (indicated by the blue cross), to construct a parabola (red curve) that is assumed to be a reasonable model of how the true cost function varies. The first derivative, represented by the yellow line, should be zero (horizontal) at the true minimum. The minimization algorithm computes the value of the parameter that corresponds to the minimum of the constructed parabola and then reevaluates the derivatives using this new estimate. This process is repeated iteratively until a minimum is reached. See also Plate 75.

FIGURE 2 The cost function is represented on the vertical axis and a parameter that needs to be adjusted to minimize the cost function is shown on the horizontal axis. Calculus-based univariate minimization uses the first and second derivatives of the cost function at a given point (indicated by the blue cross), to construct a parabola (red curve) that is assumed to be a reasonable model of how the true cost function varies. The first derivative, represented by the yellow line, should be zero (horizontal) at the true minimum. The minimization algorithm computes the value of the parameter that corresponds to the minimum of the constructed parabola and then reevaluates the derivatives using this new estimate. This process is repeated iteratively until a minimum is reached. See also Plate 75.

p0 is the optimum value of the parameter p, and c is the cost function, this approximation gives c(p) = c(p0) + ^(p - p0)2-

The first derivative of the cost function with respect to p, C is given by:

c'(p)=2*k*(p - po), and the second derivative, c", by c"(p) = 2*k. From this, it follows directly that

The parabolic form of the cost function is justified by the fact that the first derivative of the cost function should be zero at a local minimum or maximum. The optimization strategy is very simple: Compute the first and second derivatives of the cost function with respect to the parameter, divide the first derivative by the second derivative, and subtract the resulting quotient from the current value of the parameter. If the parabolic model were perfectly accurate (which it generally is not), the minimum would be reached in a single step. As the minimum is approached, the parabolic approximation should become increasingly valid, and convergence should be rapid with repeated iterations. A reasonable stopping criterion is when the first derivatives become arbitrarily close to zero or when the predicted or actual improvements in the cost function become arbitrarily small.

0 0

Post a comment