1
$\begingroup$

The description:

I have a number of similar piecewise functions, where $d$ is the translation distance lets assume this is the function (where a and b are known constants): $$f(x-d) = \left\{ \begin{array}{l} a-b(x-d) & \text{if } 0 \le x-d < \frac{a}{b}\\ a+b(x-d) & \text{if } -\frac{a}{b} < x-d < 0 \end{array} \right.$$ Example

when $d$ is small we will have a number of them overlapping ($d$ is always bigger than zero) and as $d$ gets big fewer will overlap until they are are barley touching and that is the maximum $d$ (since we cannot have any area in the middle that is not covered by at least one function).

The value that I care about is the sum of these functions, so overlapping areas add up (it is like stacking these graphs on top of each other) and my total function is: $$f_\text{total}(x) = \sum_{n=0}^{i} f(x-nd)$$ $i$ is the number of functions in a system

The problem:

I want to optimize the system by finding the maximum $d$ that still satisfy the condition: $$f_\text{total}(x) \ge z$$ $z$ is defined based on the system requirement (known value)

The question:

How can I solve this? what type of mathematical methods will help me accomplish this?

I did it on Matlab by simply running a loop and incrementing $d$ by some small value until the condition is not satisfied, however, to get an accurate result I need to increment $d$ by a very tiny value and the computation will take a very long time.

Update:

Here is a Matlab simulation of the function translation as we increase $d$ until it reaches the maximum value $2\frac{a}{b}$, the thick black line is the sum of these function $f_\text{total}(x)$. I realized from this that the lowest point in the sum is always at point $x$ where two adjacent nodes intersect.

Example2

$\endgroup$
  • 1
    $\begingroup$ I would not describe the peak-to-peak distance $d$ as the "distance between functions" but rather the translation distance or distance between nodes. $\endgroup$ – hardmath Apr 3 '15 at 23:32
  • $\begingroup$ I'm not sure how familiar you may be with the "hat" functions as a basis for piecewise linear functions, but your problem is new to me. With the so-called "hat functions" the basis is formed by translating one function a distance $d$ that is exactly half the (symmetrical) support size of that function, i.e. $d = a/b$ in your notation. Apparently you contemplate distances $d$ that are arbitrary proportions of that, so that your functions pack more closely together. $\endgroup$ – hardmath Apr 6 '15 at 21:25
  • $\begingroup$ The sum is over all the hats or just over the overlap (of two or more) of them? $\endgroup$ – nicoguaro Apr 6 '15 at 22:20
  • $\begingroup$ @hardmath I looked at the hat functions which is exactly what I have, but unfortunately it didn't help me much, since my math skills are not really good. $\endgroup$ – Fahad Alduraibi Apr 8 '15 at 19:30
  • $\begingroup$ @nicoguaro the sum is over all of them, check the animated GIF image which I have added to the problem description. $\endgroup$ – Fahad Alduraibi Apr 8 '15 at 19:31
5
$\begingroup$

As a general rule in developing and testing numerical software, I try to eliminate as many parameters as possible. I'm sure it has occurred to you that the distance $d$ and "floor" $z$ are scalable for specified values of $a$ and $b$.

In particular the maximum of the reference "hat" function:

$$ f(x) = a \cdot \left(1 - \frac{|x|}{a/b} \right) \;\; \text{ on } \;\;(-a/b,+a/b) $$

occurs at $x=0$, where $f(0) = a$. So we can factor $a$ out of each hat function, and modify the floor $z$ to be instead $z/a$. Effectively we will take $a=1$.

Similarly the horizontal scale of distances is relative to the size of the interval $(-a/b,+a/b)$, so that if you also set $b=1$ we can treat $d$ as a multiple of the interval half-length $a/b = 1$. Knowing the solution $d$ for given $z$ with $a=b=1$ allows us to give the solutions for any $a,b,z$ with a simple scaling.

To make all this concrete, define the special case of the original problem where:

$$ F(x) = 1 - |x| \;\; \text{ on } \;\; (-1,+1) $$

and otherwise $F(x) = 0$. We reduce the original problem to the special case by taking $Z = z/a$, and then asking for the maximum distance $D$ such that:

$$ F_{\text{total}}(x) \equiv \sum_{k\in \mathbb{Z}} F(x - kD) \ge Z $$

Then an original problem with arbitrary $a,b,z \gt 0$ would have a solution $d = (a/b)D$.

To solve the special case, start with $D=2$. The sum of our functions $F_{\text{total}}(x)=\sum_k F(x-kD)$ is a simple sawtooth wave with a peak (maximum) value $1$ at every even integer and a floor (minimum) value zero at every odd integer, i.e. periodic of length $D=2$. Thus $D=2$ would be our maximum only if $Z \le 0$, which is probably not interesting. We therefore consider how to reduce the peak-to-peak distance $D$ until everywhere $F_{\text{total}} \ge Z$.

If we cut $D$ by half, so $D=1$, the effect is to make $F_{\text{total}}$ a constant function, $F_{\text{total}}(x)=1$.

Repeatedly "halving" $D$ exactly, e.g. $D = 2^{-n}$, will again produce constant functions (something that can be glimpsed in your animated GIF). For $D = 2^{-n}$, $F_{\text{total}}(x) = 2^n$.

Therefore we can quickly "bracket" the maximum value of $D$ by finding nonnegative integer $n$ such that:

$$ 2^n \le Z \lt 2^{n+1} $$

This cuts down considerably on the effort required to find the maximum distance $D$. But more can be said, so that eventually a fairly explicit expression for $D$ in terms of $Z$ can be given.


Despite the infinite number of summands appearing in the definition, $F_{\text{total}}(x)$ gets nonzero contributions at any particular real $x$ from only finitely many summands. The regular spacing $D$ between hat functions $F(x-kD)$ allows us to bound the number whose supports contain a common point. If $|kD| \gt 2$, then $F(x)$ and $F(x-kD)$ have supports with empty intersection, so a particular point is in the support of at most $\lfloor 2/D \rfloor$ hat functions. From this "local" finiteness it follows that $F_{\text{total}}$ is continuous and piecewise linear.

The regular spacing $D$ makes $F_{\text{total}}$ periodic with period $D$. Since the reference hat function $F(x)$ is even:

$$ F(x) = F(-x) $$

$F_{\text{total}}$ is also even and symmetric about $x = D/2$:

$$ F_{\text{total}}(x + D/2) = F_{\text{total}}(-x + D/2) $$

By its periodicity it suffices to consider the restriction of $F_{\text{total}}$ to $[0,D]$, and its minimum there (resp. its maximum there) will be the global minimum (resp. global maximum).

Indeed because peaks of our hat functions occur only to the left or to the right of $[0,D]$, the summands' restrictions to it are convex (concave up). It follows that $F_{\text{total}}$ is convex on $[0,D]$. Thus by the symmetry already noted, the minimum occurs at the midpoint $x = D/2$ while the maximum occurs at endpoints $x=0,D$.

The supports of hat functions containing the minimizing argument $x = D/2$ lie symmetrically to its left and right. On the left $D/2$ is in the support of $F(x+kD)$ for $k \ge 0$ if and only if:

$$ \frac{D}{2} + kD \le 1 $$

$$ k \le \frac{1}{D} - \frac{1}{2} $$

It follows that to the left of $D/2$ we have $\lfloor D^{-1} + 1/2 \rfloor$ contributing summands:

$$k = 0,\ldots,\lfloor D^{-1} - 1/2 \rfloor $$

and an equal number of equal contributions to the right. Thus:

$$ \begin{align*} F_{\text{total}}(D/2) &= 2 \sum_{k=0}^{\lfloor D^{-1} - 1/2 \rfloor} F(kD + D/2) \\ &= 2 \sum_{k=0}^{\lfloor D^{-1} - 1/2 \rfloor} (1 - (k+1/2)D) \end{align*} $$

Gauss's trick of summing an arithmetic sequence applies, absorbing the factor $2$:

$$ \begin{align*} F_{\text{total}}(D/2) &= \lfloor D^{-1} + 1/2 \rfloor \cdot \left[\left(1 - \frac{D}{2}\right) + \left(1 - \left(\lfloor D^{-1} - 1/2 \rfloor + 1/2 \right) D \right) \right] \\ &= \lfloor D^{-1} + 1/2 \rfloor \cdot [2 - \lfloor D^{-1} + 1/2 \rfloor D] \end{align*} $$

Despite the evident jump in $\lfloor D^{-1} + 1/2 \rfloor$ when $D^{-1}$ is an integer plus one-half, the above expression for $F_{\text{total}}(D/2)$ is continuous there and elsewhere. Confirmation of this is left as "an exercise for the Reader".

Note that when $D^{-1} = n$, a positive integer, $\lfloor D^{-1} + 1/2 \rfloor = n$ and:

$$ F_{\text{total}}(D/2) = n \cdot [2 - 1] = n $$

On the other hand, when $D^{-1} + 1/2 = n$ is a positive integer, then $D = (n - 1/2)^{-1}$ and:

$$ F_{\text{total}}(D/2) = n \left[2 - \frac{n}{n - 1/2} \right] = n \cdot \frac{n-1}{n - 1/2} \lt n $$

So $F_{\text{total}}(D/2)$ is strictly increasing as $D$ decreases, and when $D \in [(n-1/2)^{-1}, (n+1/2)^{-1}]$, we have a linear dependence of $F_{\text{total}}(D/2)$ on $D$.

Determining the maximum $D$ for which everywhere $F_{\text{total}}(x) \ge Z$ amounts to solving for $D$:

$$ F_{\text{total}}(D/2) = Z $$

Let $n = \lfloor Z \rfloor$. Then $(n+1)^{-1} \lt D \le n^{-1}$.

It remains only to compute $F_{\text{total}}(D/2)$ at $D = (n + 1/2)^{-1}$ to learn whether $Z = F_{\text{total}}(D/2)$ is attained for $D \in ((n+1)^{-1},(n + 1/2)^{-1}]$ or $D \in ((n+1/2)^{-1}, n^{-1}]$.

The exact answer may be found, whichever subinterval is correct, by linear interpolation on $D$, because in either case we have reduced the term $\lfloor D^{-1} + 1/2 \rfloor$ to a constant.

$\endgroup$
  • $\begingroup$ Thanks for the answer and the approach I really appreciate your efforts, it is still not the answer I am looking for, but it will help. $\endgroup$ – Fahad Alduraibi Apr 13 '15 at 15:50
  • $\begingroup$ I will fill in all the details. $\endgroup$ – hardmath Apr 13 '15 at 16:09
  • $\begingroup$ If the details are hard to digest, perhaps you can propose values for $a,b,z$ and I can quickly show how to find $d$ to illustrate the use of the formulas. $\endgroup$ – hardmath Apr 14 '15 at 18:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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