# Complexity of finding one vertex of a nonempty polytope

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?

• probably it's better to think of shooting at direction of increasing/decreasing a coordinate of $x_0$. So you compute the slacks at $x_0$ - here you need $O(mn)$: if one of them is 0, you got a facet to restrict to. Otherwise, pick an arbitrary coordinate $k$ of $x_0$, and form a univariate system of inequalities involving this coordinate as a variable. Find a vertex solution to it, this is a new value for the $k$-th coordinate of $x_0$, so that it lies on a facet. This can be done in $O(m)$ operations. – Dima Pasechnik May 9 '19 at 15:38

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

• Hi Dima, yes,you' re right, this problem is related to Phase 1. However, I cannot accept your answer for 2 reasons: In my understanding, the typical (textbook) way to solve Phase 1 is to use simplex iterations, starting from a basic feasible solution for a modified problem. I am interested in complexity, so I would like to avoid the simplex... – guigux May 9 '19 at 12:32
• I also get stuck around the same problem as Dylan Phase 1 adds slack variables and work with an LP in canonical form, for which a BFS is known, while I want a simple method that finds a vertex in the form $P=\{x:Ax\leq b\}$ that takes advantage of the knowledge of a point $x_0 \in P$ – guigux May 9 '19 at 12:41
• It seems that the approach proposed by Rahul in the same question is exactly what I suggested above, I would happily welcome any reference in some text book that describes that approach. – guigux May 9 '19 at 12:43
• probably there is a reason that simplex is fast in Phase I, some kind of general position situation that makes pivoting fast. – Dima Pasechnik May 9 '19 at 14:03
• see the edit for something that is probably close to optimal... – Dima Pasechnik May 10 '19 at 9:07