STOCHASTIC SEARCHING ON THE LINE AND ITS APPLICATIONS TO PARAMETER LEARNING IN NONLINEAR OPTIMIZATION

We consider the problem of a learning mechanism (for example, a robot) locating a point on a line when it is interacting with a random envir onment which essentially informs it, possibly erroneously, which may i t should move. In this paper we present a novel scheme by which the po int can be learned using some recently devised learning principles. Th e heart of the strategy involves discretizing the space and performing a controlled random walk on this space. The scheme is shown to be eps ilon-optimal and to converge with probability 1. Although the problem is solved in its generality, its application in nonlinear optimization has also been suggested. Typically, an optimization process involves working one's way toward the maximum (minimum) using the local informa tion that is available. However, the crucial issue in these strategies is that of determining the parameter to be used in the optimization i tself. If the parameter is too small the convergence is sluggish. On t he other hand, if the parameter is too large, the system could erroneo usly converge or even oscillate. Our strategy can be used to determine the best parameter to be used in the optimization.