I have a question regarding convex functions and compositions that I'm hoping someone could provide some insight on.
For a given non-convex function g(x), I'm wondering if it's possible to find another function h such that the composition h(g(x)) results in a convex function. In other words, does there exist a function h that can 'convexify' a non-convex function g when composed together?
I've been studying convex analysis and optimization, but I'm still a bit uncertain about the conditions and techniques for constructing such a function h, if it exists. Any guidance, references, or insights from the knowledgeable members here would be greatly appreciated.
Thank you in advance for your time and help!
The answer is, technically, yes. As I hinted at in my comment, making $h$ constant satisfies the conditions. Given any $g$, and any constant function $h$ (which is convex), $h \circ g$ is constant and hence convex.
However, in the realm of convex-optimization, this is likely unhelpful. The unstated spirit of this question is one of convexification of optimisation problems. Can we take a non-convex objective function, compose it with a convex function, and get a nice convex problem, the solution of which tells us something about the solution of the original problem?
Zim's comment is a reasonable attempt to solidify this problem: what if we insisted that the minimisers of $h \circ g$ are precisely the minimisers of $g$? This, unfortunately, doesn't work either: the minimisers of a convex function is a convex set, so if $g$ has a non-convex set of minimisers, then $h \circ g$ must have a different set of minimisers.
Perhaps, instead of insisting that $\operatorname*{argmin} g = \operatorname*{argmin} (h \circ g)$, we insist that $\operatorname{\overline{conv}} \operatorname*{argmin} g = \operatorname*{argmin} (h \circ g)$? Again, this is not going to work. Consider, for example, $$g(x) = x^2(x - 1)^2,$$ a quartic polynomial with precisely two minima at $x = 0$ and $x = 1$. At $x = 1/2$, there is a local maximum of $1/16$. Note that the equation $g(x) = 1/32$ has exactly four solutions $x_1, x_2, x_3, x_4$ such that $$x_1 < 0 < x_2 < \frac{1}{2} < x_3 < 1 < x_4.$$ Note that, for any $h$, $h \circ g$ is constantly $h(1/32)$ on those four points. Since $h \circ g$ is convex, we would have to have $h \circ g$ be constant on $[x_1, x_4]$, which strictly contains $\operatorname{\overline{conv}} \operatorname*{argmin} g = [0, 1]$. The fact that this interval is non-trivial and horizontal implies $h$ achieves its minimum all along this interval, as must $h \circ g$, hence $$\operatorname*{argmin} (h \circ g) \supseteq [x_1, x_4] \supsetneq [0, 1] = \operatorname{\overline{conv}} \operatorname*{argmin} g.$$
If we're happy with strict containment as above, then we might as well set $h$ to be constant once again.
All of this is to say, convexification via composition appears to be a bit of a dead end. You're better off convexifying by the second Fenchel dual instead, which is guaranteed to produce a lower-semicontinuous, convex function, whose infimum agrees with the infimum of whatever function you feed into it.