Dichotomous search algorithm in numeric optimization

1.7k Views Asked by At

If we assume that $\phi$ is convex and continuous in $[a,b]$, it is obvius that, in this interval, $\phi$ has a minimizer. The goal is know what point is it.

The main idea of Dichotomous search is reduce the size of the interval what is the minimizer evaluating $\phi$ into two points, $\overline{a}, \overline{b} \in (a,b) : \overline{a} < \overline{b} $.

For this, the algorithm uses the fact that if $\phi(\overline{a}) < \phi(\overline{b})$, the minium of $\phi$ in $[a,b]$ is contained in the interval $[a,\overline{b}]$. And $\phi(\overline{a}) \geq \phi(\overline{b})$, the minium of $\phi$ in $[a,b]$ is contained in the interval $[\overline{a},b]$

Therefore, the Dichotomous algorithm computes the midpoint of the interval (step-by-step), $\frac{a+b}{2}$ and, then moves slightly to either side of the midpoint to compute two test points: $\frac{a+b}{2} \pm \varepsilon$, where $\varepsilon$ is a very small number.

Why need to move slightly to either side of the midpoint?

1

There are 1 best solutions below

4
On BEST ANSWER

The reason is that you need to evaluate the function at two points, $\bar{a}$ and $\bar{b}$. The closer those $\bar{b}$ is to $a$, and the closer $\bar{a}$ is to $b$, the further you can shrink the interval, so you want $\bar{a}$ and $\bar{b}$ to be close to each other.