3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Dima Pasechnik May 9 '19 at 15:38
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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... $\endgroup$ – guigux May 9 '19 at 12:32
  • $\begingroup$ 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$ $\endgroup$ – guigux May 9 '19 at 12:41
  • $\begingroup$ 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. $\endgroup$ – guigux May 9 '19 at 12:43
  • $\begingroup$ probably there is a reason that simplex is fast in Phase I, some kind of general position situation that makes pivoting fast. $\endgroup$ – Dima Pasechnik May 9 '19 at 14:03
  • $\begingroup$ see the edit for something that is probably close to optimal... $\endgroup$ – Dima Pasechnik May 10 '19 at 9:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.