# What non-convex functions be written as the $\min$ of multiple convex functions?

I am working on an optimization framework that can be used to optimize objective functions that can be written as the $\min$ of several convex functions. I was thinking about the generality of this framework and wonder if all functions can be written in this form? If not, what is the largest family of functions (e.g. continuous, differentiable, bounded from below, etc.) that can?

So, in summary ...

What is the largest family of functions that can be written as the $\min$ of one or more (preferably finite) convex functions?

• Every function $f$ can be written as $\min_x \{ i_{\{x\}} + f(x)\}$, where $i_{\{x\}}$ is the indicator function of $x$, which is convex.
– gerw
Feb 2, 2016 at 21:22
• Assuming gerw means the characteristic function, $i_{\{x'\}}(x)$ is convex and $f(x')$ is constant.
– user856
Feb 3, 2016 at 16:10
• @Rahul: I use characteristic function and indicator function the other way round as wikipedia. And I feel that 'indicator function' is much more used in the branch of convex analysis.
– gerw
Feb 3, 2016 at 18:32
• @Sobi: The function $i_{\{x\}}$ is convex (its $0$ on $x$, and $+\infty$ elsewhere). Hence, the function $x' \mapsto i_{\{x\}}(x') + f(x)$ equals $f(x)$ on $x$ and elsewhere it is $+\infty$. Hence, $f(x') = \min_x \{i_{\{x\}}(x') + f(x)\}$.
– gerw
Feb 3, 2016 at 18:34
• Only if your function is piecewise convex with a finite number of pieces.
– user856
Feb 3, 2016 at 20:01