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?

$\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
    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
    Feb 3, 2020 at 15:02

1 Answer 1

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.

$\endgroup$
2
  • $\begingroup$ Max min optimization is in P with linear objective over a compact polyhedra? $\endgroup$
    – VS.
    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
    Apr 20, 2020 at 4:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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