3
$\begingroup$

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

$\endgroup$
6
  • 1
    $\begingroup$ Depending on how you want to use the $\max$, you might be able to linearize exactly. $\endgroup$
    – RobPratt
    Feb 21 at 0:49
  • 1
    $\begingroup$ $\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) .$ $\endgroup$
    – Nat
    Feb 21 at 5:29
  • $\begingroup$ @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. $\endgroup$
    – Clement
    Feb 21 at 9:49
  • $\begingroup$ @Nat That is going to be a nightmare when it comes to implemention. $\endgroup$
    – Clement
    Feb 21 at 9:54
  • $\begingroup$ @Clement You do not necessarily require integer variables for linearization. Where does the $\max$ appear in your problem? $\endgroup$
    – RobPratt
    Feb 21 at 14:11
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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