0
$\begingroup$

Theorem: An $n$-dimensional closed convex set $C$ in $\mathbb{R}^n$ is the intersection of the closed half-spaces tangent to it.

In the beginning of the proof, it is established that the epigraph $G$ of the support function of $C$ is the closure of the convex hull of the set $S$ of all exposed rays of $G$, i.e., $G = \operatorname{cl}(\operatorname{conv}(S))$. But then Rockafellar says that "...it follows that...$C$ is the intersection of all the half-spaces $\left\{x | \langle x, x^* \rangle \le \alpha \right\}$, such that the set of non-negative multiples of $(x^*,\alpha)$ is a non-vertical exposed ray of $G$." How do we see that? Why are the vertical exposed rays (if any) not considered?

$\endgroup$
1
$\begingroup$

If it's ok, I'll postpone the discussion of vertical exposed rays until the end. First, about the non-vertical ones. Rockafellar states

'...the linear functions $\langle x, \cdot \rangle$ majored by $\delta^*(\cdot|C)$, which correspond of course to points in $C$, are the same as the linear functions whose epigraphs contain every non-vertical exposed ray of G.'

Let $NV\subseteq S$ be the 'non-vertical' exposed rays of $G$. For each ray $r$ in $NV$ is a non-vertical ray, we may write it as $r := r(x^*, \alpha):= \{\lambda (x^*, \alpha): \lambda\geq 0\}$ for some non-zero $x^*\in \mathbb{R}^n$ and $\alpha\in \mathbb{R}$. Note that $x^*\neq 0$ which comes from the ray being non-vertical.

With this notation, \begin{align*} C = &\{x\in \mathbb{R}^n: \langle x, x^*\rangle\leq \alpha,~ \forall ~r(x^*, \alpha)\in NV\}\\ =&\bigcap_{r(x^*, \alpha)\in NV}\{x\in \mathbb{R}^n: \langle x, x^*\rangle\leq \alpha\}. \end{align*}

Hence, $C$ is the intersection of half-spaces of the form $\{x\in \mathbb{R}^n: \langle x, x^*\rangle\leq \alpha\}$ where $r(x^*, \alpha)$ is a non-vertical extreme ray. In other words, $C$ is the intersection of half-spaces of the form $\{x\in \mathbb{R}^n: \langle x, x^*\rangle\leq \alpha\}$ where all non-negative scalars of $(x^*, \alpha)$ form a non-vertical extreme ray of $C$.

-------

Now for vertical exposed rays, I'll try to give an intuition (I hope this helps). A vertical exposed ray of $G$ is defined by a vertical hyperplane $H$ in $\mathbb{R}^{n+1}$ that defines a valid inequality for $G$ --- by a vertical hyperplane, I mean one of the form $H=\{(x, y)\in \mathbb{R}^n\times \mathbb{R}: \langle (x,y), (x^*, 0)\rangle = \beta\}$ for some $x^*\in \mathbb{R}^n$ and $\beta\in \mathbb{R}$ (note that $\beta$ will actually be $0$ here because of the form of a vertical ray). Note that $G$ is contained on one side of $H$. On the side of $H$ that does not contain $G$, the function support function $\delta^*(\cdot|C)$ equals infinity. This means that if $x\in \mathbb{R}^n$ is separated from $G$ by $H$, then $\delta^*(x|C) = \sup\{\langle x, x^*\rangle:~x^*\in C\} = \infty$ and so $x$ is a recession direction of $C$. So vertical exposed rays do not need to be considered as they define unbounded directions of $C$.

$\endgroup$
  • $\begingroup$ Thanks a lot! Please allow for some time to go carefully through your answer. $\endgroup$ – Manos Feb 1 '17 at 4:01
  • $\begingroup$ You can see how vertical rays are unnecessary from the previous equations for defining $C$. A vertical ray is of the form $r(0, \alpha)$. If you substitute this into the description of $C$, we obtain $$C = \left(\bigcap_{r\in NV}\{x\in \mathbb{R}^n: \langle x, x^*\rangle \leq \alpha\}\right)\cap \left(\bigcap_{r\not\in NV}\{x\in \mathbb{R}^n: \langle x, 0\rangle \leq \alpha\} \right)$$ The latter sets are just $\mathbb{R}^n$, so they don't `contribute' to $C$ $\endgroup$ – JSP Feb 1 '17 at 4:09

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.