Assume we’re given a known domain for a function , and that the function can be calculated (i.e., it is known to the algorithm). Further, assume we also have a known goal value (e.g., a zero of the function). The purpose of this algorithm is to find the domain value that generates the goal value .

Begin by evaluating the function some fixed number of times at random points in the domain, which will produce a set of range values. Then select the value for which is minimum, where . That is, you select the domain value that generates a range value that is closest to the goal value.

Assume that is the average difference between the range values and the goal value over the domain values selected. That is, we calculate the difference between each range value and the goal value , and calculate the average over those differences.

Evaluate the following –

.

That is, allows us to compare the difference between the distance from our best range value and the goal value, and the average distance between range values and the goal value.

Then evaluate the function another times in the domain, using as the seed value for the points that are randomly selected, over a range of . This will cause the domain to shrink as we get closer to the goal value.

Repeat this process until is within some tolerable error.

Attached is code that implements this algorithm, that can find the zero of a parabola, but it can be easily augmented to include any function. Note that this algorithm would work analogously in any dimension of Euclidean space.

The algorithm is not deterministic, and the runtime will of course depend upon your tolerance for error. In the case of a simple parabola, it can find the zero over a range of [-5,5], with a tolerance of , in about 0.005 seconds.

8_30CMNDLINE

least_error_optimization