Mapping non-convex functions onto convex functions

Question

I am wondering if a non-convex optimization problem can be reduced to a convex one by mapping non-convex functions/sets onto convex functions/sets. In this context, I would like to know if the following claim is true:

For any non-convex function $f: \mathbb{R} \rightarrow \mathbb{R}$ there exists a convex function $g : \mathbb{R} \rightarrow \mathbb{R}$ such that $f\circ g$ is convex.

For example, $f = \log(x)$ is not convex but $g(x) = \exp(x)$ (which is convex) yields $(f\circ g) (x) = x$ also convex.

Another example is $f(x) = x^3$ and $g(x) = \begin{cases} -x, & \text{if $x < 0$} \\[2ex] x, & \text{otherwise} \end{cases}.$

EDIT: $g$ constant is a trivial solution, but I am not interested in this case.

Answer 1

Any constant function $g$ would do that, but that is useless for optimization problems.

If we add the condition that $g$ is not constant then the answer is no, even for functions defined on (finite or infinite) intervals. More precisely:

Let $I, J \subset \Bbb R$ be intervals, and $g: I \to J$ a non-constant convex function. Then there is a continuous function $f: J \to \Bbb R$ such that $f \circ g$ is not convex.

The idea is that a convex function assumes it maximum on any closed interval at one of the boundary points of the interval, and that this property is preserved under an (injective) change of variable.

Proof: W.l.o.g. assume that $g(x_0) < g(x_1)$ for some $x_0 < x_1$. The convexity of $g$ implies that $g$ is strictly increasing on any interval $[x_1, x_2] \subset I$. Then $g$ maps $[x_1, x_2]$ bijectively onto $[y_1, y_2] := [g(x_1), g(x_2)] \subset J$.

Now we can define $f: J \to \Bbb R$ as $$ f(y) = \sin\left( \pi \frac{y-y_1}{y_2-y_1}\right) \, . $$

If $f \circ g$ were convex then $$ \begin{aligned} \max \{ f(y) \mid y_1 \le y \le y_2 \} &= \max \{ (f\circ g)(x) \mid x_1 \le x \le x_2 \} \\ &= \max( (f\circ g)(x_1), (f\circ g)(x_2) ) \\ &= \max(f(y_1), f(y_2)) \\ & = 0 \end{aligned} $$

and that is not obviously not the case.

Answer 2

Suppose $f$ is bounded. Then $f\circ g$ is bounded and convex, so it is constant.

Answer 3

If $f(x)=x\sin x$ and $g:\Bbb R\to\Bbb R$ is convex and not constant, then $f\circ g$ is not convex. If $g$ is a convex function defined on $\Bbb R$, call $Q_g=\left\{x\in\Bbb \,:\, g(x)\ne \inf\limits_{y\in\Bbb R}g(y)\right\}=(-\infty, a)\cup (b,\infty)$ (for some $-\infty\le a\le b\le\infty)$. Let's say $b<\infty$. By convexity, $\left.g\right\rvert_{(b,\infty)}:(b,\infty)\to \left(\inf\limits_{t\in\Bbb R}g(t),\infty\right)=(u,\infty)$ is a homeomorphism. If $f\circ g$ were convex, then $h=f\circ \left.g\right\rvert_{(b,\infty)}$ would be too. In particular (being convex on an interval), it would satisfy this topological property:

For all $x$, $h(x)=\min\limits_{t\in\operatorname{dom}h} h(t)$ if and only if there is an open set $U\ni x$ such that $h(x)=\min\limits_{t\in U} h(t)$.

This property is invariant under composition on the right by a homeomorphism. This would imply that $h\circ\left. g\right\rvert_{(b,\infty)}^{-1}=\left.f\right\rvert_{(u,\infty)}$ has it. Which is not the case, because $x\sin x$ has infinitely many local minima in any neighbourhood of $\infty$ (each attaining different values).