Package org.anchoranalysis.math.optimization

Class SearchClosestValueMonoticallyIncreasing

Object

SearchClosestValueMonoticallyIncreasing

public class SearchClosestValueMonoticallyIncreasing
extends Object

Given a monotonically increasing function of an integer, determine the input value that provides an output value as close to target as possible.

The input-values must be integers, and have a minimum bound.

It begins at the minimum-bound, and in a similar manner to exponential search, successively doubles, until a lower and upper bound are found.

It then proceeds with a binary-search-style recursive evaluation to find the integer value that produces the exact closest value to target.

An upper bound on the input-values may also be optionally imposed via boundUpper.

Author:

Owen Feehan

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static interface	SearchClosestValueMonoticallyIncreasing.ValueFunction	The function that calculates the output value for a particular input int.

Constructor Summary

Constructors

Constructor	Description
SearchClosestValueMonoticallyIncreasing(double target, SearchClosestValueMonoticallyIncreasing.ValueFunction function)	Create without an upper bound.
SearchClosestValueMonoticallyIncreasing(double target, SearchClosestValueMonoticallyIncreasing.ValueFunction function, IntPredicate boundUpper)	Creates a new SearchClosestValueMonoticallyIncreasing instance.

Method Summary

Modifier and Type	Method	Description
int	findOptimalInput(int boundLower)	Finds the input value that produces a calculated-value that is closest to target.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

SearchClosestValueMonoticallyIncreasing

public SearchClosestValueMonoticallyIncreasing(double target,
 SearchClosestValueMonoticallyIncreasing.ValueFunction function)

Create without an upper bound.

Parameters:

target - the target value to try and be closest to when evaluating function on differing inputs.

function - calculates an output value for a particular input integer.

SearchClosestValueMonoticallyIncreasing

public SearchClosestValueMonoticallyIncreasing(double target,
 SearchClosestValueMonoticallyIncreasing.ValueFunction function,
 IntPredicate boundUpper)

Creates a new SearchClosestValueMonoticallyIncreasing instance.

Parameters:

target - The target value to try and be closest to when evaluating function on differing inputs.

function - Calculates an output value for a particular input integer.

boundUpper - An optional upper bound, which must be false for all values less than a particular threshold, and true all values over it.

This allows an additional constraint to be placed on the exploration of values.

It is expressed as a predicate rather than as a constant, as the threshold may not be known exactly, and this allows the search function to explore it, as it also seeks the closest value to target.

It is guaranteed that this predicate will only be evaluated after a call to function with the same value - and this call was the most-recent call. This may help optimize implementation code of function and boundUpper.

Method Details

findOptimalInput

public int findOptimalInput(int boundLower)

Finds the input value that produces a calculated-value that is closest to target.

Parameters:

boundLower - a lower bound on the input range, inclusive.

Returns:

the input-value that is optimal to produce the closest value to target when evaluated using calculateValue.