One-dimensional search methods

234 Views Asked by At

Among the one-dimensional search methods there are some, such as the one of the golden-section search, that only use the function, and others such as the one of the bisection, that use the derivative of the function.

Do you think that something similar to the bisection method could be done, but using only the value of the function, without derivatives? That is, take the average value of the interval and evaluate it to reduce the interval in each iteration in half

2

There are 2 best solutions below

2
On BEST ANSWER

Knowing the value of $f$ at the midpoint and the left and right ends of an interval is not sufficient by itself to determine whether the minimum is in the left half or right half of the interval. It's easy to construct examples to see this.

For example, if $f(0)=2$, $f(1)=1$, and $f(2)=2$, you can't tell whether the minimum is in the interval from 0 to 1 or the interval from 1 to 2.

1
On

There is ternary search. It is a generalization of binary search for finding the maximum (or minimum) of a unimodal function. The idea is, you split the search space $[a, b)$ into three (approximately) equal parts, $[a, m)$, $[m, n)$, and $[n, b)$, and can discard one of the side ones. If $f(m) < f(n)$, then your maximum is in $[m, b)$. If $f(m) \geq f(n)$, then the maximum is in $[a, n)$.