can any continuous function be represented as a sum of convex and concave function? I read that any continuous function can be represented as a sum of convex and concave function, meaning for all $f(x)$, $f(x) = g(x) + h(x)$ where $g$ is convex and $h$ is concave.
There could be infinitely many decompositions of that sort.
Anyone knows where I can see a proof or this, or knows of a proof of this?
Thanks.
 A: A $C^1$ function $f$ on a compact interval is convex (or is it concave?)
if and only if $f'$ is increasing and is concave (or is it convex?)
if and only if $f'$ is decreasing. If a function on a compact interval
is a sum of a convex and a concave function, each of which is $C^1$, then
$f'$ is the sum of an increasing and a decreasing function and so
has bounded variation. There are continuous functions which are not
of bounded variation on a compact interval. Integrating one gives a
$C^1$ function $f$ which is not the sum of a $C^1$ convex and
a $C^1$ concave function. Perhaps it could be the sum of some
more general convex and concave functions, but I wouldn't bet on it :-)
A: You need more conditions than even absolute continuity. A characterisation of continuous, convex functions defined on open intervals is that they must be the indefinite integral of a monotonically non-decreasing function. (See here for example.) In particular, this means that continuous, convex functions are absolutely continuous.
So if you take any function that is continuous and not absolutely continuous (Cantor's stair case comes to mind), it cannot be decomposed as a sum of a convex and a concave function.
What's more important is that a convex function, by Alexandrov's theorem, must have a second derivative almost everywhere. Therefore your initial function must be even better than just absolutely continuous, it needs to also admit almost everywhere second derivatives.
And even assuming almost everywhere second derivatives is not enough, if you take the function $x \sin(1/x)$  which is analytic away from the origin, you cannot represent it as the difference of two convex functions.
Of course, there is still a gap between twice almost everywhere differentiable and David Speyer's everywhere twice-continuously differentiable condition. I am not entirely sure where the correct boundary lies, or if there is a correct boundary using just classical differentiability notions.
A: If $f$ is $C^2$ (meaning the derivatives $f'$ and $f''$ are defined and continuous), and if $f$ is defined on a closed interval like $[0,1]$, then there is an easy solution. Since $f''$ is continuous, it has a minimal value $m$. Choose $c$ positive and greater than $m$. Then $f(x)+c x^2/2$ is convex, by the double derivative test, and $-c x^2$ is concave. Of course, $[f(x)+c x^2/2] + [-cx^2/2] = f(x)$. 
It shouldn't be too much harder to do a general continuous function, but I don't see it right now.
A: Counterexample:
Take
$f(x)=x^2sin(\frac{1}{x^2})$      (with f(0)=0)
this is a continuous function, whose gradient is unbounded as x goes to 0.
g'(x) and h'(x) are monotonic, and hence bounded on [-1,1], so the gradient of g(x)+h(x) is bounded as x goes to 0.
Edit: Looking at it again, this doesn't look fantastically rigorous, but I think it holds up.
A: It is known that every continuously differentiable function with a Lipschitz derivative (in particular every twice differentiable function) is the difference of a convex function and a convex quadratic function on a compact convex set (see "Characterizing zero-derivative points", J.Global Optimization, v.46 (2010) 155-161). For twice continuously differentiable functions of the single variable this decomposition is easy to prove using a characterization of convex function and the Weierstrass existence theorem. 
A: Assume $f$ to be differentiable. We need to write $f'$ as the sum of nondecreasing and a nonincreasing functions $g$ and $h$. This is possible if and only if $f'$ has bounded variation: for every $a<b$, there exists $M$ such that for any integer $n$ and any $a=x_1 \lt \ldots \lt x_{n+1} = b$, $\sum_{i=1}^n |f(x_{i+1})-f(x_i)| \leq M$.
In this case we define, for $x \geq 0$, $g(x)=\mathrm{sup}_{0=x_1 \lt \ldots \lt x_{n+1}=x} \sum_{i=1}^n \left(f(x_{i+1})-f(x_i) \right)^+$ where $y^+ = y$ if $y \geq 0$ and $0$ otherwise. Define $g$ similarly on $]-\infty,0]$, and $h=f-g$. It is easy to check that $g$ is nondecreasing, $h$ is nonincreasing, and their primitives give the result.
A: No, let's assume that we talk about a function from $R$ to $R$.
Let $f:R \rightarrow R$ be a continuous function that is not locally Lipschitz.
This function cannot be written as the sum of convex and concave functions.
Since convex(concave) functions are locally Lipschitz, so is their sum.
