Return to 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?

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?

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

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?

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?

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