# What is an efficient algorithm for finding the minimum of a parabola-shaped function? [closed]

I have a continuous function f(x) that is bounded on the interval (0, N), where N is a large positive integer (~10,000,000). The function is shaped like an upwards-facing parabola, however, it is slightly skewed (so not exactly parabolic). I am able to calculate values of f(x), however it is quite computationally expensive to sample.

What are some possible algorithms for efficiently and accurately approximating the minimum value of this parabola-shaped function using the smallest number of iterations?

• What is the dimension? Can you use optimization algorithms? Jun 6, 2022 at 23:55

The parabola going through $$(a,f(a))$$, $$(b,f(b))$$, $$(c,f(c))$$ has a minimum at $$G(a,b,c):=\frac{1}{2}\left( \frac{f(a)(b^2-c^2)+f(b)(c^2-a^2)+f(c)(a^2-b^2)}{f(a)(b-c)+f(b)(c-a)+f(c)(a-b)}\right)$$
So if you start with three reasonable guesses $$x_0$$, $$x_1$$ and $$x_2$$, you can iterate with $$x_{n+1}=G(x_{n-2}, x_{n-1}, x_n)$$ until you get whatever convergence you desire, and then take $$f$$ of the limit at the end.
• (+1) For a convex quadratic $f$, then this is of course exact with exactly 3 evaluations of $f$. But if we only know that $f$ "looks like" a parabola, I wonder how we can compare the efficiency of this approach compared to something like ternary search.
• @Sycorax: This looks basically like Newton's method in optimization, except instead of using first and second derivatives at a point we interpolate a parabola between multiple points. As such, it's probably faster for "well-behaved" functions but can be worse for pathological cases. (I also suspect that always replacing the first of the three sample points is suboptimal; replacing the one with the highest $f(x_i)$ value might work better.) Jun 7, 2022 at 10:30