[Tutorial] Variations of Golden-section Search on a Density Function

Taking a further step from my previous post, in this one, we are going to see the application of the Golden-section Search to a density function. If you are not quite familiar with the method yet, you might want to refer first here.

Motivational Problem

Suppose we have a function

f:[L,R]→[0,∞) satisfying

, which shows the spread of local minimum/maximum of a function

g:[L,R]→R that is unimodal. Denote $m$ as the minimum/maximum peak point of $g$, we aim to find a point $p$ such that

, where

ϵ represents an acceptable error and $ϵ<1$. We achieve this by only querying the value of the function at specific points, i.e., evaluating $f(x)$ for chosen values of $x$ in the interval $[L,R]$, as efficiently as possible.

Golden-section Search Method

Performing search based on the unimodal function

In the previous post, we have shown that in the Golden-section Search method, we usually want to have our pivot points to be located in both

L+(1−ϕ1​)(R−L) and $R-(1-\frac{1}{\varphi })(R-L)$. However, we notice that the number of queries depends on the value of $L$ and $R$; consequently, when the range between $L$ and $R$ is big enough (say they are approaching $-\infty$ and $\infty$), the number of queries used will also become bigger. That being said, performing a search based on function $g$ will not be reliable.

Performing search based on the density function

To make up for this, we need to make an adjustment for which interval we are going to query as our base. By using prior knowledge about the statistical method, we can focus our search on where the minimum / maximum is more likely to be found. Hence, we want to perform our search based on function

f. For the pivots that we needed, we want to set $p_1$ and $p_2$ as values that satisfy

and

This works well as after each transition; we manage to remove either

[L,p1​] or $[p_2,R]$ from our search space. Although, in a sense, it is quite hard to calculate the number of queries needed as $p_1$ and $p_2$ do not entirely depends on both $L$ and $R$, but also $f$. However, notice that we can always choose $p=\frac{L+R}{2}$ and $\delta =\frac{R-L}{2}$ in any valid interval that subject to $|m-p|\le \delta$. Denote $k$ as ${\int }_{p-\delta }^{p+\delta }f(x)dx$, let's analyze the two cases:

• Case

  KaTeX can only parse string typed expression
  [L,p1​] is removed from the interval $[L,R]$:
  $$\begin{array}{rlrl}p& :=\frac{p_1+R}{2}& & \\ \delta & :=\frac{R-p_1}{2}& & \\ k& :={\int }_{p_1}^{R}f(x)dx& & ={\int }_L^{R}f(x)dx-{\int }_L^{p_1}f(x)dx\\ & & & =\frac{1}{\varphi }{\int }_L^{R}f(x)dx\end{array}$$

• Case

  KaTeX can only parse string typed expression
  [p2​,R] is removed from the interval $[L,R]$:
  $$\begin{array}{rl}p& :=\frac{L+p_2}{2}\\ \delta & :=\frac{p_2-L}{2}\\ k& :={\int }_L^{p_2}f(x)dx=\frac{1}{\varphi }{\int }_L^{R}f(x)dx\end{array}$$

Each query allows us to reduce

k to $\frac{1}{\varphi }k$; denote $Q$ as the number of queries needed, then:

Additional Variation: Density Function

When encountering a similar function, say

f, that does not satisfy the ${\int }_{-\infty }^{\infty }f(x)dx=1$ condition, but still represents the spread of the peak point in a unimodal function, we can make a transformation to accommodate this scenario. We will transform the function $f(x)$ into $f^{\prime }(x)$ and $ϵ$ into ${ϵ}^{\prime }$, where:

and

. And there we have it! If prior knowledge about the function's behavior or specific features of the local minima/maxima is known, we can always customize the search strategy accordingly. This could involve using different weighting schemes or adapting the pivots.

© 2023 Yohandi. All rights reserved.