2
May
寻求一个光滑的最大值函数
By 苏剑林 | 2015-05-02 | 131475位读者 |在最优化问题中，求一个函数的最大值或最小值，最直接的方法是求导，然后比较各阶极值的大小。然而，我们所要优化的函数往往不一定可导，比如函数中含有最大值函数$\max(x,y)$的。这时候就得求助于其他思路了。有一个很巧妙的思路是，将这些不可导函数用一个可导的函数来近似它，从而我们用求极值的方法来求出它近似的最优值。本文的任务，就是探究一个简单而有用的函数，它能够作为最大值函数的近似，并且具有多阶导数。下面是笔者给出的一个推导过程。
在数学分析中，笔者已经学习过一个关于最大值函数的公式，即当$x \geq 0, y \geq 0$时，我们有
$$\max(x,y)=\frac{1}{2}\left(|x+y|+|x-y|\right)\tag{1}$$
那么，为了寻求一个最大值的函数，我们首先可以考虑寻找一个能够近似表示绝对值$|x|$的函数，这样我们就把问题从二维降低到一维了。那么，哪个函数可以使用呢？
直接观察挺难发现哪个函数可以使用的，我们将问题逐步向简单推进。我们对$f(x)=|x|$求导，除了$x=0$这一点外，其他都可以顺利求导
$$f'(x) = \left\{\begin{aligned}1,&\,x > 0\\
-1,&\, x < 0\end{aligned}\right.\tag{2}$$
这是一个简单的分段函数，在物理中，这类函数十分常见，跟它最接近的，应该是单位阶跃函数$\theta(x)$：
$$\theta(x) = \left\{\begin{aligned}1,&\,x > 0\\
0,&\, x < 0\end{aligned}\right.\tag{3}$$
那么
$$f'(x)=2\theta(x)-1\tag{4}$$
下面只需要寻求$\theta(x)$的近似函数，物理学家已经提供现成的函数给我们了，一个比较简单的形式是[来源：维基百科]
$$\theta(x)=\lim_{k\to +\infty} \frac{1}{1+e^{-k x}}\tag{5}$$
那么我们就可以取$\frac{1}{1+e^{-k x}}$作为近似函数了，代入$(4)$式得到$\frac{2e^{k x}}{1+e^{k x}}-1$，积分得到
$$\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}$$
不难发现，$(6)$式中的对数部分，在$k$足够大的时候，常数$2$的影响微乎其微，把它去掉之后，我们有一个比较简单的绝对值函数：
$$|x|=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{-kx})\tag{7}$$
结合$(7)$式和$(1)$式，我们就得到
$$\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}$$
$(8)$式还可以再化简，我们得到
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{-2kx}+e^{2ky}+e^{-2ky})\tag{9}$$
并且由于$(1)$式是在$x\geq 0,y\geq 0$时成立的，所以$(9)$式中的$e^{-2kx}$和$e^{-2ky}$均变得不重要了，我们也把它们去掉，进一步得到
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{2ky})\tag{10}$$
或者写成
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{ky})\tag{11}$$
$(11)$式正是我们希望得到的理想的最大值函数。虽然我们的推导基于$x\geq 0,y\geq 0$，但是不难发现，对于$x,y$中出现负数时，上述公式仍然成立！它甚至还可以推广到多个变量的最大值函数：
$$\max(x,y,z,\dots)=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{ky}+e^{kz}+\dots)\tag{12}$$
关于$(11)$式更多的展示，请阅读Matrix67的《如何构造一个平滑的最大值函数》：
http://www.matrix67.com/blog/archives/2830
观察$(11)$式的结构可以看出，这实际上是做了这样的一个事情：找一个在整个实数域上都单调递增的函数，而且增长速度要快于线性增长，然后求和，最后取逆函数。因此，不难构造出类似的函数：我们选$y=x^{2k+1}$，那么得到
$$\max(x,y)=\lim_{k\to+\infty} \sqrt[2k+1]{x^{2k+1}+y^{2k+1}}\tag{13}$$
当然，$(13)$的精度（或者说收敛速度）远没有$(11)$那么好，要提高精度也不难，比如
$$\max(x,y)=\lim_{k\to +\infty} \frac{1}{k}\ln\ln\left(e^{e^{kx}}+e^{e^{ky}}\right)\tag{14}$$
综合精度和简洁两方面考虑，估计最优的选择就是$(11)$了。
转载到请包括本文地址：https://kexue.fm/archives/3290
更详细的转载事宜请参考：《科学空间FAQ》
如果您还有什么疑惑或建议，欢迎在下方评论区继续讨论。
如果您觉得本文还不错，欢迎分享/打赏本文。打赏并非要从中获得收益，而是希望知道科学空间获得了多少读者的真心关注。当然，如果你无视它，也不会影响你的阅读。再次表示欢迎和感谢！
如果您需要引用本文，请参考：
苏剑林. (May. 02, 2015). 《寻求一个光滑的最大值函数 》[Blog post]. Retrieved from https://kexue.fm/archives/3290
@online{kexuefm-3290,
title={寻求一个光滑的最大值函数},
author={苏剑林},
year={2015},
month={May},
url={\url{https://kexue.fm/archives/3290}},
}
September 25th, 2020
x,y都小于0等式就不成立了
依然成立
如果x+y小于0的话，可以把（1）式中的|x+y|换成-|x+y|,最后到第（8）式时会出现两个ln相减，化简后的分母是e^(2kx+2ky)+1,趋近于1，即可得到最后的结果
补充下，当x和y没有限制时，max(x,y)=1/2(x+y+|x-y|)
最近刷到一篇对激活函数光滑近似的文章就用到这个思路：
SMU: smooth activation function for deep networks using smoothing maximum technique
https://arxiv.org/abs/2111.04682
嗯嗯，这种挺没意思的，前不久我才介绍了一篇：https://kexue.fm/archives/8718
嗯，是的，其实楼主直接用\[\max(x, y) = \frac{1}{2} \left( |x - y| + x + y \right) \tag{1}\]证明会更好
嗯嗯，其实这篇文章有些年代的局限性，当时我刚好学到了文章中的公式，就直接从文章中的公式出发了，现在看来自然有很多地方可以简化一下。
但是不难发现，对于x,y中出现负数时，上述公式仍然成立！
当X,Y 只有一个负数的时候很容易证明成立。 当X,Y 都小于零的时候
\max(x,y)=\frac{1}{2}\left(|x-y|+x+y\right)\tag{1}
用然后带入|x|=\lim_{k\to +\infty} \frac{1}{k}\ln(e^{kx}+e^{-kx})\tag{7}就可以得到：
\max(x,y)=\lim_{k\to +\infty} \frac{1}{2k}\ln(e^{2kx}+e^{2ky})\tag{10}这个结论了。
自己推导了一下。作者的一个很容易证明，有时候我要理解很久。
但是不难发现，对于 \(x, y\) 中出现负数时，上述公式仍然成立！当 \(x < 0, y < 0\) 时，有：
\[\max(x, y) = \frac{1}{2} \left( |x - y| + x + y \right) \tag{1}\]
然后带入 \(|x| = \lim_{{k \to +\infty}} \frac{1}{k} \ln(e^{kx} + e^{-kx}) \tag{7}\) 就可以得到：
\[\max(x, y) = \lim_{{k \to +\infty}} \frac{1}{2k} \ln(e^{2kx} + e^{2ky}) \tag{10}\]
这个结论由作者证明，尽管有时我需要花些时间理解。这些公式可以通过 LaTeX 语法嵌入到你的文档中，用于显示数学公式和推导过程。
February 7th, 2021
您好，请问“(13)的精度（或者说收敛速度）远没有(11)那么好”中的精度和收敛速度具体是什么意思？我不太理解。
对于同一个$k$，几乎都有
$$\left|\max(x,y)-\frac{1}{k}\ln(e^{kx}+e^{ky})\right| < \left|\max(x,y)-\sqrt[2k+1]{x^{2k+1}+y^{2k+1}}\right|$$
请问这个怎么证明呢
这还真把我问倒了。其实这个不等式并非恒成立的，只是一个趋势，我们可以用一阶近似观察一下。首先留意到$\frac{1}{k}\ln(e^{kx} + e^{ky})$和$\sqrt[2k+1]{x^{2k+1} + y^{2k+1}}$其实都是大于$\max(x,y)$的，所以我们只需要证明
$$\frac{1}{k}\ln(e^{kx} + e^{ky}) < \sqrt[2k+1]{x^{2k+1} + y^{2k+1}}$$
假设$x > y$，我们有
$$\frac{1}{k}\ln(e^{kx} + e^{ky}) = x + \frac{1}{k}\ln(1 + e^{k(y-x)})\approx x + \frac{e^{k(y-x)}}{k}$$
以及
$$\sqrt[2k+1]{x^{2k+1} + y^{2k+1}} = x\left[\sqrt[2k+1]{1 + (y/x)^{2k+1}}\right]\approx x\left[1 + \frac{1}{2k+1}(y/x)^{2k+1}\right] = x + \frac{1}{2k+1}(y/x)^{2k}y$$
两个形式有相似之处，如果$e^{y-x}\ll y/x$，那么所证不等式成立。而对于$x,y > 1$来说，$e^{y-x}\ll y/x$是比较容易成立的。
暂时没有时间将它转化为精准的不等式证明，抱歉。
May 22nd, 2021
您好，公式（5）分母中e的指数不是应该是是-2kx吗？
有什么区别呢？反正都是要$k\to\infty$。
August 4th, 2023
请问(8)到(9)的化简是如何推的？
$\ln a + \ln b = \ln (ab)$，然后展开$ab$。
October 24th, 2023
留一个有意思的发现，选择tanh作为逼近f(x)=|x|导数时可以发现得到的就是式7
嗯嗯。但写这篇文章的时候，其实我还不大熟悉tanh～
June 16th, 2024
苏神，为什么“找一个在整个实数域上都单调递增的函数，而且增长速度要快于线性增长，然后求和，最后取逆函数”，其极限还是max(x)啊？要怎么证明$\lim_{\tau \rightarrow 0^{+}} \tau F^{-1} (\sum_{j=1}^n e^{F(x_j)/\tau}) =\max(\mathbf x)$啊？
我要表达的意思是
$$f^{-1}(\sum_i f(x_i))\approx \max_i x_i$$
这是因为当$f(x)$的增长速度远快于线性时，$\sum_i f(x_i)\approx f(\max_i x_i)$，即以最大那一项为主，所以
$$f^{-1}(\sum_i f(x_i))\approx f^{-1}(f(\max_i x_i)) = \max_i x_i$$
June 20th, 2024
请问一下，从公式(11)到公式(12),这步扩展怎么理解or证明呢？
可以用两面夹直接证明。。。[手动狗头]
假设$x_1 > x_2 > \cdots > x_n$，那么
$$\frac{1}{k}\ln\sum_i e^{k x_i} = \frac{1}{k}\ln e^{k x_1}\sum_i e^{k (x_i-x_1)} = x_1 +\frac{1}{k}\sum_i e^{k (x_i-x_1)}$$
其中
$$\sum_i e^{k (x_i-x_1)} = 1 + e^{k(x_2-x_1)} + e^{k(x_3-x_1)} + \cdots $$
后面的指数都是负数，当$k\to\infty$时它们$\to 0$，所以$\sum_i e^{k (x_i-x_1)}\to 1$，取对数后是0，所以最后等于最大值$x_1$。
厉害!!!