4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I presume $g$ surjective? $\endgroup$ – Saucy O'Path Jul 6 '18 at 8:37
  • $\begingroup$ just a side comment with a clarification. $\log(x)$ is a concave function. So, negated concave should yield convex, agree? $\endgroup$ – user550103 Jul 6 '18 at 8:37
  • 3
    $\begingroup$ Any constant function $g$ would do that, but you are probably looking for strictly monotonic (injective) functions. $\endgroup$ – Martin R Jul 6 '18 at 8:38
  • $\begingroup$ @MartinR Thanks for your reply, but I am not interested in the trivial solution $g$ constant. $\endgroup$ – Alex Silva Jul 6 '18 at 8:42
  • 1
    $\begingroup$ The reason why it can't be true in a meaningful way is the reason why convex optimization is nice: local minima of a convex function are global minima, i.e. if there is some $x$ and some neigbourhood $U$ of $x$ such that $f(y)\ge f(x)$ for all $y\in U$, then $f(y)\ge f(x)$ for all $y$. If $f$ takes distinct values in many distinct local minima, then $f\circ g$ must "forget" that topological obstruction. A convex function covers intervals as a homeomorphism, as a $\cup$-thing or as a $\setminus\underline\quad/$-thing. So $f\circ g$ can't forget about those local minima (unless $g$ avoids them). $\endgroup$ – Saucy O'Path Jul 6 '18 at 9:22
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

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