Smooth approximation of $\max(f_1(x),f_2(x),\cdots,f_n(x))$

Question

In the GAMS documentation concerning non-smooth optimization I found the following statement:

A smooth approximation for $\max(f(x),g(y))$ is as in the following example code:

[f(x) + g(y) + sqrt(sqr(f(x)-g(y)) + sqr(delta))] /2 where delta a small number.

Does something similar exist for $\max(f_1(x),f_2(x),\cdots,f_n(x))$?

Answer 1

Indeed, there exists numerous smooth approximations for the max function. One of the most well known approximation is the Kreisselmeier-Steinhauser (KS) functional, that approximates the non-smooth functional $$ \max(f_1(x), \cdots, f_n(x)) $$ with the smooth functional $$ KS(f_1, \cdots, f_n; \rho) = \frac{1}{\rho} \log{\sum_{i=1}^n w_i e^{\rho f_i} } = \max_i f_i \; + \; \frac{1}{\rho} \log{\sum_{i=1}^n w_i e^{\rho (f_i - \max_i(f_i))} } $$ with $\rho>0$ and $w_1, \cdots, w_n$ given (positive) weights.

This functional satisfies:

• $KS(f_1, \cdots, f_n; \rho) > \max_i(f_i)$ for all $\rho >0$
• $\lim_{\rho \to +\infty} KS(f_1, \cdots, f_n; \rho) \to \max_i(f_i)$
• $\max_i(f_i) < KS(f_1, \cdots, f_n; \rho) \leq \max_i(f_i) + \frac{\log(n)}{\rho} $

You could find more details about the KS functional in

Polyak, R. A. "Smooth optimization methods for minimax problems." SIAM Journal on Control and Optimization 26.6 (1988): 1274-1286.