Optimization Algorithm

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

Begin by evaluating the function some fixed number of times K at random points in the domain, which will produce a set of K range values. Then select the value x for which |y - y_g| is minimum, where y = F(x). That is, you select the domain value that generates a range value that is closest to the goal value.

Assume that \mu 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 y_i and the goal value |y_i - y_g|, and calculate the average over those differences.

Evaluate the following –

\epsilon = \frac{|y - y_g|}{\mu}.

That is, \epsilon 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 K times in the domain, using x as the seed value for the points that are randomly selected, over a range of x \pm \epsilon \frac{b - a}{2}. This will cause the domain to shrink as we get closer to the goal value.

Repeat this process until |y - y_g| 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 10^{-5}, in about 0.005 seconds.




Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s