# A differentiable approximation to the minimum function

Suppose we have a function $f : \Re^N \rightarrow \Re$ which, given a vector, returns the value of its smallest element. How can I approximate $f$ with a differentiable function(s)?

-
The tag of the question is probably wrong. Sorry for that. – eakbas Aug 11 '10 at 5:45

If signs aren't a big deal, use the generalized mean formula

$$\left(\frac{1}{n}\sum x_i^k\right)^{1/k}$$

for $k\to -\infty$.

-
Nice, but you probably want to get rid of 1/n so that the result is as close to the smallest x_i as possible? – Neil Aug 11 '10 at 7:42
@Neil: The $1/n$ normalization is the standard one since it gives exactly what you want when all the $x_i$ are equal. But in fact if $n$ is fixed and $k$ approaches negative infinity, it doesn't matter asymptotically what constant you put inside the parentheses. – Tracy Hall Aug 11 '10 at 8:28
Since the function is piecewise linear, probably the most efficient smooth approximation is just by convolution with standard mollifiers $\epsilon^-n \rho(x/\epsilon)$, this simply 'rounds the corners' and leaves the function unchanged at most points. But the OP should really clarify what he needs. – Piero D'Ancona Aug 11 '10 at 11:10

A smooth approximation is $f(x) = -\frac{1}{\rho}\log \sum_i e^{-\rho x_i}$. The larger $\rho>0$, the closer the approximation is to the minimum.

-

What about $f: [x_1 \dots\ x_n] \mapsto \frac{1}{\sum_i x_i^{-1}}$?

-
I see a small problem if any of the $x_i$ is nonpositive. – Pait Jun 27 '13 at 22:07
@pait: +1, you may want to add this comment to the accepted answer as well? – Neil Jun 28 '13 at 1:33
Well the accepted answer states that it's only applicable to absolute values, and 0 is not a problem in the formula with squares. It seems that to achieve smoothness it is more practical to work with exponentials. – Pait Jun 28 '13 at 12:11

For two dimensions, we have $\min(x,y) = \tfrac{1}{2}(x+y-|x-y|)$, so you just need a differentiable approximation to $x \mapsto |x|$. Then for higher dimensions we have $\min(x,y,z) = \min(x, \min(y,z))$, etc.

-