Hi everybody

I have got a polytope described by a set of inequalities. I do not have any equality constraints and I do not think that such equality constraints exist at all for this problem.

I wonder, if there any algorithmic or analytical method which can help proving that there is no equality constraints such that I can easily conclude my polytope's dimension. Well, the problem is not a toy size instance, it a huge one.

regards, Shahin

asked 24 Dec '12, 09:59

ShahinG's gravatar image

ShahinG
281213
accept rate: 0%

edited 24 Dec '12, 17:24

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310


The common method for verifying that a polytope has a particular dimension \(d\) (actually the dimension of the affine hull of a polytope) is to exhibit a set of \(d+1\) affinely independent points contained in the polytope. For a full-dimensional polytope in \(R^n\), that is a set of \(n+1\) points \({x^0, x^1, \dots, x^n}\) such that \(x^1 - x^0, x^2 - x^0, \dots, x^n - x^0\) are linearly independent. For a many-dimensional polytope, you'll need to have a systematic way of generating those points.

Note that if the origin is feasible, you can take it as \(x^0\), which might simplify the problem.

link

answered 24 Dec '12, 17:18

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

edited 24 Dec '12, 17:20

many thanks, well, I was searching for a different method. Finding those n+1 points is quite tricky. That "systematic way" is not always trivial. Any article for an alternative method? any tutorial ? any generic/algorithmic way? through introducing an equality/inequality with generic coefficients?

(24 Dec '12, 17:28) ShahinG
1

To prove full dimensionality, all you really need is a point in the strict interior. Polytopes of lower dimension don't have a strict interior.

Once you have that, you can use it as the first point and add small multiples of the n unit vectors to get the remaining points.

(24 Dec '12, 17:46) Matthew Salt... ♦

Thanks. Any article doing similar? By the way, such a strictly interior point does the same job as a origin which (we suppose) is an extreme point?

(25 Dec '12, 03:59) ShahinG
1

That's a basic result--you can probably find it in any nonlinear programming book.

Any feasible point can serve as x^0 in the affine independence test. If you have the origin, the test just reduces to linear independence of the remaining points, with no translation needed.

(25 Dec '12, 08:54) Matthew Salt... ♦

In general, the problem of computing a polyhedron's dimension is at least as hard as solving an LP.

Fortunately, there are polynomial time algorithms. For example, Section 3 of Brick decompositions and the matching rank of graphs by Edmonds, Pulleyblank, and Lovász provides a very general algorithm.

link

answered 16 Oct '13, 02:00

Austin%20Buchanan's gravatar image

Austin Buchanan
1.3k313
accept rate: 42%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×27
×4
×2
×1

Asked: 24 Dec '12, 09:59

Seen: 6,483 times

Last updated: 16 Oct '13, 02:00

OR-Exchange! Your site for questions, answers, and announcements about operations research.