Minimize Discrete Integral

161 Views Asked by At

Assuming i have discrete samples of a function and thereby estimate a continuous function $f(x)$ by connecting the samples linearly with each other. Could look for example like this:

is there an easy way to minimize $b - a$ for:

\begin{equation} \int _{a}^{b}f(x)dx = n\ \end{equation}

where $n$ is a constant?

Or in words: We are looking for the area below the function, with the smallest width ($b -a$), with a size equal to a constant $n$.

1

There are 1 best solutions below

0
On

If I haven't made mistakes somewhere then I think this is a criterion for local minima:

If $f > 0$ is continuous and piecewise linear then critical points of $t = g(a)$ correspond to $(a,b) = (a, a+t)$ such that:

  • $f(a) = f(b)$
  • the area under $f$ between $a$ and $b$ equals $n$

and they are local minima if furthermore:

  • $f'(a)f(b)^2 > f'(b)f(a)^2$

Setup

If we can assume $f$ is positive and continuous as in the example, then for any fixed $a$, the equation $\int_a^{a+t} f(x)\,dx = n$ is satisfied for at most one value of $t$. This defines another function $t = g(a)$. You can differentiate this function with respect to $a$, and basically use single variable calculus ways of finding the minimum.

Find critical points

Let's compute the derivative of $g$ at a point $(a,t)$ to check if it's a local extremum. Set $t + \Delta t$ and $a + \Delta a$, this changes the integral by

$$\Delta I = \int_{b}^{b + \Delta b}f(x)\,dx - \int_{a}^{a+\Delta a}f(x)\,dx = (f'(b)\Delta b + f(b))\Delta b - (f'(a)\Delta a + f(a))\Delta a $$

(Note: we used piecewise linearity to compute the integrals here)

Setting $\Delta b = \Delta a + \Delta t$ and using $\Delta I = 0$ we can now solve a quadratic equation for $\Delta t$ to get:

$$\dfrac {\Delta t} {\Delta a} = \dfrac {-(f(b) + f'(b)\Delta a) + \sqrt{ (f(b) + f'(b)\Delta a)^2 - 4f'(b)\Delta a((f'(b)-f'(a))\Delta a + f(b) - f(a)) } } {2f'(b)\Delta a} $$

Now take the limit as $\Delta a \to 0$.

Use the difference of squares to evaluate the limit, as in $\frac{-A + \sqrt{A^2 + B}}{C} = \frac{B}{\left(A + \sqrt{A^2 + B}\right)C}$.

This leads to:

$$ \dfrac { 4f'(b)\Delta a((f'(b)-f'(a))\Delta a - f(b) + f(a)) } { \left( -(f(b) + f'(b)\Delta a) - \sqrt{ (f(b) + f'(b)\Delta a)^2 - 4f'(b)\Delta a((f'(b)-f'(a))\Delta a + f(b) - f(a)) } \right) 2f'(b)\Delta a} $$ $$\longrightarrow \dfrac {4f'(b)(f(a)-f(b))} {-4f(b)f'(b)} = \dfrac {f(a)-f(b)} {f(b)} $$

So $\dfrac{dg}{da} = \dfrac {f(a)-f(b)} {f(b)}$ so we get a critical point if $f(a) = f(b)$. This is mentioned much more briefly in someone's comment.

Classify local extrema

Now you may use a second derivative test. Namely, we computed above that $$g'(a) = \dfrac{f(a)}{f(b)} - 1$$ so now $$g''(a) = f'(a)/f(b) - f'(b)\cdot b'\cdot f(a)/f(b)^2$$ where $b' = (a + g(a))' = 1 + g'(a) = f(a)/f(b)$ so that $$g''(a) = f'(a)/f(b) - f'(b)f(a)^2/f(b)^3$$ Assuming $f$ is positive again, then $g''(a) > 0$ translates to $$f'(a)f(b)^2 > f'(b)f(a)^2$$


Note: $f'(a)/f'(b) - (f(a)/f(b))^2 > 0$ does look reminiscent of second partial derivative test so maybe there is a more slick way of doing this, but I didn't think carefully about that.