Sampling 3 points of a function determines unique parabola. Using this information we will go directly to its minimum. Suppose, we have 3 points such that line segment contains minimum of a function . Than, we need to solve following system of equations:
Note, that this system is linear, since we need to solve it on . Minimum of this parabola will be calculated as:
Note, that if , than will lie in
def parabola_search(f, x1, x2, x3, epsilon): f1, f2, f3 = f(x1), f(x2), f(x3) while x3 - x1 > epsilon: u = x2 - ((x2 - x1)**2*(f2 - f3) - (x2 - x3)**2*(f2 - f1))/(2*((x2 - x1)*(f2 - f3) - (x2 - x3)*(f2 - f1))) fu = f(u) if x2 <= u: if f2 <= fu: x1, x2, x3 = x1, x2, u f1, f2, f3 = f1, f2, fu else: x1, x2, x3 = x2, u, x3 f1, f2, f3 = f2, fu, f3 else: if fu <= f2: x1, x2, x3 = x1, u, x2 f1, f2, f3 = f1, fu, f2 else: x1, x2, x3 = u, x2, x3 f1, f2, f3 = fu, f2, f3 return (x1 + x3) / 2
The convergence of this method is superlinear, but local, which means, that you can take profit from using this method only near some neighbour of optimum.