Extreme points of a polyhedral set

I have a set of inequalities that form a polyhedral set. I want to find the extreme points of this. How do I do this? Also, in the image attached, there are only 4 variables. I would like to scale it up as well if needed (upto around 15). Kindly help.

An image of the constraints is attached. Kindly ignore the * on a few of the RHS values. Also for solvability, assume all b values are more than or equal to 0 (lower bounds).

Answer 1

[John D'Errico]

Was it really necessary to put a picture of the equations into your question, when simple text was just as easy? That means, in order for me to solve your problem as is, I need to retype all of your equations by hand, something I hate to do, as I will always make a mistake. These old eyes always get me in trouble these days.

Anyway, there are surely many ways to solve this. Here is one approach.

First, you would need to formulate the problem in a matrix form, of the form A*x <= b. I would also note that 4 of your "equations" are simply bound constraints.

LB = [0 0 0 0];
UB = [2 2 1 1];
A = [1 1 0 0;1 0 1 0;1 0 0 1;0 1 1 0;0 1 0 1;0 0 1 1;1 0 1 1;0 1 1 1]

A = 8×4

1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1

b = [3 3 2 2 2 1 3 3]'

b = 8×1

3 3 2 2 2 1 3 3

I THINK that represents your equations. Now you need ot recognize that a linear program will find ONE vertex of a simplex. So just use linprog, with different objective vectors.

The problem is, linprog only finds one vertex at a time. So I'll run linprog multiple times, using many different sets of orthogonal vectors for f.

vertices = zeros(0,4);
for iter = 1:10
  f44 = orth(rand(4));
  opts = optimset('linprog');
  opts.Display = 'none';
    
  for i = 1:4
      vertices(end+1,:) = linprog(f44(:,i),A,b,[],[],LB,UB,opts);
  end
end

At the end, vertices will have more solutions than we need, because some of the vertices will have been found ultiple times. So I'll discard them.

vertices = uniquetol(vertices,1e-12,'ByRows',true)

vertices = 12×4

0 0 0 1.0000 0 0 1.0000 0 0 1.0000 1.0000 0 0 1.5000 0.5000 0.5000 0 2.0000 0 0 1.0000 1.0000 0 1.0000 1.0000 2.0000 0 0 1.5000 1.5000 0.5000 0.5000 2.0000 0 0 0 2.0000 0 1.0000 0

We can see here that 12 solutions were found as vertices. in 4 dimensions, I would expect no more than 2^4=16 solutions, so this seems reasonable.

Note that in 15 dimensions, you may expect on the order of 2^15=32768 vertices.

[Arjun M]

Thank you so much. This is exactly what I wanted. Can you please explain what the objective function here is? What are we trying to do with the orthogonal vectors?

Also, sorry for not typing in the code.

[Arjun M]

Also, why are you iterating it 10 times? Is there a specific reason to that?

Answer 2

[Matt J]

If the polyhedron is bounded, you can use lcon2vert, downloadable from,

https://www.mathworks.com/matlabcentral/fileexchange/30892-analyze-n-dimensional-convex-polyhedra