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

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

• Depending on how you want to use the $\max$, you might be able to linearize exactly. Feb 21 at 0:49
• $\max\left(x_0,x_1,\ldots,x_n\right) = \max\left(x_0,\max\left(x_1,\max\left(\ldots,x_n\right)\right)\right) .$
– Nat
Feb 21 at 5:29
• @RobPratt Hi Rob, I would like to avoid ending up with an MILP because of the difficulties associated with MILPs. The question is if I can win anything out of staying in the NLP domain. Probably not, because I will have to deal with a global optimization problem, but I would like to give it a try. Feb 21 at 9:49
• @Nat That is going to be a nightmare when it comes to implemention. Feb 21 at 9:54
• @Clement You do not necessarily require integer variables for linearization. Where does the $\max$ appear in your problem? Feb 21 at 14:11

## 1 Answer

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.