1
$\begingroup$

I have a problem which is as follows:

Let the set $S$:

$$S = \left\{(x, y) \in \mathbb{R}^2 : |x|^{\frac 13} + |y|^{\frac 13} \leq 1\right\}$$

Find out if the set is convex or not, and sketch the set.

And then I found out that $S$ is not convex, and was able to sketch the set (by thinking that $S$ would have to be on or below the function).

But what I don't fully understand is the relation between the epigraph of the function and the set $S$. Is $S$ the epigraph of the function? If so, then $S$ is per definition the points that lie on or above the function but below $f(x,y)=1$? How is it then that $S$ is shaped like a four pointed star, if the epigraph is the points that lie above the function?

My second question is: if $S$ is the epigraph of the function, is it sufficient to show that since the function is not convex, that $S$ is not convex? Or can an epigraph be convex if its function is not convex?

I'm finding this somewhat confusing, so hope someone can clarify this for me.

$\endgroup$
  • $\begingroup$ I'm thinking of the "function": |x|ˆ(1/3) + |y|ˆ(1/3) $\endgroup$ – Sig Apr 20 '17 at 11:51
  • $\begingroup$ (1) $S$ is not an epigraph en.wikipedia.org/wiki/Epigraph_(mathematics). (2) No, showing that your function $f$ is not convex doesn't show that a region defined by "$f(x, y) \le C$" is not convex. (3) $S$ is not convex. You can prove it by producing two points in S such that the coord joining them does lie completely in $S$. $\endgroup$ – dohmatob Apr 20 '17 at 13:19
  • $\begingroup$ $S$ is a sublevel set of the function. $\endgroup$ – Brian Borchers Apr 20 '17 at 18:26
1
$\begingroup$

A simple answer to your question is that: $$ S = \{\textbf{x} \in \mathbb{R}^2: \lvert x_1 \rvert^{1/3} + \lvert x_2 \rvert^{1/3} \leq 1\} = \{\textbf{x} \in \mathbb{R}^2: ( \lvert x_1 \rvert^{1/3} + \lvert x_2 \rvert^{1/3} )^3 \leq 1\} = \{\textbf{x} \in \mathbb{R}^2: \lVert \textbf{x}\rVert_{1/3} \leq 1\}.$$ This is basically the unit $q$-norm ball where $q=1/3$, so this is not a convex set.

[Note: A function is convex, if and only if, the epigraph of the function is convex.]

$\endgroup$
  • $\begingroup$ But is S, the way the problem specifies S, the epigraph of |x|ˆ(1/3) + |y|ˆ(1/3)? And if so, would it be sufficient to say that since |x|ˆ(1/3) + |y|ˆ(1/3) is not convex that neither is S? Or can the epigraph of a function be convex if the function itself is not convex? $\endgroup$ – Sig Apr 20 '17 at 15:23
  • $\begingroup$ Hum, this can be more with rather basic ideas. You are invoking (without proof) the non-convexity of unit balls of $\ell_p$ norms when $0 \le p < 1$. Though this is perfectly correct, it's an overkill. $\endgroup$ – dohmatob Apr 20 '17 at 18:38
  • $\begingroup$ @dohmatob you are perfectly correct. I am assuming that we know the fact about the norm. Else the way, you solved the way that is the correct way to do. Cheers!! $\endgroup$ – Rajat Apr 21 '17 at 11:58
  • $\begingroup$ @Sig Please check out the definition of epigraph: en.wikipedia.org/wiki/Epigraph_(mathematics) $\endgroup$ – Rajat Apr 21 '17 at 12:00
1
$\begingroup$

It is good to first get an empirical feeling of the problem. In Python, you'd do

x, y  = xy = randn(2, 100000)
data = xy[:, abs(x) ** (1./3) + abs(y) ** (1./3) <= 1]
subplots(figsize=(6, 6))
scatter(*data, s=1)
xlabel("$x$")
ylabel("$y$")
title("$|x|^{1/3} + |y|^{1/3} \\le 1$")
tight_layout()
grid("on")

enter image description here

Now it should be pretty clear why this function can't be convex. Indeed, the point $a = (0, 1)$ and $a = (1, 2)$ are both in $S$ but the coord $[a, b]$ is not a subset of $S$. For example $\frac{a+b}{2} \not \in S$ since $2(1/2)^{1/3} > 1$.

General case

In general $2(1/2)^p > 1$ for all $p \in (0, 1)$, from which you see that If $p \in (1, \infty]$,

then the $\ell_p$ unit ball is convex iff $p \ge 1$ (the if part is provided by Holder's inequality).

$\endgroup$
  • $\begingroup$ Yeah I understand that, but would it be sufficient to show that since |x|ˆ(1/3) + |y|ˆ(1/3) is not convex, that S can not be convex? Or is the only way to show that S is not convex by using Jensens inequalities? $\endgroup$ – Sig Apr 20 '17 at 15:20

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.