bracketing: Bracketing.
In brunasqz/NonlinearOpMethods: Nonlinear Optimization Methods

Description Usage Arguments Details Value About the parameter sstep References See Also Examples

bracketing is a function that determines a range (bracket) [a, b] of values where a univariate function has possibly a local minimum. This function is able to implement an accelerated search.

1 2	bracketing(phi, alpha0 = 0, phi0 = NULL, sstep = 0.05, t = 2, maxNI = 50)

`phi`	A univariate function.
`alpha0`	A number, starting point.
`phi0`	A number, objective value of `alpha0`.
`sstep`	A number with the step to increase alpha0 until a bracket is determined. It can accept positive or negative values, see below.
`t`	Multiplicator factor to increase sstep in each iteration. If `t > 1`, an accelerated search is performed. Use `t = 1` for the fixed step version.
`maxNI`	Maximum number of iterations. It can be used to determine degenerate problems with no finite minimum, when the bracket does not exist.

Given a starting point alpha0, the bracketing process follows:
1. Set alpha1 <- alpha0 and alpha2 <- alpha1 + sstep
2. While the function is decreasing in this direction, keep increasing alpha1 and alpha2, that is, Repeat the following until phi(alpha2) > phi(alpha1):
2.1 Set sstep <- t*sstep
2.2 Set alpha0 <- alpha1
2.3 Set alpha1 <- alpha2
2.3 Set alpha2 <- alpha1 + sstep
In the end, either [alpha1, alpha2] or [alpha0, alpha2] can be chosen as bracket. The latter was preferred here for safety purposes. Also, notice that the method here can employ an accelerated search by setting t > 1, in which the step of alpha increases in each iteration.

Returns a bracket in the format of a list. These intervals can be used in other interval halving methods, such as the goldensection.

If phi comes from phi(alpha) := f(x + alpha*s) for a given point x and a descent direction s, then sstep > 0 will correctly yield a descent direction in the univariate version. For general single-variable functions, the option sstep < 0 is left to handle specific situations, as shown in the examples.

Rao, Singiresu S.; Engineering Optimization Theory and and Practice, 4th ed., pages 273:279.

The documentation of the functions univariate_f and goldensection in this package.

# A univariate function
phi <- function(alpha)
{
  return (alpha^5 - 5*alpha^3 - 20*alpha + 5)
}
# Plot the function for convenience over the interval [-5,5]
plot(phi, -5, 5)
# In the inverval [0,5], it has a minimum in alpha = 2. Starting from
# alpha0 = 0, for instance, the following bracket is obtained
bracket <- bracketing(phi, alpha0 = 0) #(0.75, 3.15), containing 2
# If phi0 = phi(alpha0) = 5 is provided, the results are the same, but the
# number of evaluations is reduced by one
bracket <- bracketing(phi, alpha0 = 0, phi0 = 2)
# Setting t = 1 (fixed step size) generates a smaller interval, but increases
# the number of evaluations considerably
bracket <- bracketing(phi, alpha0 = 0, t = 1) #(1.95, 2.05)
# Starting from alpha0 = 4, only one iteration is executed because phi is
# increasing in this direction (the optimum is actually at 4)
bracket <- bracketing(phi, alpha0 = 4, sstep = 0.05) #(4, 4.05)
# However, changing the sign of sstep yields a correct bracketing of the
# true minimum.
bracket <- bracketing(phi, alpha0 = 4, sstep = -0.05) #(0.85, 3.25)
# Finally, from -4 to the left this function has no finite minimum, and thus
# the algorithm goes until the total iterations are run. This is an indicator
# of a problem with no minimum.
bracket <- bracketing(phi, alpha0 = -4, sstep = -0.05)