Let $P$ be a polytope given by some half-space description: $P=\{x\in\mathbb{R}^n: Ax\leq b\}$ for some $A\in\mathbb{R}^{m\times n}, b\in\mathbb{R}^m$. Assume that $x_0\in P$ for some given $x_0$ (in particular, $P\neq\emptyset$). What is the complexity of finding one (i.e., any) vertex of $P$?

Obviously, we can find a vertex in polynomial time by using Linear Programming, by optimizing over $P$ in an arbitrary direction, but I guess we can do better than that. For example, I think it might be possible to shoot from $x_0$ in an arbitrary dimension until a face is hit (which can be done in $O(mn)$), and then proceed inductively within this face. To do this, I think we need to compute a basis for the affine hull of that face, which certainly requires something like $O(n^2)$. Since we need $n$ iterations, that would be a $O(\max(n^3,n^2m))$ algorithm, can't we do better?