Suppose the convex polytope is the set of feasible solutions $\mathbf{x}\in\mathbb{R}^n$ for the linear system $\mathbf{A}\mathbf{x}=\mathbf{b}\,,\; \mathbf{A}\in\mathbb{R}^{m\times n}$ subject to some (linear) constraints $\mathbf{0}\leq\mathbf{x}\leq\mathbf{v}$; how is it possible to select an interior point of said polytope, i.e. it doesn't lie on an edge or vertex of the polytope?


Does the algorithm requires the knowledge of what the vertices of the polytope are?



Interior point of a convex polytope
Finding all vertices of the polytope would have the same complexity as the Vertex Enumeration Problem. I do not think that's a practical approach. 


The polytope is the intersection of the box $0\leq x \leq v$, and the hyperplanes $Ax=b$. A point in the interior of the box, which also lies on the hyperplanes is what is desired. Consider the following convex optimization problem:
$$
\max\_{x\in R^n} \left\{\min \{x\_1, v\_1-x\_1,\cdots, x\_n, v\_n-x\_n\} \right\} ~\mbox{subject to}~ Ax=b ~~\&~~ 0\leq x\leq v.
$$


The rationale is that the numbers within the $\min$ brackets are the distances from the $2n$ hyperplanes defining the box. Thus, maximizing the minimum of those forces the optimal point to be in the interior. The optimization problem can be written as an LP with $n+1$ variables and $m+4n$ constraints. Hence this gives a polynomial time algorithm for determining a point in the interior. Also note that the optimal value is positive if and only if such an interior point exists. 


