5
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ What is the dimension? Can you use optimization algorithms? $\endgroup$
    – Onyambu
    Jun 6, 2022 at 23:55

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ (+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. $\endgroup$
    – Sycorax
    Jun 7, 2022 at 1:20
  • 1
    $\begingroup$ @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.) $\endgroup$ Jun 7, 2022 at 10:30
5
$\begingroup$

Ternary search is a simple algorithm to find the minimum (or maximum) of a unimodal function without using any derivative information. It proceeds by starting with some interval, and then recursively discards one-third of the interval until some tolerance is reached.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.