The World of Piecewise Max/Min

April 02, 2021 | 12 minutes, 28 seconds

Creating our Functions

Simple Definition

Suppose we want two functions that describe the largest and the smallest of two numbers, say \(a\) and \(b\). We can define those two functions as functions in two variables each. One, which gives the largest, and one which gives the smallest.

For our 'maximum' function, we return \(a\) if \(a\) is bigger than \(b\), or \(b\) if \(b\) is bigger than \(a\). Of course, we have to include the cases wherein they're equal, but that's easy enough to do because that means they'll both be the largest. Hence we have:

\[ \operatorname{max}\left(a,b\right) = \begin{cases} a & a \geq b \\ b & b \geq a \end{cases}\]

Similarly for our 'minimum' function, we return \(a\) if \(a\) is smaller than \(b\), or \(b\) if \(b\) is smaller than \(a\). Again, we can account for equality easily:

\[ \operatorname{min}\left(a,b\right) = \begin{cases} a & a \leq b \\ b & b \leq a \end{cases}\]

Absolute value-form of Max/Min

Our above piecewise functions can easily describe these functions in two variables, but we don't know what they actually mean in terms of elementary functions we already know. However, we can easily recognise they do look relatively similar to say the absolute value function, just in terms of \(a\) and \(b\) and combinations thereof instead of \(x\). The following derivations are based on an intuition playing with piecewise equations; I strongly encourage you to play around with them to get a working understanding of some of the strategies when trying to achieve a recognisable form for them.

We can begin with our 'maximum' function, to derive a formula which we understand (note that this is a derivation but also does prove equality by the means we use to derive it. You can double check this by proving case-by-case.):

\[ \begin{align} \operatorname{max}(a,b) &= \begin{cases} a & a \geq b \\ b & b \geq a \end{cases} \\ &= \begin{cases} a & a \geq b \\ b & a \leq b \end{cases} \\ &= \begin{cases} a-b & a-b \geq 0 \\ 0 & a-b \leq 0 \end{cases} + b \\ &= \frac{1}{2}\left(\begin{cases} 2\left(a-b\right) & a-b \geq 0 \\ 0 & a-b \leq 0 \end{cases}\right) + b \\ &= \frac{1}{2}\left(\begin{cases} a-b & a-b \geq 0 \\ -\left(a-b\right) & a-b \leq 0 \end{cases}+a-b\right) + b \\ &= \frac{1}{2}\left(a+b+\left|a-b\right|\right) \\ \end{align}\]

We can apply a similar process to our 'minimum' function:

\[ \begin{align} \operatorname{min}(a,b) &= \begin{cases} b & a \geq b \\ a & b \geq a \end{cases} \\ &= \begin{cases} b & a \geq b \\ a & a \leq b \end{cases} \\ &= \begin{cases} 0 & a-b \geq 0 \\ a-b & a-b \leq 0 \end{cases} + b \\ &= \frac{1}{2}\left(\begin{cases} 0 & a-b \geq 0 \\ 2\left(a-b\right) & a-b \leq 0 \end{cases}\right) + b \\ &= \frac{1}{2}\left(-\begin{cases} a-b & a-b \geq 0 \\ -\left(a-b\right) & a-b \leq 0 \end{cases}+a-b\right) + b \\ &= \frac{1}{2}\left(a+b-\left|a-b\right|\right) \\ \end{align}\]

TL;DR - Geometrically speaking: When we want the biggest number of two numbers, we take the average of those two numbers and add half the distance between them. When we want the smallest, we take the average again but instead take away half the distance between them (which is always positive).


Now that we have the definitions of our functions with two variables, we can try extending them to allow sets as inputs; i.e. we want to find the maximum value in a set, and the minimum value in a set, if they exist respectively.


\[ \operatorname{max}\left(S\right) = \begin{cases} s_{1} & s_{1} \geq \operatorname{max}\left(S\setminus \{s_{1}\}\right) \\ s_{2} & s_{2} \geq \operatorname{max}\left(S\setminus \{s_{2}\}\right) \\ \vdots & \vdots \\ s_{n} & s_{n} \geq \operatorname{max}\left(S\setminus \{s_{n}\}\right) \\ \end{cases}\]

and \(\operatorname{max}\{a\}=a\). Given this definition, we can see that our original definition for a set with 2 elements holds.


\[ \operatorname{min}\left(S\right) = \begin{cases} s_{1} & s_{1} \leq \operatorname{min}\left(S\setminus \{s_{1}\}\right) \\ s_{2} & s_{2} \leq \operatorname{min}\left(S\setminus \{s_{2}\}\right) \\ \vdots & \vdots \\ s_{n} & s_{n} \leq \operatorname{min}\left(S\setminus \{s_{n}\}\right) \\ \end{cases}\]

and \(\operatorname{min}\{a\}=a\). Given this definition, we can see that our original definition for a set with 2 elements holds.


Union Property

\(\operatorname{max}\left(S\cup T \right) = \operatorname{max}\{\operatorname{max}\left(S\right),\operatorname{max}\left(T\right)\}\)

