Take the 2-minute tour ×

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)?

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

4 Answers 4

up vote 2 down vote accepted

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$.

share|improve this answer
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.

share|improve this answer

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

share|improve this answer
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.

share|improve this answer

Your Answer


