5
$\begingroup$

A convex polyhedron can be represented by a set of linear inequalities. If the inequalities involve $n$ variables, then the polyhedron can be $n$-dimensional, but it can also be of a smaller dimension - in case some of the inequalities in fact define equalities. As a simple example, the following inequalities:

$$x_1 \geq 0, x_2\geq 0, x_3 \geq 0\\ x_1 \leq 1, x_2\leq 1, x_3 \leq 1 $$

define a 3-dimensional polyhedron (a cube). But if the last inequality is changed to $x_3 \leq 0$ then the polyhedron becomes 2-dimensional (a square).

What is an algorithm for determining the dimension of a polyhedron given by a set of linear inequalities?

EDIT: By "convex polyhedron" I meant any object that can be represented by the intersection of a finite number of half-spaces (i.e., conjunction of finitely many linear inequalities).

$\endgroup$
  • 2
    $\begingroup$ The simplex algorithm can be used to construct a vertex, if the polytope is non-empty. If it is empty the dimension is zero. Once you have a vertex the simplex can also be adapted to compute the neighboring vertices. The difference between the neighboring vertices and the first one are a bunch of vectors. Their rank gives you the dimension. This is what first popped in my head, there should be better methods. $\endgroup$ – plop Jul 19 at 0:56
  • 1
    $\begingroup$ @plop Note that what you suggest is indeed true for poly topes, but may fail for general poly hedrons, since there are non-empty polyhedrons without vertices (e.g. $\mathbb{R}^n$) $\endgroup$ – Discrete lizard Jul 19 at 11:38
  • $\begingroup$ @plop Ah, I just noticed that a convex polyhedron is in fact a polyhedron that is a polytope... (rather than a polyhedron that happens to be convex..., makes sense I guess, as all polyhedra are convex) While there may be better known methods than what you suggest, there may also not be. Perhaps you can turn your comment into an answer? $\endgroup$ – Discrete lizard Jul 19 at 12:44
  • $\begingroup$ Maybe it would be good to clarify whether you're interested in polytopes or polyhedra and use one of those terms. The term "convex polyhedron" means a polytope, but can be confused for general polyhedra (as I just did). $\endgroup$ – Discrete lizard Jul 19 at 12:46
  • 1
    $\begingroup$ @Discretelizard That's true. I implicitly assumed that when they would apply the simplex they would have to transform it to standard form. This always has a vertex, since it is contained in an orthant. There might not be 'neighboring vertices', but all we need are the directions departing from that vertex. Passing to the standard form increases dimension, in general. But one can always map the directions computed from the problem in standard form back to the original variables. And only then compute their rank. $\endgroup$ – plop Jul 19 at 22:08
3
$\begingroup$

While there are probably much more efficient approaches, the following method can be used to compute the dimension in polynomial time, and is not too complicated.

Implicit inequalities

The dimension of a polyhedron $P$ is defined as the dimension of its affine hull, i.e. $\dim P := \dim \mathrm{aff}(P)$.

Let $a^i x \leq b_i$ for $i\in M$ be the linear inequalities that compose the system $A x\leq b$ defining $P$. An inequality $a^i x \leq b_i$ is called an implicit inequality of this system if $a^i x = b_i$ for all $x$ such that $A x\leq b$. Let $A^= x\leq b^=$ denote the subsystem of $Ax\leq b$ that consists only of the implicit inequalities in $Ax\leq b$. Now, we have the folllowing theorem:

Let $P = \{x\in \mathbb{R}^n \mid Ax\leq b\}$ be a nonempty1 polyhedron. Then, $\mathrm{aff}(P) = \{x \mid A^= x= b^=\} = \{x \mid A^= x\leq b^=\}$. Additionally, $\dim P = n - \mathrm{rank}\ A^=$.

(see Theorem 3.17 from Integer Programming by Conforti, Cornuéjols, and Zambelli. Chapter 3.8 contains additional examples for computing the dimension by hand)

So, to compute the dimension of $P$, we first find all implicit inequalities to obtain $A^=$, and then compute the rank of $A^=$. The latter is easy to do, but the first can be rather complicated to do in general (although it is often doable 'by hand' for well structured cases).