\(\operatorname{min}\left(S\cup T \right) = \operatorname{min}\{\operatorname{min}\left(S\right),\operatorname{min}\left(T\right)\}\)

This only works if each of the respective sets have a defined respective maximum/minimum and the overall set has a defined maximum/minimum.

For the sake of keeping this post short, and not copying essentially the same steps, I'll provide a proof of this for the maximum function we have.

Claim: Suppose we have \(T \subseteq S\). Then provided \(\operatorname{max}\left(S\setminus T\right)\), \(\operatorname{max}\left(T\right)\) and \(\operatorname{max}\left(S\right)\) exist, then we have that \(\operatorname{max}\{\operatorname{max}\left(S\setminus T\right), \operatorname{max}\left(T\right)\} = \operatorname{max}\left(S\right)\).

By the definition of our maximum function, we have that:

\[ \operatorname{max}\{\operatorname{max}\left(S\setminus T\right), \operatorname{max}\left(T\right)\} = \begin{cases} \operatorname{max}\left(S\setminus T\right) & \operatorname{max}\left(S\setminus T\right) \geq \operatorname{max}\left(T\right) \\ \operatorname{max}\left(T\right) & \operatorname{max}\left(S\setminus T\right) \leq \operatorname{max}\left(T\right) \end{cases}\]

Let \(s = \operatorname{max}\left(S\right)\). This means that \(s \geq \operatorname{max}\left(S\setminus T\right)\) and \(s \geq \operatorname{max}\left(T\right)\), and that we have two cases only (because checking elements in \(S\setminus T\) and \(T\) mean we check all elements of \(S\)):

1. \(s \in S\setminus T: \operatorname{max}\left(S\setminus T\right) = s\)

By our earlier definition:

\[ \begin{align} \operatorname{max}\{\operatorname{max}\left(S\setminus T\right), \operatorname{max}\left(T\right)\} &= \begin{cases} \operatorname{max}\left(S\setminus T\right) & \operatorname{max}\left(S\setminus T\right) \geq \operatorname{max}\left(T\right) \\ \operatorname{max}\left(T\right) & \operatorname{max}\left(S\setminus T\right) \leq \operatorname{max}\left(T\right) \end{cases} \\ &= \begin{cases} s & s \geq \operatorname{max}\left(T\right) \\ \operatorname{max}\left(T\right) & s \leq \operatorname{max}\left(T\right) \end{cases} \\ &= s \end{align}\]

2. \(s \in T: \operatorname{max}\left(T\right) = s\)


\[ \begin{align} \operatorname{max}\{\operatorname{max}\left(S\setminus T\right), \operatorname{max}\left(T\right)\} &= \begin{cases} \operatorname{max}\left(S\setminus T\right) & \operatorname{max}\left(S\setminus T\right) \geq \operatorname{max}\left(T\right) \\ \operatorname{max}\left(T\right) & \operatorname{max}\left(S\setminus T\right) \leq \operatorname{max}\left(T\right) \end{cases} \\ &= \begin{cases} \operatorname{max}\left(S\setminus T\right) & \operatorname{max}\left(S\setminus T\right) \geq s \\ s & \operatorname{max}\left(S\setminus T\right) \leq s \end{cases} \\ &= s \end{align}\]

As both cases yield \(s\) we have shown that \(\operatorname{max}\{\operatorname{max}\left(S\setminus T\right), \operatorname{max}\left(T\right)\} = s = \operatorname{max}\left(S\right)\).

Finally, letting \(S = P \cup T\) we have the property shown above.

Good example to let you wrap your head around this property: Simplify \(\operatorname{max}\{\operatorname{max}\{a,b\},c,d\}\)

The input of the max function is a set of 3 elements in particular. Let's split the set into the following two subsets: \(\{\operatorname{max}\{a,b\}\}\) and \(\{c, d\}\).

By our property, we then have \(\operatorname{max}\{\operatorname{max}\{\operatorname{max}\{a,b\}\}, \operatorname{max}\{c, d\}\}\).

By the definition of our max function, we then have \(\operatorname{max}\{\operatorname{max}\{a,b\}, \operatorname{max}\{c, d\}\}\).

Applying our property again combining our two subsets \(\{a,b\}\) and \(\{c,d\}\) we get: \(\operatorname{max}\{a,b,c,d\}\).

Please note, that usually these steps are more intuition than anything else, so long as this base property holds, it's fine (unless you need to, for some reason, definitively prove it works in your case).

Addition Property

\(\operatorname{max}\left(S\right) + k = \operatorname{max}\{ s + k : s \in S \}\)

\(\operatorname{min}\left(S\right) + k = \operatorname{min}\{ s + k : s \in S \}\)

