# Idea

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

# Algorithm

```
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
```

# Bounds

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.