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.
Best Answer
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:
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.