Bounded section of pointed cone

Dependencies:

Let $C = {x \in R^{n} : (a_{i}^{T} x \geq 0, \forall i \in I) and (a_{i}^{T} x = 0, \forall i \in E)}$ be a pointed cone. Let $A$ be the matrix whose rows are ${a_{i} : i \in I \cup E}$ . Then $rank (A) = n$ .

Let $K \subseteq I \cup E$ and let $B$ be the matrix having rows ${a_{i} : i \in K}$ such that $rank (B) = n$ . Let $b = \sum_{i \in I \cup E} λ_{i} a_{i}$ , where $λ_{i} > 0$ for $i \in K$ . Let $γ > 0$ and let $P = {x \in C : b^{T} x = γ}$ . Then $P$ is bounded and $b^{T} x > 0$ for any $x \in C - {0}$ . Hence, $\forall x \in C - {0}$ , $(γ / b^{T} x) x \in P$ .

Proof

Let $\hat{x} \in C - {0}$ .

Lemma 1: $\exists i \in K$ such that $a_{i}^{T} \hat{x} > 0$ .

Proof: Suppose $a_{i}^{T} \hat{x} = 0$ for all $i \in K$ . Then $B \hat{x} = 0$ . Hence, $\hat{x} = 0$ since $rank (B) = n$ , which is a contradiction. Hence, $\exists i \in K$ such that $a_{i}^{T} \hat{x} > 0$ . □

Lemma 2: $b^{T} \hat{x} > 0$ and $(γ / b^{T} \hat{x}) \hat{x} \in P$ .

Proof: Suppose $a_{k}^{T} \hat{x} > 0$ , where $k \in K$ (by Lemma 1). Then $b^{T} \hat{x} = \sum_{i \in I \cup E} λ_{i} a_{i}^{T} \hat{x} \geq λ_{k} a_{k}^{T} \hat{x} > 0$ . Let $γ / b^{T} \hat{x})$ . Then $μ > 0$ , so $μ \hat{x} \in C$ . $b^{T} (μ \hat{x}) = γ$ , so $μ \hat{x} \in P$ . □

Lemma 3: $P$ is bounded.

Proof: Suppose $P$ is not bounded. Then $P$ has a non-zero direction $d$ . Hence, $d \in C - {0}$ and $b^{T} d = 0$ . Since $d \in C$ , we get $B d \geq 0$ . So, $a_{i}^{T} d \geq 0$ for $i \in K$ . Since $0 = b^{T} d = \sum_{i \in I \cup E} λ_{i} (a_{i}^{T} d) \geq \sum_{i \in K} λ_{i} (a_{i}^{T} d) \geq 0$ and $λ_{i} > 0$ for $i \in K$ , we get that $a_{i}^{T} d = 0$ for all $i \in K$ . Hence, $B d = 0$ . But since $rank (B) = n$ , this means $d = 0$ , which is a contradiction. □

Bounded section of pointed cone

Dependencies:

Proof

Dependency for:

Info:

Transitive dependencies: