Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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
2  
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

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.