In Search of a Smooth Maximum Function

寻求一个光滑的最大值函数 苏剑林 · 2015-05-02 · Mathematics function extremum smoothness

Seeking a smooth maximum function

In optimization problems, the most direct way to find the maximum or minimum of a function is to take derivatives and compare the values at the extrema. However, the functions we want to optimize are often not differentiable — for instance, when the function involves the max function $\max(x,y)$. In such cases we need to look for other approaches. One clever idea is to approximate these non-differentiable functions with a differentiable function, so that we can find their approximate optimum using the usual methods for locating extrema. The task of this post is to explore a simple and useful function that can serve as an approximation to the max function and that possesses derivatives of all orders. Below is a derivation the author has worked out.

In mathematical analysis, we already learned a formula concerning the max function: when $x \geq 0, y \geq 0$, we have

$$\max(x,y)=\frac{1}{2}\left(|x+y|+|x-y|\right)\tag{1}$$

So, in order to find a max function, we can first try to find a function that approximates the absolute value $|x|$, which reduces the problem from two dimensions to one. So which function can we use? more

It's hard to spot the right function just by staring at it, so let's work our way toward it step by step. Differentiating $f(x)=|x|$, we find that except at the single point $x=0$, it can be differentiated everywhere without any trouble

$$f'(x) = \left\{\begin{aligned}1,&\,x > 0\\ -1,&\, x < 0\end{aligned}\right.\tag{2}$$

This is a simple piecewise function. In physics, this kind of function is extremely common, and the function closest to it should be the unit step function $\theta(x)$:

$$\theta(x) = \left\{\begin{aligned}1,&\,x > 0\\ 0,&\, x < 0\end{aligned}\right.\tag{3}$$

So

$$f'(x)=2\theta(x)-1\tag{4}$$

All that remains is to find an approximating function for $\theta(x)$, and physicists have already handed us a ready-made one — a fairly simple form is source: Wikipedia

$$\theta(x)=\lim_{k\to +\infty} \frac{1}{1+e^{-k x}}\tag{5}$$

So we can take $\frac{1}{1+e^{-k x}}$ as our approximating function. Substituting it into equation $(4)$ gives us $\frac{2e^{k x}}{1+e^{k x}}-1$, and integrating yields

$$\begin{aligned}f(x)&=\frac{2}{k}\ln(1+e^{kx})-x\\ &=\frac{1}{k}\left[\ln(1+e^{kx})+\ln(1+e^{-kx})\right]\\ &=\frac{1}{k}\ln(2+e^{kx}+e^{-kx})\end{aligned}\tag{6}$$

It's not hard to notice that in the logarithmic term of equation $(6)$, when $k$ is sufficiently large, the constant $2$ has negligible influence. Dropping it, we get a fairly simple absolute value function:

$$|x|=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{-kx})\tag{7}$$

Combining equations $(7)$ and $(1)$, we obtain

$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\left\{\ln[e^{k(x+y)}+e^{-k(x+y)}]+\ln[e^{k(x-y)}+e^{-k(x-y)}]\right\}\tag{8}$$

Equation $(8)$ can be simplified further, giving us

$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{-2kx}+e^{2ky}+e^{-2ky})\tag{9}$$

And since equation $(1)$ holds when $x\geq 0,y\geq 0$, the terms $e^{-2kx}$ and $e^{-2ky}$ in equation $(9)$ become unimportant too, so we drop them as well, arriving at

$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{2ky})\tag{10}$$

or equivalently

$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{ky})\tag{11}$$

Equation $(11)$ is precisely the ideal max function we were looking for. Although our derivation was based on $x\geq 0,y\geq 0$, it's not hard to see that the formula still holds even when negative numbers appear in $x,y$! It can even be generalized to a max function of multiple variables:

$$\max(x,y,z,\dots)=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{ky}+e^{kz}+\dots)\tag{12}$$

For more discussion of equation $(11)$, see Matrix67's post "How to Construct a Smooth Max Function":

http://www.matrix67.com/blog/archives/2830

Looking at the structure of equation $(11)$, we can see that what it actually does is this: find a function that is monotonically increasing over the entire real line and that grows faster than linearly, sum it over the variables, and then take the inverse function at the end. With that in mind, it's easy to construct similar functions: if we choose $y=x^{2k+1}$, we get

$$\max(x,y)=\lim_{k\to+\infty} \sqrt[2k+1]{x^{2k+1}+y^{2k+1}}\tag{13}$$

Of course, the precision (or rather, the rate of convergence) of $(13)$ is nowhere near as good as that of $(11)$. It isn't hard to improve the precision either, for example

$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{k}\ln\ln\left(e^{e^{kx}}+e^{e^{ky}}\right)\tag{14}$$

Weighing both precision and simplicity, $(11)$ is probably the best choice overall.