Complexity of finding one vertex of a nonempty polytope

Question

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). Since we need $n$ iterations, that would be a $$O(n^2(m+n^2))$$ algorithm, can't we do better?

Answer 1

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, "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$.