This is a classical problem in Linear Programming - to start a simplex method, one must find a vertex. 

This is so-called "Phase I" of the simplex method, and without doubt the best ways to do this have been researched a lot.
See e.g. what 
Brian Borchers [wrote in scicomp](https://scicomp.stackexchange.com/questions/7616/how-to-start-the-simplex-method-from-a-feasible-internal-point/16268#16268), "How to start the Simplex method from a feasible internal point?"  

---

It is not hard to show that $O(mn^2)$ operations suffice. Basically, it's some kind of extended Gauss elimination. Assume that we already have $k$ independent facets with $x_k$ on them, given by a triangularised matrix of the corresponding equations, and the remaining inequalities are also transformed so that the 1st $k\geq 0$ variables do not arise in them.

Now, fix the $k+2$-th, $k+3$-th,... $n$-th coordinate of $x$ to be as in $x_k$, obtaining a univariate system of inequalities -- $k+1$-th coordinate is the variable. It  specifies a finite range $[\tau,\tau']$. Set the $k+1$-th coordinate of $x_{k+1}$ to be equal to either $\tau$ or $\tau'$, and the $k+2$-th,... $n$-th coordinates of $x_{k+1}$ to be the same as in $x_k$.  Use the triangular system of equations to back-solve for $k$-th, $k-1$-th,...,1st coordinates of $x_{k+1}$. (This is all quick, needs $O(nm)$).

Now we have $x_{k+1}$, lying in a face of smaller dimension that $x_k$; at this point one has to triangularise the newly found equations; if the dimension of the face drops by $r$, one needs at most $O(rnm)$ operations. At this point we are ready to repeat the loop, with $k$ increased by $r$.