Representing point in pointed polyhedral cone

Dependencies:

  1. Polyhedral set and polyhedral cone
  2. Extreme directions of a convex set
  3. Rank of a matrix
  4. Bounded section of pointed cone
  5. Point in polytope is convex combination of BFS
  6. Extreme direction of convex cone as extreme point of intersection with hyperplane
  7. Extreme point iff BFS

Let $C = \{x \in \mathbb{R}^n: (a_i^Tx \ge 0, \forall i \in I) \textrm{ and } (a_i^Tx = 0, \forall i \in E)\}$ be a pointed polyhedral cone.

Let $\xhat \in C$. Let $T \defeq \{i \in I \cap E: a_i^T\xhat = 0\}$ and $B \defeq \{a_i: i \in T\}$. Then $\xhat$ can be represented as a non-negative combination of at most $n-\rank(B)$ extreme directions of $C$.

Proof

This is trivially true when $\xhat = 0$, so assume $\xhat \neq 0$.

Since $C$ is pointed, $\exists c$ such that $c^Tx > 0$ $\forall x \in C - \{0\}$. Without loss of generality, assume $c^T\xhat = 1$ (because we can scale $c$). Let $P \defeq \{x \in C: c^Tx = 1\}$. Then $\xhat \in P$ and $P$ is bounded.

Lemma: $c$ is not a linear combination of $B$.

Proof: Suppose $c$ is a linear combination of $B$. Let $c = \sum_{i \in T}\alpha_i a_i$. Then \[ 1 = c^T\xhat = \sum_{i \in T}\alpha_i(a_i^T\xhat) = 0. \] This is a contradiction. Hence, $c$ is not a linear combination of $B$. □

Since $P$ is bounded and $\xhat$ is tight at $\rank(B) + 1$ linearly independent constraints of $P$, we can represent $\xhat$ as a convex combination of $n - \rank(B)$ BFSes of $P$. The BFSes of $P$ are extreme points of $P$, which are extreme directions of $C$.

Dependency for:

  1. Representing point in full-rank polyhedron

Info:

Transitive dependencies:

  1. /linear-algebra/vector-spaces/condition-for-subspace
  2. /linear-algebra/matrices/gauss-jordan-algo
  3. /complex-numbers/conjugation-is-homomorphic
  4. /sets-and-relations/equivalence-relation
  5. Group
  6. Ring
  7. Polynomial
  8. Integral Domain
  9. Comparing coefficients of a polynomial with disjoint variables
  10. Field
  11. Vector Space
  12. Linear independence
  13. Span
  14. Inner product space
  15. Inner product is anti-linear in second argument
  16. Semiring
  17. Matrix
  18. Stacking
  19. System of linear equations
  20. Product of stacked matrices
  21. Matrix multiplication is associative
  22. Reduced Row Echelon Form (RREF)
  23. Matrices over a field form a vector space
  24. Row space
  25. Elementary row operation
  26. Every elementary row operation has a unique inverse
  27. Row equivalence of matrices
  28. Row equivalent matrices have the same row space
  29. RREF is unique
  30. Identity matrix
  31. Inverse of a matrix
  32. Inverse of product
  33. Elementary row operation is matrix pre-multiplication
  34. Row equivalence matrix
  35. Equations with row equivalent matrices have the same solution set
  36. Rank of a matrix
  37. Basis of a vector space
  38. Linearly independent set is not bigger than a span
  39. Homogeneous linear equations with more variables than equations
  40. Rank of a homogenous system of linear equations
  41. Cone
  42. Convex combination and convex hull
  43. Transitivity of convexity
  44. Convex set
  45. Polyhedral set and polyhedral cone
  46. Basic feasible solutions
  47. Condition for existence of BFS in a polyhedron
  48. Point in polytope is convex combination of BFS
  49. Convex hull of a finite number of points in Euclidean space is bounded
  50. Extreme point of a convex set
  51. Extreme point iff BFS
  52. Condition for a point to be extreme
  53. Condition for polyhedral cone to be pointed
  54. Direction of a convex set and Recession cone
  55. Recession cone of a polyhedron
  56. Polyhedron is unbounded iff it has direction
  57. Bounded section of pointed cone
  58. Extreme directions of a convex set
  59. Extreme direction of convex cone as extreme point of intersection with hyperplane