Extreme points of a polyhedral set

39 views (last 30 days)
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).

Accepted Answer

John D'Errico
John D'Errico on 19 Sep 2022
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.
  2 Comments
Arjun M
Arjun M on 20 Sep 2022
Also, why are you iterating it 10 times? Is there a specific reason to that?

Sign in to comment.

More Answers (1)

Matt J
Matt J on 19 Sep 2022
If the polyhedron is bounded, you can use lcon2vert, downloadable from,

Categories

Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!