2
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you mean that it doesn't lie on a proper face, or on an edge or vertex? That wouldn't necessarily be an interior point. Anyway, an idea would be by induction on the dimension of the faces, using the fact that these are aso convex polytopes. Also, you can triangulate. $\endgroup$
    – efs
    Commented Feb 3, 2020 at 14:56
  • 2
    $\begingroup$ If you know the vertices, you may take a minimal set and use the definition as the convex hull. $\endgroup$
    – efs
    Commented Feb 3, 2020 at 15:02

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Max min optimization is in P with linear objective over a compact polyhedra? $\endgroup$
    – VS.
    Commented Apr 20, 2020 at 3:58
  • $\begingroup$ @VS, thanks for the comment. I have mentioned in my answer that the optimization can be converted to an LP with $n+1$ variables and $m+4n$ constraints. That is, replace the cost function by $t$ (yet another variable), and include constraints $x_i \geq t$, $v_i-x_i\geq t$, $\forall i$. This LP can then be solved using an Interior Point Method. $\endgroup$
    – DSM
    Commented Apr 20, 2020 at 4:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .