6
$\begingroup$

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?

$\endgroup$

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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