# Epigraphs and convexity

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.

• I'm thinking of the "function": |x|ˆ(1/3) + |y|ˆ(1/3) – Sig Apr 20 '17 at 11:51
• (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$. – dohmatob Apr 20 '17 at 13:19
• $S$ is a sublevel set of the function. – Brian Borchers Apr 20 '17 at 18:26

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

• 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? – Sig Apr 20 '17 at 15:23
• 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. – dohmatob Apr 20 '17 at 18:38
• @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!! – Rajat Apr 21 '17 at 11:58
• @Sig Please check out the definition of epigraph: en.wikipedia.org/wiki/Epigraph_(mathematics) – Rajat Apr 21 '17 at 12:00

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


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

• 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? – Sig Apr 20 '17 at 15:20