Check if two functions are identical

Question

I am studying the so called Max Min Plus Scaling (MMPS) systems that are defined as functions containg max, min, sum and multiplication by a scalar operation. An example is the function $f(x) = \max(5x+3,3x-8)-\min(-x,4x-2)+5x-7$. I want to find out how to determine that two MMPS are identical, meaning that they assume the same values $\forall x \in \mathbb{R}$. This is not trivial, since many functions are actually the same even though they seem different. For instance, the three functions $$g(x)=\max(-x,x)\\h(x)=\max(\min(-x,-2x),\min(x,2x))\\i(x)=\max(\min(-x,-3x),x)$$ are all identical (they all correspond to the function $f(x)=|x|$).

How can I prove if two MMPS functions are the same? I could rewrite the two MMPS functions in the canonical form which means I am writing the MMPS as a min of max functions, or as a max of min functions, but then I don't know how to proceed because for instance $h_1(x)=\max(\min(-x,-2x),\min(x,2x))$ and $h_2(x)=\max(\min(-x,-5x),\min(x,5x))$ are both in canonical form but they are identical. In other words, one function $f(x)$ may have infinite canonical forms.

Answer 1

When dealing with this kind of functions, you should divide the range of function so that you could eliminate canonical forms then prove that they are identical in fact. For demonstration, let's prove that your $f,g,i$ are same by dividing the range of function.

Note that the parameters of $\max$s and $\min$s in your $g,h,i$ are integer multiples of $x$ or their $\max$, $\min$ result. Therefore, we only need to consider two cases: $x \ge 0$ and $x<0$.

i) $x \ge 0$

$2x \ge x \ge 0 \ge -x \ge -2x \ge -3x$. Therefore $$g(x)=\max(-x,x)=x\\h(x)=\max(\min(-x,-2x),\min(x,2x))=\max(-2x,x)=x\\i(x)=\max(\min(-x,-3x),x)=\max(-3x,x)=x$$

ii) $x < 0$

$2x < x < 0 < -x < -2x < -3x$. Therefore $$g(x)=\max(-x,x)=-x\\h(x)=\max(\min(-x,-2x),\min(x,2x))=\max(-x,2x)=-x\\i(x)=\max(\min(-x,-3x),x)=\max(-x,x)=-x$$

By i) and ii), $g,h,i$ are identical.

Answer 2

Let $PL$ be the set of piecewise linear functions over a finite number of intervals, that means

$$f(x) \in PL: \exists c_1 < \ldots < c_n \in \Bbb R, f(x) {\space \rm is \space linear \space over \space} [c_i,c_{i+1}], i=1,\ldots,{n-1} {\space \rm and \space over \space} (-\infty,c_1], [c_n,\infty)$$

Let's call any choice for $c_1,\ldots,c_n$ above a $support$ of $f(x)$.

I think that $PL=MMPS$, but at least it is easy to show that $MMPS \subseteq PL$. That is because you start with $x$, which is linear and also piecewise linear, and when you do multiplication with a scalar you go from $f(x) \in PL$ to $af(x) \in PL$ with the same support.

If you add two functions $f,g$ from $PL$, then the sum is in $PL$ as well, with the union of any support of $f$ with any support of $g$ being a support of the sum.

If you take the max/min of any two functions $f,g \in PL$, then again consider the union of any support of $f$ with any support of $g$, which we call $s_1 < \ldots < s_n$. Over $(-\infty,s_1], [s_1,s_2],\ldots,[s_{n-1},s_n],[s_n,\infty)$ the min/max of $f$ and $g$ is just the min/max of linear functions. Depending on whether those linear functions intersect in the interval or not, the min/max on that interval is either linear or piecewise linear with one additional support (the x-value where the two linear functions intersect). That means the min/max of $f,g$ is also piecewise linear.

If you have 2 MMPS functions $f$ and $g$, then you (or some software) needs to calculate a support of $f-g$. This is the conceptually easy but boring part: you start with the innermost subfunctions: They are linear, so just choose support $c_1=0$. When you calculate sums and min/max, do as I have outlined above.

Eventually, you need to check that $f(s)=g(s)$ for all $s$ in a support of $f-g$ as well as for some $s$ that is smaller then the smallest member of that support and for some $s$ that is larger then the largest member of that support. If that is not true, then obviously $f \neq g$. If it is true, then they are equal.

Answer 3

Recursively, from the inside, progressing outwards, you can convert an MMPS function to a piecewise linear function, with domain $(-\infty,\infty)$, and with finitely many pieces, such that

• Each piece is defined on its own closed interval (except the unbounded intervals, which will be open in the unbounded direction).
• The domain intervals overlap adjacent domain intervals at their endpoints, and only at those points.
• No two adjacent pieces have the same formula (if that happens at an intermediate stage, the pieces can be merged).

If an MMPS function is expressed in the form described above, call it a PLF function ("Piecewise Linear Form" function).

Operations on PLF functions:

• To scale a PLF function, just scale the formula on each piece, leaving the domain intervals unchanged.
• To add two PLF functions, the set of separating points for the new domain intervals will be the union of the separating points for the functions being added. Then simply add the formulas of each function, restricted to each of the new domain intervals. When done, merge adjacent pieces if they have the same formula.
• To find the min or max of two PLF functions, the process is the same as for adding, except perform a min or max rather than an add. If the line segments for the pieces on one of the new domain intervals intersect inside interval, the new interval needs to be split into two intervals with appropriate choice of min or max on each of the two subintervals created by the split. When done, merge adjacent pieces if they have the same formula.

Two MMPS functions expressed as PLF functions will be equal if and only if they have the same set of domain intervals, and for each such interval, the associated linear function is the same.

The process can tedious to do by hand, so it would probably be a good idea to implement the process as a computer program.