scdensity (version 1.0.3)

improve: Move points closer to a target while maintaining a constraint.

Description

improve(startValue, x, confun) uses a greedy algorithm to move the elements of a user-supplied vector startValue closer to their target values x, while continually satisfying the constraint-checking function confun.

Usage

improve(
  startValue,
  x,
  confun,
  verbose = FALSE,
  maxpasses = 500,
  tol = diff(range(c(startValue, x))/1e+05)
)

Value

A vector of the same length as startValue, with elements closer to x.

Arguments

startValue

The vector of starting values for the search. Must satisfy confun(startValue) == TRUE

x

The target values.

confun

The constraint-checking function. confun(y) must return a Boolean value that is invariant to permutations of its vector argument y.

verbose

A logical value indicating whether or not information about iteration progress should be printed to the console.

maxpasses

The maximum allowable number of sweeps through the data points. At each pass, every point that is not pinned at the constraint boundary is moved toward its target point in a stepping-out procedure.

tol

Numerical tolerance for constraint checking. A point is considered to be at the constraint boundary if adding tol to it causes the constraint to be violated. If tol is too large, the algorithm will terminate prematurely. If it is too small, run time will be increased with no discernible benefit in the result.

Details

The algorithm implemented here is the one in Wolters (2012), "A Greedy Algorithm for Unimodal Kernel Density Estimation by Data Sharpening," Journal of Statistical Software, 47(6). It could conceivably be useful as a part of other gradient-free optimization schemes where we have an infeasible point and a feasible one, and we seek a point that is on the constraint boundary near the infeasible one.

Examples

#Constrain points to be inside the hypercube with vertices at -1 and +1.
#The target point is a vector of independent random standard normal variates.
#Start at rep(0,n) and "improve" the solution toward the target.
n <- 20
incube <- function(x) all(x <= 1 & x >= -1)
x0 <- rep(0,n)
target <- sort(rnorm(n))
xstar <- improve(x0, target, incube, verbose=TRUE)
dist <- abs(target - xstar)
zapsmall(cbind(target, xstar, dist), 4)