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$, $m\geq n$. 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 direction 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 can be done in $O(n^3)$ operations using a QR decomposition (or a bit faster (in theory) if we use fast matrix multiplication, cf. [this paper](https://arxiv.org/pdf/1812.02056.pdf)). Since we need $n$ iterations, that would be a $$O(n^2(m+n^2))$$ algorithm, can't we do better?



Complexity of finding one vertex of a nonempty polytope
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$.


