The set $$\mathcal P = \{x : Ax \leq b\}$$ is a linear polytope (or, more precisely, an $H$-polytope) and is defined as the intersection of a finite number of halfspaces.
The simplex method for the linear program optimizes over a polytope
$$ \begin{array}{ll} \min_{x\in \mathbb R^n} &c^Tx\\ \mathrm{s.t.} & Ax \leq b \end{array} $$
and initializes by finding an extreme point, e.g $\bar x$ where $A\bar x \leq b$, and $A_I\bar x = b_I$ for a set of row indices $I$ of length $n$, and $A_I$ is invertible.
Suppose that such an $A_I$ exists. Are there any systematic or commonly accepted ways of finding an extreme feasible point? Even if it's a crappy way, are there any ways that are used in practice? I found many references on how to proceed once the feasible point is found, but not how to pick it to begin with.
Thank you!
A common approach is to introduce slack variables $s$, i.e., $Ax + s = b$. Define $s = s^+ - s^-$ with $s^+ \geq 0$ and $s^- \geq 0.$ And consider for objective function $\min_{s,x} 1^Ts^-$. In other words, solve
\begin{array}{ll} \min_{s, x} & 1^T s^-\\ \mathrm{s.t.} & Ax + s= b\\ & s = s^+ - s^-\\ & s^+, s^- \geq 0\\ \end{array}
Then, $s = b$ with $x = 0$ is a solution for that particular problem. Now, if the optimal value is $0$, then $s^- = 0$, hence the corresponding $x$ verifies $Ax \leq b$, and therefore is a solution to your original problem. If the optimal value is not $0$, then your original problem is not feasible.