Finding implicit inequalities via linear programming

Note that an inequality $a^i x \leq b_i$ is implicit if and only if the hyperplane $a^i x = b_i$ (i.e. the 'border' of the halfspace defined by the inequality) contains $P$. We can determine whether this is the case by solving a pair of linear programs (thanks to @plop for pointing this out). The inequality $a^i x \leq b_i$ is implicit if and only if

$$\max \{a^i x \mid Ax\leq b\} = \min \{a^i x \mid Ax\leq b\} = b_i,$$

or in other words when optimizing within $P$ in the directions of $a^i$ and $-a^i$ both yields the value $b_i$.

To see why this is true, first note that if either of the results of these programs give a value other than $b_i$, we have found some $x\in P$ with $a^i x \neq b^i$, so the inequality is not implicit2.

For the other implication, any point $x'\in P$ that lies outside the hyperplane $a^i x =b_i$ lies inside the hyperplane $a^i x = b'_i$ for some $b'_i\neq b_i$. If $b'_i < b_i$, then $\min \{a^i x \mid Ax\leq b\} \leq a^i x' = b'_i < b_i$, and if $b'_i > b_i$, then $\max \{a^i x \mid Ax\leq b\} > b_i$. So at least one of the linear programs gives a value unequal to $b_i$ if $a^i x \leq b$ is not implicit.

The algorithm

So, a possible algorithm for finding the dimension of $P$ in $\mathbb{R}^n$ when given by a system of $m$ inequalities is

  1. Solve $2m$ linear programs to find the implicit inequalities and $A^=$.
  2. Compute the rank $r$ of $A^=$, and return $n-r$.

Linear programs can be solved in polynomial time via e.g. the interior point method (although the simplex method is much faster in practice), and the rank of a matrix can be computed in polynomial time via Gaussian elimination. So, the dimension of a polyhedron can be computed in polynomial time.

As I mentioned earlier, there are probably much better approaches than what I suggest here. The suggestions offered by @plop in the comments look promising and I recommend anyone looking for something better than what I'm suggesting here to follow them through, but I will end my answer here, it is already long enough.


(The first part of this answer is taken from these slides by Rudi Pendavingh , page 8)


1: If $P$ is empty, then its dimension is $0$. Additionally, we can test whether $P$ is empty via linear programming. So, we can and I will assume that $P$ is non-empty for the remainder of this answer.
2: It may happen that the minimization and maximization program give the same value, but a different one than $b_i$. (Try to think of an example!) In this case, the inequality must be redundant: it can be removed from the system without changing $P$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting! So it is possible that this problem is not fully solved yet? $\endgroup$ – Erel Segal-Halevi Jul 22 at 18:48
  • $\begingroup$ @ErelSegal-Halevi The simplex method, or any algorithm solving the linear programming problem, solves the question of detecting those implicit inequalities. You can just solve the LP problem which objective function is the inequality in question, the constrains are all the inequalities, and then the LP problem with the opposite of the inequality as objective function. Note also that the problem of computing dimension and detecting implicit inequalities are two different problems. $\endgroup$ – plop Jul 22 at 19:43
  • $\begingroup$ About complexity the linear programming problem can be solved in polynomial time. Therefore, all these questions: dimension, implicit inequalities, affine hull, etc can also be solved in that time, since they can be reduced to LP a number of times bounded by the number of inequalities. $\endgroup$ – plop Jul 22 at 20:15
  • $\begingroup$ The problem of solving systems of inequalities is a classic one. Some key words that might be useful to search could be "elimination" + "linear" + "inequalities". I didn't read in detail, but it looks like, for example, this document contains a good part of the topic, if not all that is needed. $\endgroup$ – plop Jul 22 at 20:17
  • $\begingroup$ @ErelSegal-Halevi Well, it seems I was proven wrong rather quickly in thinking this problem was computationally hard. As I state in my answer, there are probably much better algorithms then what I give here, and plop's suggestions in particular look promising, but I feel going into that is outside of the scope of this answer. $\endgroup$ – Discrete lizard Jul 23 at 7:09

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.