(Note again we're only showing this for the maximum function - using the same process, this property is also easy to show for the minimum function)

This will only be a sketch of a proof. Since our definition is recursive, we can prove this property for the maximum function with an input set with 2 elements, and it holds for sets with any more than that number of elements in it also. In essence, we can recursively use the following:

\[ x + k \geq \operatorname{max}\left(S\setminus \{x\}\right)+k \implies x + k \geq \operatorname{max}\{y+k:y\in S\setminus \{x\}\}\]

If you want to see this, you can expand the piecewise definition for sets with any length and you'll eventually reach the same conclusion.


\[ \begin{align} \operatorname{max}\{a,b\} &= \begin{cases} a & a \geq b \\ b & b \geq a \end{cases} \\ \operatorname{max}\{a,b\} + k &= \begin{cases} a & a \geq b \\ b & b \geq a \end{cases} + k \\ &= \begin{cases} a+k & a \geq b \\ b+k & b \geq a \end{cases} \\ &= \begin{cases} a+k & a+k \geq b+k \\ b+k & b+k \geq a+k \end{cases} \\ &= \operatorname{max}\{a+k,b+k\} \end{align}\]

Multiplication Properties

\(a\times \operatorname{max}\left(S\right) = \begin{cases} \operatorname{max}\{a\times s:s\in S\} & a \geq 0 \\ \operatorname{min}\{-a\times s:s\in S\} & a \leq 0 \end{cases}\)

\(a\times \operatorname{min}\left(S\right) = \begin{cases} \operatorname{min}\{a\times s:s\in S\} & a \geq 0 \\ \operatorname{max}\{-a\times s:s\in S\} & a \leq 0 \end{cases}\)

And yet again we'll only do this for the maximum function; the steps are similar enough for the minimum function. We'll also only do this for the 2 element set definition; it's also easy enough to show this works for larger sets via our recursive definition.

Suppose we have \(a \geq 0\):

\[ \begin{align} \operatorname{max}\{p,q\} &= \begin{cases} p & p \geq q \\ q & q \geq p \end{cases} \\ a\times \operatorname{max}\{p,q\} &= a\times \begin{cases} p & p \geq q \\ q & q \geq p \end{cases} \\ &= \begin{cases} ap & p \geq q \\ aq & q \geq p \end{cases} \\ &= \begin{cases} ap & ap \geq aq \\ aq & aq \geq ap \end{cases} \\ &= \operatorname{max}\{ap, aq\} \end{align}\]

For \(a \leq 0\):

\[ \begin{align} \operatorname{max}\{p,q\} &= \begin{cases} p & p \geq q \\ q & q \geq p \end{cases} \\ a\times \operatorname{max}\{p,q\} &= a\times \begin{cases} p & p \geq q \\ q & q \geq p \end{cases} \\ &= \begin{cases} ap & p \geq q \\ aq & q \geq p \end{cases} \\ &= \begin{cases} ap & ap \leq aq \\ aq & aq \leq ap \end{cases} \\ &= \operatorname{min}\{ap, aq\} \end{align}\]

Alternative \(\left|x\right|\) Definition

\(\left|x\right| = \operatorname{max}\{x,-x\}\)

\(\left|x\right| = -\operatorname{min}\{x,-x\}\)

Firstly, there are a lot more properties than the ones I've listed above. However, the ones I've listed at the ones that are most relevant to me and will, at some point, be used. If you do have any more ideas though, and would like to suggest them, you can email me at any time.

I've listed this under properties because it is a nice relation back to what we already know, on top of the formulas for max/min functions given respectively. In fact, using those definitions are one way to get the definitions above.

The alternative is this:

\[ \begin{align} \left|x\right| &= \begin{cases} x & x \geq 0 \\ -x & x \leq 0 \end{cases} \\ &=\begin{cases} x & 2x \geq 0 \\ -x & 2x \leq 0 \end{cases} \\ &=\begin{cases} x & x \geq -x \\ -x & x \leq -x \end{cases} \\ &= \operatorname{max}\{x,-x\} \end{align}\]


\[ \begin{align} \left|x\right| &= \begin{cases} x & x \geq 0 \\ -x & x \leq 0 \end{cases} \\ &= -\begin{cases} -x & 2x \geq 0 \\ x & 2x \leq 0 \end{cases} \\ &=-\begin{cases} -x & x \geq -x \\ x & x \leq -x \end{cases} \\ &= -\operatorname{min}\{x,-x\} \end{align}\]

The reason we would like these definitions is so that we could easily combine them with expressions involving the maximum/minimum functions, rather than the converse, which is incredibly difficult or even downright impossible.

An example: Rewrite the expression in terms of the maximum function: \(\operatorname{max}\{y,-y-1\}+|y|\).

Using this definition we have \(\operatorname{max}\{y,-y-1\}+\operatorname{max}\{y,-y\}\).

Then, we can apply the addition properties twice; one, for moving our absolute value in, then second, for simplifying each term inside the max.

\(\operatorname{max}\{\operatorname{max}\{2y,0\}, \operatorname{max}\{-1,-2y-1\}\}\)

Applying our union property to get \(\operatorname{max}\{2y,0,-1,-2y-1\}\) and simplifying we finally get \(\operatorname{max}\{2y,0,-2y-1\}\).

If you want to go further, we can add and subtract \(\frac{1}{2}\) to/from our expression, apply addition property, apply our union property and absolute value definition, then apply addition property again to get \(\operatorname{max}\{\left|2y+\frac{1}{2}\right|-\frac{1}{2},0\}\).