A novel technique for stochastic root-finding: Enhancing the search with adaptive d-ary search

Our solution recursively shrinks the search space by, at least, a factor of 2d3 at each epoch, where d ≥ 2 is a user-defined parameter of the algorithm. Our scheme is based, in part, on the Continuous Point Location with Adaptive d-ary Search (CPL-AdS), originally presented by Oommen and his co-authors. The solution to the CPL-AdS, however, is not applicable here because of the inherent asymmetry of the SRF problem. Our solution invokes a CPL-AdS-like solution to partition the search interval into d sub-intervals, evaluates the location of the unknown root x* with respect to these sub-intervals using Learning Automata, and prunes the search space in each iteration by eliminating at least one partition. Our scheme, the CPL-AdS algorithm for SRF, denoted as SRF-AdS, is shown to converge to the unknown root x* with an arbitrary large degree of accuracy, i.e., with a probability as close to unity as desired.