BinarySearch

class decida.BinarySearch.BinarySearch(low, high, min, max, min_delta=None, bracket_step=None, bracket_mult=None, find_max=True)

synopsis:

Binary Search iterator class.

BinarySearch organizes a binary search for a parameter value based on some external evaluation which gives a success or failure using trial parameter values presented by the BinarySearch instance.

The binary search proceeds as follows:

  • Set the parameter to the low configuration value.
  • Bracket1 mode: stay or move the parameter value lower until the external evaluation produces success (if find_max is False, look for failure).
  • Set the parameter value to the high configuration value.
  • Bracket2 mode: stay or move the parameter value higher until the external evaluation producess failure (if find_max is False, look for success).
  • With the upper and lower brackets determined, search within their interval for the maximum value of the parameter which produces success (if find_max is False, look for the minimum value of the parameter which produces success).
  • Bracket trial values are changed according to the configuration options bracket_step (increase or decrease by a specific step), or bracket_mult (increase or decrease by multiplying or dividing by a specific factor). Also the initial brackets are limited by min and max configuration options.
  • Convergence is reported when the absolute change in trial parameter values is less than the min_delta configuration option.

constructor arguments:

low (float)

first parameter value to try in binary-search bracket lower-bound (bracket1) mode. If the evaluation produces a success, the mode proceeds to bracket upper-bound (bracket2) mode. Otherwise, the parameter is decremented by bracket_step, if specified, or divided by bracket_mult if specified.

high (float)

first parameter value to try in binary-search bracket upper-bound (bracket2) mode. If the evaluation produces a success, the mode proceeds to binary search (bisection) mode. Otherwise, the parameter is incremented by bracket_step, if specified, or multiplied by bracket_mult if specified.

min (float)

minimum value of the parameter. If searching in bracket1 mode goes below min, the binary search stops.

max (float)

maximum value of the parameter. If searching in bracket2 mode goes above max, the binary search stops.

min_delta (float, default=None)

Convergence is achieved if the absolute change between parameter steps is less than min_delta.

bracket_step (float, default=None)

If specified, the parameter is revised by one bracket_step in bracket1 or bracket2 modes.

bracket_mult (float, default=None)

If specified, the parameter is revised by scaling by bracket_mult in bracket1 or bracket2 modes.

find_max (bool, default=True)

If True, maximum value of the parameter is found which gives a successful result. If False, bracket modes and searching goes in the opposite sense.

example (from test_BinarySearch_2):

def funct(x) :
    a, b, c = 1.0, -4.0, 2.0
    y = a*x*x + b*x + c
    return y

bin = BinarySearch(
     low=1.0, high=2.0, min=-10, max=3,
     min_delta=1e-6, bracket_step=0.1
)

bin.start()
while not bin.is_done() :
    x=bin.value()
    f=funct(x)
    success = (f >= 0)
    print "%-10s: x=%-18s y=%-18s %-5s" % (bin.mode(), x, f, success)
    bin.update(success)

print
print "x = ", bin.last_success()

public methods:

is_done()

return True if convergence is achieved.

results:

  • Return True if bisection has converged.
last_success()

return the last successful parameter value.

results:

  • Returns the parameter value which last achieved success.
mode()

return the binary search mode.

results:

  • The binary search mode is returned. The modes are:

    • start : initial mode.
    • bracket1 : search for the lowest value of the parameter that produces a successful result.
    • bracket2 : search for the highest value of the parameter that produces an unsuccessful result.
    • bisection : binary search mode.
    • done : convergence.
start()

reset parameter value, brackets and binary search mode.

results:

  • Resets the binary search object to its starting state.
  • The parameter is set to the first trial value.
  • Initial bracket values are reset.
  • The bisection mode is set to “start”
update(success)

update the trial parameter value.

results:

  • Revise the parameter value based on the two last bracketed binary search values and success or failure of the current parameter value.
  • Binary search brackets are revised.
value()

return the updated parameter value.

results:

  • Returns the updated parameter value which is to be tried for success.