Abhijeet Mulgund's Personal Webpage

Search

Search IconIcon to open search

Optimal Solution Set of Linear Program is a Face of Constraint Polytope

Last updated Nov 1, 2022

# Statement

Suppose for $n, m \in \mathbb{N}$, $\mathbf{b}, \mathbf{c} \in \mathbb{R}^{n}$, $A \in \mathbb{R}^{m \times n}$, we have the Linear Program $$\begin{align*} &&\max \mathbf{c}^{T} \mathbf{x}\\ &\text{s.t.}&A \mathbf{x} \leq \mathbf{b}\\ &&\mathbf{x} \geq 0, \end{align*}$$ Then the Set of Optimal Solutions is a Convex Polytope Face of the feasible set polytope.

# Proof

TODO