When is the difference of two convex functions convex?

13.9k Views Asked by At

Assume that $X$ is a finite-dimensional Banach space. I know that, in general, if two functions $f, g : X \to \mathbb{R}$ are convex, then the function $(f-g) : X \to \mathbb{R}$ given by $x \mapsto f(x) - g(x)$ is not necessarily convex. Are there conditions we can impose on $f$ and $g$ so that the difference is still convex, e.g., if $f (x) \geq g (x)$ for every $x$ then can we say it's convex?

Are there any results about the convexity of the difference of convex functions?

2

There are 2 best solutions below

0
On

$f\ge g$ is not sufficient: for example, take $f(x)=\sqrt{x^2+1}$ and $g(x)=|x|$ (with $X=\mathbb R$); for another, take $f(x)=|x|$ and $g(x)=\max\ \{0,|x|-1\}$.

0
On

For any real-valued function $h$, $\alpha\in[0,1]$ and $x,y$ in the (convex) domain, let $$ D(h,\alpha,x,y)=\alpha h(x)+(1-\alpha)h(y)-h[\alpha x+(1-\alpha)y]. $$ Convexity for $h$ means $D(h,\alpha,x,y)\geq 0$ for all $\alpha,x,y$.

For your situation, one sufficient condition for $f-g$ to be convex is that $$ D(f,\alpha,x,y)\geq D(g,\alpha,x,y)\tag{i} $$ for all $\alpha,x,y$. (I think of this as $f$ being "more convex" then $g$.) Note that (i) doesn't impose convexity directly on $f$ and $g$. For example, $f(x)=-x^2$ and $g(x)=-2x^2$ satisfy (i) so that $f-g$ is convex but $f$ and $g$ are individually concave.

When the domain is $\mathbb{R}$ and $f$ and $g$ are both twice differentiable, it is also sufficient to have $$ f''\geq g''\tag{ii}. $$