Suppose that a polyhedron $P\subset\mathbb{R}^n$ has two $\mathcal{V}$-representations $$ \begin{align} P &= \text{conv}(\{x_1,...,x_k\})+\text{coni}(\{w_1,...,w_r\}) \\[4pt] &= \text{conv}(\{y_1,...,y_{\ell}\})+\text{coni}(\{v_1,...,v_s\}). \end{align} $$ Here $\text{conv}$ is the convex combination: $$ \text{conv}(S):=\left\{\sum_{j=1}^J\lambda_jx_j:x_j\in S,\,\lambda_j\ge 0,\,\sum_{j=1}^J\lambda_j=1,\,J\in\mathbb{N}\right\}, $$ and $\text{coni}$ is the conic combination: $$ \text{coni}(T):=\left\{\sum_{j=1}^J\theta_jw_j:w_j\in T,\,\theta_j\ge 0,\,J\in\mathbb{N}\right\}. $$ My question: What can we say about the relation between the points $x_j,w_j,y_j,v_j$ used in the two representations?

My attempt:

  1. Relation between the $x_i$'s and $y_j$'s. It is possible that $x_j\not\in\text{conv}(\{y_1,...,y_{\ell}\})$, since $$ \begin{align} &\quad\ \text{conv}(\{x_1,...,x_k,w_1,...,w_r\})+\text{coni}(\{w_1,...,w_r\}) \\ &=\text{conv}(\{x_1,...,x_k\})+\text{coni}(\{w_1,...,w_r\}). \end{align} $$ The coefficients of $w_1,...,w_r$ in the convex combination can be absorbed into the conic combination.

  2. Relation between the $w_i$'s and $v_j$'s. My intuition tells me that $w_i\in\text{coni}(\{v_1,...,v_s\})$ for each $i$, because the convex combination represents the bounded part of $P$, while the conic combination represents the unbounded part. However, I am unable to give a proof.


1 Answer 1


I have figured out the answer. It is true that $w_i\in\text{coni}(\{v_1,...,v_s\})$ for each $i$.

It suffices to prove that when $P=\text{conv}(\{x_1,...,x_k\})+\text{coni}(\{w_1,...,w_r\})$, its recession cone $$ \text{recc}(P):=\{d\in\mathbb{R}^n:x+\theta d\in P\ \ \forall\,x\in P\ \ \forall\,\theta\ge 0\} $$ is given by $$ \text{recc}(P)=\text{coni}(\{w_1,...,w_r\}). $$ The inclusion $(\supset)$ is obvious. To prove $(\subset)$, for every $d\in\text{recc}(P)$, for every $\theta\ge 0$, since $x_1+\theta d\in P$, then $$ x_1+\theta d=\sum_{i=1}^k\lambda_i(\theta)x_i+\sum_{j=1}^r\mu_j(\theta)w_j, $$ where $\lambda_i(\theta)\ge 0$, $\mu_j(\theta)\ge 0$, and $\sum_{i=1}^k\lambda_i(\theta)=1$. Rearranging the terms, we obtain $$ d=\frac{1}{\theta}\left(\sum_{i=1}^k\lambda_i(\theta)x_i-x_1\right)+\sum_{j=1}^r\frac{\mu_j(\theta)}{\theta}w_j. $$ For all $\theta\ge 0$ it holds that $$ \left\|\sum_{i=1}^k\lambda_i(\theta)x_i-x_1\right\|_2\le \sum_{i=1}^k\|x_i\|_2, $$ so $$ d=\lim_{\theta\to\infty}\sum_{j=1}^r\frac{\mu_j(\theta)}{\theta}w_j\in\text{coni}(\{w_1,...,w_r\}) $$ by the closedness of the cone.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .