when is the epigraph a convex cone?

Question

The problem is from Stephen Boyd's textbook, which I couldn't solve. The question is "when is the epigraph of a function a convex cone?" The solution says that it is when the function is convex and positively homogeneous (f(ax) = af(x) for a>=0). Can anybody explain how the solution can be derived?

Answer 1

I'll assume you're familiar with the fact that a function is convex if and only if its epigraph is convex.

If the function is positive homogenous, then by just checking definitions, we see that its epigraph is a cone. That is, for all $a > 0$, we have:

$$ \begin{aligned}(\mathbf{x},t) \in \text{epi f} &\Leftrightarrow f(\mathbf{x})\le t \\& \Leftrightarrow af(\mathbf{x})=f(a\mathbf{x}) \le at \\ &\Leftrightarrow (a\mathbf{x},at) \in \text{epi f}\end{aligned}$$

On the other hand suppose the epigraph is a cone. This means for all $a>0$, if $(\mathbf{x},t) \in \text{epi} f$ then $(a\mathbf{x},at) \in \text{epi f}$. Clearly $(\mathbf{x},f(\mathbf{x})) \in \text{epi f}$, so $(a\mathbf{x},af(\mathbf{x})) \in \text{epi f}$, which means that $$ f(a\mathbf{x}) \le a f(\mathbf{x}).$$ Likewise $(a\mathbf{x},f(a\mathbf{x})) \in \text{epi f}$. So, again, if the epigraph is a cone, $(\mathbf{x},f(a\mathbf{x})/a) \in \text{epi f}$, or: $$ f(\mathbf{x}) \le f(a\mathbf{x})/a.$$ Combining the two inequalities, we get: $$ f(\mathbf{x}) \le f(a\mathbf{x})/a \le f(\mathbf{x})$$ Which means $f(a\mathbf{x}) = a f(\mathbf{x})$, ie, the function is positive homogenous.

Answer 2

An alternative approach: $$\text{epi f} = \{(\mathbf{x},t):f(\mathbf{x})\le t\}$$ Consider any two points that belong to the epigrafh, $e_1=(\mathbf{x_1},t_1)$ and $e_2=(\mathbf{x_2},t_2) $. Then for any $\theta_1, \theta_2 \ge 0$ it holds that $$f(\mathbf{x_1})\le t_1 \Rightarrow \theta_1f(\mathbf{x_1})\le \theta_1t_1 \;,\qquad f(\mathbf{x_2})\le t_2 \Rightarrow \theta_2f(\mathbf{x_2})\le \theta_2t_2\qquad \Rightarrow \theta_1f(\mathbf{x_1})+\theta_2f(\mathbf{x_2})\le \theta_1t_1+\theta_2t_2\qquad [1]$$ For the epigraph to be a convex cone we must have $$(\theta_1e_1 + \theta_2e_2) \in \text{epi f} \Rightarrow (\theta_1\mathbf{x_1}+\theta_2\mathbf{x_2}, \theta_1t_2+\theta_2t_2) \in \text{epi f}$$ $$\Rightarrow f(\theta_1\mathbf{x_1}+\theta_2\mathbf{x_2})\le \theta_1t_2+\theta_2t_2\qquad [2] $$

By convexity of $f()$ we have, for $\lambda \in [0,1]$, $$f(\lambda \mathbf{x_1} + (1-\lambda)\mathbf{x_2}) \le \lambda f(\mathbf{x_1})+ (1-\lambda)f(\mathbf{x_2})\qquad [3]$$ Now select some $\tau \ge 0$ , multiply the argument of the LHS and use the homogenetiy property to obtain $$f(\tau\lambda \mathbf{x_1} + \tau(1-\lambda)\mathbf{x_2}) \le \lambda f(\mathbf{\tau x_1})+ (1-\lambda)f(\mathbf{\tau x_2}) = \tau \lambda f(\mathbf{x_1})+ \tau(1-\lambda)f(\mathbf{x_2}) \;[4]$$ Since $\tau$ and $\lambda$ are arbitrary, they can give any non-negative number. So define $\theta_1 \equiv \tau\lambda$ and insert into the outer most LHS and RHS of $[4]$ to obtain:

$$f(\theta_1 \mathbf{x_1} + (\tau-\theta_1)\mathbf{x_2}) \le \theta_1 f(\mathbf{x_1})+ (\tau-\theta_1)f(\mathbf{x_2}) \;[5]$$

Next we set $\theta_2 = \tau-\theta_1$. Perhaps this looks restrictive? We must be able to prove the result for arbitrary pairs $(\theta_1, \theta_2)$. But we can chose arbitrary pairs $(\theta_1, \theta_2)$: chose them first and then $\tau$ is determined which in turn determines $\lambda$. What we are saying is that $\forall (\theta_1, \theta_2)$ there exist $\{\tau \ge0,\; \lambda \in[0,1]\}$ such that eq. $[3], [4]$ are satisfied (in fact, $\tau = \theta_1+\theta_2$ and $\lambda = \theta_1/(\theta_1+\theta_2)$). So we can write $[5]$ as

$$f(\theta_1 \mathbf{x_1} + \theta_2\mathbf{x_2}) \le \theta_1 f(\mathbf{x_1})+ \theta_2f(\mathbf{x_2}) \;[6]$$ Equation $[6]$ weakly separates the LHS of $[2]$ from its RHS, through eq. $[1]$, and the required result is proven.

(P.S.: the way homogeneity property is stated, implies that $f(\mathbf 0) = 0)$).