25
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Since convex functions are continuous, $f$ must be continuous. So you should maybe change the question to cover only continuous functions for starters. $\endgroup$ – J. J. Dec 7 '10 at 15:58
  • $\begingroup$ @J.J.: convex functions are continuous only on some domains. $\endgroup$ – Mariano Suárez-Álvarez Dec 7 '10 at 19:54
  • $\begingroup$ @Mariano: That's true, but I was supposing he was talking about functions $\mathbb{R} \to \mathbb{R}$. I think the domain can be any open convex subset of $\mathbb{R}$. $\endgroup$ – J. J. Dec 8 '10 at 3:59
21
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ what would this look like for sin(x) $\endgroup$ – mathcast Dec 7 '10 at 16:07
  • $\begingroup$ Follow David Speyer's construction to get $\sin(x)+x^2$ and $-x^2$ $\endgroup$ – Ross Millikan Dec 7 '10 at 16:37
  • 8
    $\begingroup$ "It shouldn't be too much harder to do a general continuous function, but I don't see it right now." -phew-, I hope you don't see it, since it is not true... $\endgroup$ – Willie Wong Dec 7 '10 at 16:57
  • 1
    $\begingroup$ Wow, you are absolutely right. Good catch. $\endgroup$ – David E Speyer Dec 7 '10 at 21:24
  • $\begingroup$ the "closed interval" is necessary? The statement won't hold in infinite intervals? $\endgroup$ – becko Apr 15 '16 at 16:08
25
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ See this: books.google.com/books?id=cqyHkkCxVtcC&pg=PA22 section 14. $\endgroup$ – Aryabhata Dec 7 '10 at 17:17
  • 2
    $\begingroup$ @Moron: thanks! I wasn't aware of this characterisation. Just to summarise Moron's link: on a closed interval, the class of function $f = g - h$ where $g,h$ are convex with bounded first derivatives is given also by the class of functions given by the integral of a function of bounded variation. $\endgroup$ – Willie Wong Dec 7 '10 at 18:07
  • 1
    $\begingroup$ Hum, in hindsight, this is not too surprising, it is almost the definition of BV... $\endgroup$ – Willie Wong Dec 7 '10 at 18:09
3
$\begingroup$

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 :-)

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

NO, let assume we talk about a function from $R$ to $R$.

Let $f:R \rightarrow R$ be a continuous function which is not lipschitz.

This function cannot be written as sum of convex and concave function.
Since convex(concave) functions are lipschitz so is there sum.

$\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.