Interior point of polyhedron

Dependencies:

1. Polyhedral set and polyhedral cone
2. Implicit equality

$\newcommand{\xhat}{\widehat{x}}$ Let $P = \{x \in \mathbb{R}^n: (a_i^Tx \ge b_i, \forall i \in I) \wedge (a_i^Tx = b_i, \forall i \in E)\}$ be a non-empty polyhedron. Suppose $P$ doesn't have any implicit equalities. Then $\exists \xhat \in P$ such that $a_i^T\xhat > b_i$ for all $i \in I$. Such an $\xhat$ is called an interior point.

Proof

Let $i \in I$. Since $a_i^Tx \ge b_i$ is not an implicit equality, $\exists x^{(i)} \in P$ such that $a_i^Tx^{(i)} > b_i$. Pick $\xhat = (1/|I|)\sum_{i \in I}x^{(i)}$.

Dependency for:

1. Dimension of a polyhedron

Info:

• Depth: 8
• Number of transitive dependencies: 11

Transitive dependencies:

1. Group
2. Ring
3. Field
4. Vector Space
5. Semiring
6. Matrix
7. Cone
8. Convex combination and convex hull
9. Convex set
10. Polyhedral set and polyhedral cone
11. Implicit equality