Parabolic Interpolation

If a function $f(x)$ can be approximated by a parabola in the neighborhood of its minimum, then the vertex of the parabola can be used to approximate the minimum. Assuming we have available three points $a<b<c$ on the x-axis corresponding to function values $f(a)>f(b)<f(c)$, then a quadratic function $q(x)$ that goes through these points can be uniquely determined by the method of Lagrange interpolation:

$$q(x)=f(a)\frac{(x-b)(x-c)}{(a-b)(a-c)}+f(b)\frac{(x-c)(x-a)}{(b-c)(b-a)} +f(c)\frac{(x-a)(x-b)}{(c-a)(c-b)}$$ (17)

To find the minimum $q(x_{min})$ at the vertex of this quadratic function, we first set its derivative to zero:

$$q'(x)=f(a)\frac{(x-b)+(x-c)}{(a-b)(a-c)}+f(b)\frac{(x-c)+(x-a)}{(b-c)(b-a)} +f(c)\frac{(x-a)+(x-b)}{(c-a)(c-b)}=0$$ (18)

and multiply both sides by $(a-b)(b-c)(c-a)$:

$$f(a)(c-b)(2x-b-c)+f(b)(a-c)(2x-c-a)+f(c)(b-a)(2x-a-b)$$

$$= 2x[f(a)(c-b)+f(b)(a-c)+f(c)(b-a)] -[f(a)(c^2-b^2)+f(b)(a^2-c^2)+f(c)(b^2-a^2)]=0$$ (19)

and then solve the equation for $x$ to get:

$$x_{min} = \frac{1}{2}\frac{f(a)(c^2-b^2)+f(b)(a^2-c^2)+f(c)(b^2-a^2)}{f(a)(c-b)+f(b)(a-c)+f(c)(b-a)}$$

$$= b+\frac{1}{2}\frac{f(a)(c-b)(c+b-2b)+f(b)(a-c)(a+c-2b)+f(c)(b-a)(b+a-2b)}{f(a)(c-b)+f(b)(a-c)+f(c)(b-a)}$$

$$= b+\frac{1}{2}\frac{f(a)(c-b)^2+f(b)(a-c)(a+c-2b)-f(c)(b-a)^2}{f(a)(c-b)+f(b)(a-c)+f(c)(b-a)}$$

$$= b+\frac{1}{2}\frac{[f(a)-f(b)](c-b)^2-[f(c)-f(b)](b-a)^2}{[f(a)-f(b)](c-b)+[f(c)-f(b)](b-a)}$$ (20)

Unless $b$ is already at the vertex of $q(x)$, $f(x_{min})$ is smaller than $f(b)$, i.e., $x_{min}$ is closer to the minimum of $f(x)$ than $b$. This interpolation process can then be repeated using a set of three new points of $\{a, x_{min}, b\}$ if $x_{min}<b$ or $\{b, x_{min}, c\}$ if $x_{min}>b$.

In the unlikely case where the numerator of the second term in Eq. (20) is zero, i.e., $[f(a)-f(b)](c-b)^2=[f(c)-f(b)](b-a)^2$, we get $x_{min}=b$ and the iteration cannot proceed. We could choose some different point nearby to proceed.